B木

B木とは

すべての葉は同じレベルにある。

B-Treeは最小次数't'という用語で定義される。tの値はディスクブロックサイズに依存する。

ルートを除くすべてのノードには少なくともt-1個のキーが含まれていなければならない。ルートは最小で1個のキーを含むことができる。

ルートを含むすべてのノードは、最大で (2*t - 1) 個のキーを含むことができる。

ノードの子の数は、そのノードのキーの数に1を足したものである。

ノードのキーはすべて昇順にソートされる。2つのキーk1とk2の間の子には、k1からk2の範囲にあるすべてのキーが含まれる。

B-Treeはバイナリサーチツリーとは異なり、ルートから成長し、縮小する。バイナリサーチツリーは下向きに成長し、また下向きから縮小します。

他のバランス型バイナリサーチツリーと同様、探索、挿入、削除の時間計算量は O(log n)である。

B-Treeのノードの挿入は、Leaf Nodeでのみ行われます。

計算量

Worst/Average case performance for all operations O(log n)

Space complexity O(n)

例: B = 2の場合

https://scrapbox.io/files/639e785c3d795d001d208742.png