1. 序章

このチュートリアルでは、Bツリーと呼ばれるタイプのデータ構造とそのバリエーションであるB+ツリーを見ていきます。 それらの機能、それらがどのように作成されるか、およびそれらがデータベース管理システムでインデックスを作成および管理するためにどのように効果的に使用されるかについて学習します。

最後に、得た知識を使用して、BツリーとB+ツリーを比較します。

2. Bツリーとは何ですか？

Bツリーは、高速なクエリと取得のために大量のデータを格納するために設計された一種の自己平衡ツリー構造です。それらは密接な関係と混同されることがよくあります–二分探索木[X214X ]。 どちらもm-way検索ツリーの一種ですが、二分探索木は特殊な種類のBツリーと見なされます。

Bツリーは、ノード内に複数のキーと値のペアを持ち、キーの順序で昇順で並べ替えることができます。 このキーと値のペアをペイロードと呼びます。 時折、ペイロードの値の部分が「衛星データ」または単に「データ」と呼ばれるのを聞くことがあります。

データベースのコンテキストでは、キーは行の主キーまたはインデックス付き列であり、値は実際の行レコード自体またはそれへの参照である可能性があります。

ペイロードに加えて、ノードは子への参照も保持します。 通常、各ノードはディスクページを使用するため、これらの子参照は通常、子ノードがセカンダリストレージに存在するページIDを参照します。 他の検索ツリーと同様に、Bツリーは、サブツリーのキーがその左側のサブツリーのキーよりも大きくなければならないように編成されています。

2.1. Bツリーのプロパティ

ツリーがBツリーとして分類されるためには、次の条件を満たす必要があります。

  • 順序のBツリー内のノードは最大の子を持つことができます
  • 各内部ノード（非リーフおよび非ルート）には、少なくとも（/ 2）個の子（切り上げ）を含めることができます
  • ルートには少なくとも2つの子が必要です–葉でない限り
  • 子を持つ非リーフノードにはキーが必要です
  • すべての葉は同じレベルに表示される必要があります

下の画像は、Bツリーの例を示しています。 このツリーの子の最大数は3であるため、これは3次のツリーであると結論付けることができます。 すべての葉は同じレベルにあり、ルートノードと内部ノードには、Bツリーのすべての条件を満たす最低2つの子があります。

2.2. Bツリーの構築

それでは、ツリーを最初から作成しましょう。 これを行うには、バランスを保ちながらアイテムをツリーに挿入する方法を学習します。

空のツリーから始めているので、最初に挿入するアイテムがツリーのルートノードになります。 この時点で、ルートノードにはキーと値のペアがあります。 キーは1ですが、値は、表現しやすく、レコードへの参照であることを示すために星印で示されています。

ルートノードには、キーの左右に小さな長方形として表示される、左右の子へのポインタもあります。 ノードには子がないため、これらのポインターは今のところ空になります。
このツリーの順序は3であることがわかっているため、最大2つのキーしか含めることができません。 したがって、キー2のペイロードを昇順でルートノードに追加できます。

次に、3を挿入する場合、ツリーのバランスを保ち、Bツリーの条件を満たすために、いわゆる分割操作を実行する必要があります。

真ん中のキーを選択することで、ノードを分割する方法を決定できます。 真ん中のキーを選択するときは、ノードにすでに存在するキーと、挿入されるキーを考慮する必要があります。 この場合、2はノードを分割するために使用される中央のキーです。 これは、2の左側の値が左側のサブツリーに移動し、2の右側の値が右側のサブツリーに移動し、2自体が新しいルートノードの一部としてプロモートされることを意味します。

ノード内のキーの最大数を超えようとするたびにこの分割操作を実行することにより、ツリーの自己バランスを維持します。

それでは、4を挿入しましょう。 これを配置する必要がある場所を決定するには、右側のサブツリーが左側のサブツリーよりも大きなキーを持つようにBツリーが編成されていることを覚えておく必要があります。 したがって、キー4は右側のサブツリーに属します。 また、右側のサブツリーにはまだ容量があるため、昇順で3と一緒に4を追加するだけです。
右側のサブツリーは現在フルキャパシティーになっているため、5を挿入するには、上記で説明したのと同じ分割ロジックを使用する必要があります。 ノードを2つに分割して、キー3が左側のサブツリーに移動し、5が右側のサブツリーに移動して、4が2とともにルートノードに昇格されるようにします。
このリバランスにより、右端のサブツリーに6を挿入するスペースが与えられます。

次に、7を挿入してみます。 ただし、右端のツリーがフル稼働しているため、別の分割操作を実行して、キーの1つをプロモートする必要があることがわかります。

ちょっと待って！ ルートノードもフルキャパシティーです。つまり、ルートノードも分割する必要があります。

したがって、これは2つのステップで実行することになります。 まず、右側のノード5と6を分割して、7が右側、5が左側、6がプロモートされるようにする必要があります。

次に、6をプロモートするには、4が新しいルートの一部になり、6と2が左右のサブツリーの親になるようにルートノードを分割する必要があります。
このように続けて、最終的なツリーが得られるまで、キー8、9、および10を追加してツリーを埋めます。

2.3. Bツリーの検索

Bツリーは、挿入、削除、および検索操作に関して対数時間計算量を提供するため、非常に有利であると考えられています。

以下の擬似コードを使用して、Bツリーで検索操作を実行する方法を見てみましょう。

   

擬似コードは次のことを前提としています。

  • ノードには、キーと値のペアの配列 node.Payloads と、その子ノードnode.Childrenへの参照の配列があります。
  • ノードオブジェクトには、リーフノードかどうかを判断するnode.IsLeafプロパティがあります。
  • node.Payloads.Count は、ノード内のペイロードの数を示します

ツリーのキーがテーブルのIDを参照していると仮定し、IDが6のレコードを検索したい場合に、この擬似コードをどのように適用できるかを見てみましょう。  つまり、パラメータ node =BツリーのルートノードおよびsearchKey = 6を使用して、擬似コードで定義されたSearchメソッドを呼び出すことになります。

whileループを使用して、ルートノードキーを繰り返し処理し、カウンター値 i を増やして、6以上のキーが見つかるまで、またはそのノードのキーが完了するまで続けます。 ループは、iの値が1で終了します。

ここで、 i = 1 をインデックスとして使用して、 node.Children [1] （インデックス1の子ノード）を選択します。 キーを反復処理すると、 node.Payload[0]。KeyがsearchKeyと完全に一致することがわかります。 キー6に関連付けられた衛星データであるnode.Payload[0] .Valueを返すことにより、検索を終了します。

以下の画像は、灰色で網掛けされた検索パスを示しています。

3. B+ツリー

Bツリーの最もよく知られているバージョンはB+ツリーです。 B +ツリーとBツリーを区別するのは、2つの主要な側面です。

  • すべてのリーフノードは、二重リンクリストで一緒にリンクされています
  • 衛星データはリーフノードにのみ保存されます。 内部ノードはキーのみを保持し、正しいリーフノードへのルーターとして機能します

そのコンテンツをB+ツリーとして表すとしたら、Bツリーがどのように見えるかを見てみましょう。

2、4、5など、一部のキーが重複しているように見えることに注意してください。 これは、リーフノードとは異なり、B +ツリーの内部ノードは衛星データを保持できないため、リーフノードにすべてのキー/値のペアが含まれていることを何らかの方法で確認する必要があるためです。

ツリーを最初から作成して、これがどのように行われるかを見てみましょう。

3.1. B+ツリーの構築

まず、キー1と2を昇順でルートノードに挿入します。

キー3を挿入すると、ルートノードの容量を超えることがわかります。

通常のBツリーと同様に、これは分割操作を実行する必要があることを意味します。 ただし、Bツリーとは異なり、新しい右端のリーフノードの最初のキーをコピーする必要があります。 前述のように、これは、リーフノードにキー2のキー/値ペアがあることを確認できるようにするためです。

次に、キー4を右端のリーフノードに追加します。 いっぱいになっているので、別の分割操作を実行して、キー3をルートノードにコピーする必要があります。
次に、右端のリーフノードに5を追加しましょう。 もう一度順序を維持するために、リーフノードを分割して4をコピーします。 これはルートノードをオーバーフローさせるため、ルートノードを2つのノードに分割し、3つを新しいルートノードに昇格させる別の分割操作を実行する必要があります。

リーフノードの分割と内部ノードの分割の違いに注意してください。 2番目の分割操作で内部ノードを分割したとき、キー3をコピーしませんでした。

同様に、最終的なツリーに到達するまで、必要に応じて分割してコピーするたびに、6から10までキーを追加し続けます。

3.2. B+ツリーの検索

B +ツリー内の特定のキーの検索は、通常のBツリー内のキーの検索と非常によく似ています。 キー6をもう一度検索しますが、B+ツリーで検索するとどうなるか見てみましょう。

影付きのノードは、一致するものを見つけるためにたどったパスを示しています。 推論によると、B +ツリー内を検索するということは、衛星データを取得するためにリーフノードまで下がらなければならないことを意味します。 任意のレベルでデータを見つけることができるBツリーとは対照的です。

完全一致クエリに加えて、B+ツリーは範囲クエリをサポートします。 これは、B+ツリーリーフノードがすべて一緒にリンクされているという事実によって可能になります。 範囲クエリを実行するには、次のことを行う必要があります。

  • 最も低いキーの完全一致検索を見つける
  • そこから、最大のキーを持つリーフノードに到達するまでリンクリストをたどります

4. データベースのコンテキストでのBツリー

データの保存と管理は、コンピューティングの基本的な部分です。 メインメモリはプライマリデータストレージと見なされますが、揮発性で高価であるため、すべてを保存することはできません。 そのため、より安価で揮発性のないセカンダリストレージがあります。 セカンダリストレージは通常、ページと呼ばれる単位で磁気ディスクに保存されます。

ディスクからメモリに要素を転送するには、ディスクからの読み取りが必要です。 1つのディスク読み取りは、そのページから1つの要素のみを読み取ろうとしている場合でも、フルページアクセスを実行します。 ディスクの読み取りはメインメモリの読み取りほど高速ではありません。読み取りを行うたびにシークと回転遅延が発生するためです。 必要なディスクアクセスが多いほど、検索操作にかかる時間が長くなります。

DBMSは、Bツリーインデックスの対数効率を利用して、特定のレコードを見つけるために必要な読み取りの数を減らします。 Bツリーは通常、各ノードがメモリ内の単一ページを占めるように構築されます[ X226X]であり、各ノードが少なくとも半分満たされている必要があるため、アクセス数を減らすように設計されています。

5. BツリーとB+ツリーの比較

BツリーとB+ツリーの比較の最も明白なポイントをカバーしましょう：

  • B +ツリーでは、検索キーを繰り返すことができますが、これはBツリーには当てはまりません。
  • B +ツリーでは衛星データをリーフノードにのみ保存できますが、Bツリーではリーフノードと内部ノードの両方にデータを保存できます
  • B +ツリーでは、リーフノードに保存されたデータにより、内部ノードにより多くのキーを保存できるため、検索がより効率的になります。つまり、アクセスする必要のあるノードが少なくなります。
  • リーフノードからデータを削除するだけでよいため、B+ツリーからのデータの削除はより簡単で時間もかかりません。
  • B +ツリーのリーフノードは相互にリンクされているため、範囲検索操作が効率的かつ迅速になります

最後に、Bツリーは便利ですが、B+ツリーの方が人気があります。 実際、99% ofデータベース管理システムはインデックス作成にB+ツリーを使用します。

これは、B+ツリーが内部ノードにデータを保持していないためです。 これにより、ノードに格納されるキーの数が最大化され、ツリーに必要なレベルの数が最小化されます。 ツリーの深さが小さいほど、検索が速くなります。

6. 結論

この記事では、BツリーとB+ツリーの両方を詳しく調べました。 それらがどのように構築され、特定のキーを検索する方法を学びました。

最後に、私たちが学んだ情報を使用して、構造、使用法、および人気の観点から2つを比較することができました。