Bツリーの特性の紹介

B ツリーは一般的なデータ構造です。彼と一緒にB+ツリーがあります。

ここで、概念を明確にする必要があります。 B ツリー、B ツリー、B+ ツリーの違いは何ですか?彼らの関係は何ですか？

実際のところ、データ構造には B ツリーと B+ ツリーの 2 種類しかありません。 B ツリーは B ツリーとも呼ばれることがあります。これらは同じものです。 B ツリーの中央にある「-」は「マイナス記号」ではなくハイフンであることに注意してください。英語では B-Tree であり、中国語では B-tree と翻訳されます。翻訳者によってはハイフン「-」を含めることを好むため、B-tree となり、一部の読者は B-tree を B-minus tree と誤読します。

B ツリーを紹介する前に、まず重要な概念である「順序」について見てみましょう。

ツリーの順序は、ツリー内の各ノードの子ノードの最大数です。つまり、一部のノードに 2 つの子ノードがあり、一部のノードに 4 つの子ノードがあり、子ノードの最大数が 5 の場合、ツリーの順序は 5 になります。

この観点から見ると、二分木の次数は 2 です。

次に、B ツリーの主な特性を紹介します。 B ツリーの次数は m であると仮定します。 m 次 B ツリーは、空のツリーか、次のプロパティを持つツリーのいずれかです。

1. 各ノードには最大 m 個の子ノードがあります。少なくとも m/2 (切り上げ) 個のノードがあります。または、次のように表現することもできます: m/2 <= 子ノードの数 <= m。ただし、ルートノードは例外です。ルートノードには少なくとも 2 つの子ノードを含めることができます。

2. 各ノードの子ノードの数は、ノードに格納されているキーワードの数より 1 多くなります。つまり、ノードに k 個のキーワードが格納されている場合、ノードには k + 1 個の子ノード (サブツリー) が存在することになります。

3. 各ノード内のk個のキーワードは小さいものから大きいものの順に並べられ、k1、k2、k3、…kkとして記録されます。すると、ノードには p0、p1、p2、... pk と表記される k+1 個のポインターが存在します。さらに、次の図に示すように、p3 が指す子ノード内のすべての要素は k3 より大きく、k4 より小さくなります。これも比較的理解しやすく、覚えやすいです。各ポインタ p は、キーワード k 間のギャップに正確に配置されます。したがって、ギャップのポインタが指す子ノードの要素の値は、当然、ポインタの左側の要素よりも大きく、ポインタの右側の要素よりも小さくなります。