B+ツリー

他の木構造と同様に、B+木は、ルート、内部ノード（別名：内部ノード）、および葉ノードの3種類のノードの集合として表現できます。B +木では、これらのノードに対して以下の特性が維持されます。

• もし$\textstyle k_{i}}$B+ツリーの任意のノードに存在する場合、k _{i -1は}そのノードに存在し、${\displaystyle i\geq 1}$。
• すべてのリーフノードは同じ数の祖先を持つ（つまり、すべて同じ深さにある）。

ノードのポインタ特性を以下の表にまとめます。

• K：B+ツリー内の各ノードにおける潜在的な検索キーの最大数。（この値はツリー全体で一定です。）
• p _i : 0 から始まるノードインデックスiへのポインタ。
• k _i : 0 から始まるノードインデックスiの検索キー。

ノードの境界は、以下の表にまとめられています。^{[ 4 ] [ 5 ]}

定義上、B+ ツリーに含まれる各値は、ちょうど 1 つのリーフ ノードに含まれるキーです。各キーは、他のすべてのキーと直接比較可能である必要があり、これにより全順序が形成されます。^{[ 6 ]}これにより、各リーフ ノードは常にすべてのキーをソートされた状態で保持することができ、各内部ノードは、特定のリーフに含まれる値の連続した範囲を表す区間の順序付きコレクションを構築できます。ツリーの上位にある内部ノードは、独自の区間を構築でき、これは、自身の子内部ノードに含まれる区間を再帰的に集約します。最終的に、B+ ツリーのルートは、ツリー内の値の全範囲を表し、すべての内部ノードは部分区間を表します。

この再帰的な区間情報を保持するには、内部ノードはさらに以下を含む必要があります。${\displaystyle m-1}$鍵のコピー${\displaystyle l_{i}}$のために${\displaystyle i\in [1,m-1]}$は、インデックスiの子ノード（それ自体が内部ノードまたは葉ノードである可能性がある）がカバーする区間内の最小要素を表します。ここで、 m は特定の内部ノードの実際の子ノード数を表します。

B+ツリー内で値kを探しています。つまり、ルートから始めて、値kを含む可能性のあるリーフを探します。各ノードで、どの内部ノードをたどるべきかを判断します。B+ツリーの内部ノードは最大で${\displaystyle m\leq b}$ 子ノードはそれぞれ異なる部分区間を表します。m個のエントリを線形探索して対応する子ノードを選択し、最終的に葉ノードに到達したら、そのn個の要素を線形探索して目的のキーを探します。ツリーの各段で全ての子ノードの1つの枝だけをたどるため、${\displaystyle O(\log N)}$実行時間。ここで、Nは B+ ツリーの葉に格納されているキーの総数です。^{[ 4 ]}

function search( k , root ) is let leaf = leaf_search(k, root) for leaf_key in leaf.keys(): if k = leaf_key: return true return false

function leaf_search( k , node ) is if node is a leaf: return node let p = node.children() let l = node.left_sided_intervals() assert${\displaystyle |p|=|l|+1}$let m = p.len() for i from 1 to m - 1: if${\displaystyle k\leq l[i]}$: return leaf_search(k, p[i]) return leaf_search(k, p[m])

この擬似コードでは、1から始まる配列インデックスを使用していることに注意してください。

• 検索を実行して、新しいレコードをどのノードに格納すべきかを判断します。
• ノードが満杯でない場合（最大${\displaystyle b-1}$挿入後のエントリ）、レコードを追加します。
• それ以外の場合は、新しいレコードを挿入する 前に
  • ノードを分割する。
    • 元のノードには${\displaystyle \lceil (K+1)/2\rceil }$商品
    • 新しいノードには${\displaystyle \lfloor (K+1)/2\rfloor }$商品
  • コピー${\displaystyle \lceil (K+1)/2\rceil }$- 番目のキーを親ノードに割り当て、新しいノードを親ノードに挿入します。
  • 分割する必要のない親が見つかるまで、これを繰り返す。
  • 新しいレコードを新しいノードに挿入します。
• ルートが分割された場合は、親が空であるかのように扱い、上記の手順に従って分割します。

B+の木は葉ではなく根から成長する。^{[ 1 ]}

データレコードの集合が与えられたとき、特定のキーフィールドに基づいてB+ツリーインデックスを作成したいとします。一つのアプローチは、各レコードを空のツリーに挿入することです。しかし、各エントリごとにルートから適切なリーフページまで辿っていく必要があるため、この方法は非常にコストがかかります。効率的な代替手段として、一括ロードを使用する方法があります。

• 最初のステップは、検索キーに基づいてデータエントリを昇順に並べ替えることです。
• ルートとして機能する空のページを割り当て、そこにエントリの最初のページへのポインタを挿入します。
• ルートがいっぱいになったら、ルートを分割して新しいルートページを作成します。
• すべての項目が索引付けされるまで、最右端の索引ページ、つまりリーフレベルのすぐ上に項目を挿入し続けてください。

注記：

• 最上位のリーフレベルの上にある最も右側の索引ページがいっぱいになると、そのページは分割されます。
• この操作により、右端のインデックスページがルートに一歩近づいた形で分割される可能性があります。
• 分岐は根から葉のレベルまでの最も右側の経路でのみ発生します。^{[ 9 ]}

削除アルゴリズムの目的は、ツリー構造から目的のエントリノードを削除することです。適切なノードに対して削除アルゴリズムを再帰的に呼び出し、ノードがなくなるまで繰り返します。各関数呼び出しでは、インデックスを使用してノードを探し、削除してから、ルートまで遡って処理を行います。

削除したいエントリLについて：

• Lが少なくとも半分満たされている場合、完了
• Lにd-1個のエントリしかない場合は、兄弟ノード（Lと同じ親を持つ隣接ノード）から借りて再分配を試みます。
  2つの兄弟ノードの再配置が行われた後、親ノードはこの変更を反映するように更新する必要があります。2番目の兄弟ノードを指すインデックスキーは、そのノードの最小値を取る必要があります。
• 再分配が失敗した場合は、Lと兄弟ノードをマージします。マージ後、親ノードは削除されたエントリを指すインデックスキーを削除することで更新されます。つまり、マージが発生した場合は、Lの親ノードから（Lまたは兄弟ノードを指す）エントリを削除する必要があります。

注：マージはルートに伝播する可能性があり、その場合、高さが減少します。^{[ 10 ]}

ReiserFS 、NSS、XFS、JFS、ReFS、およびBFSファイルシステムはすべて、メタデータインデックスにこのタイプのツリーを使用します。BFSはディレクトリを格納するためにB+ツリーも使用します。NTFSはディレクトリおよびセキュリティ関連のメタデータインデックスにB+ツリーを使用します。EXT4は、ファイルのエクステントインデックスにエクステントツリー（修正されたB+ツリーデータ構造）を使用します。^{[ 12 ]} APFSは、ファイルシステムオブジェクトIDからディスク上の位置へのマッピングを格納し、ファイルシステムレコード（ディレクトリを含む）を格納するためにB+ツリーを使用しますが、これらのツリーのリーフノードには兄弟ポインタがありません。^{[ 13 ]}

IBM Db2 [ ^{11 ]} Informix [ ^{11 ]} Microsoft SQL Server ^{[ 11 ]} Oracle 8 [ ^{11 ] Sybase} ASE [ ^{11 ]および}SQLite [ ^{14 ]など}のリレーショナルデータベース管理システムは^{、テーブルインデックスにこのタイプのツリーをサポートしていますが、各システムは、}バリエーションと拡張を加えた基本的な B+ ツリー構造を実装しています。CouchDB ^{[ 15 ] [ a ]}やTokyo Cabinet ^{[ 16 ]}などの多くの NoSQL データベース管理システムも、データアクセスとストレージにこのタイプのツリーをサポートしています。

高次元データベース内で特定のクエリオブジェクトに匹敵するオブジェクトを見つけることは、このようなシステムで最も頻繁に使用されるものの、コストのかかる手順の1つです。このような状況では、B+ツリーを使用して最も近い近傍を見つけることが効果的です。^{[ 17 ]}