B木

ノードの条件

次数 $m$ の B木は、1 つのノードに最大 $m-1$ 個のキーと $m$ 本の枝を持ちます。根以外のノードは枠の半分以上を埋め、全部の葉を同じ段に置きます [1]。ノードの中のキーは昇順で、枝はキーの間から下の段へ伸びます。

段数

1 段下りるごとに、探す範囲は枝の数だけ狭まります。段数は ${\log }_{m}n$ に比例するので、枝が多いほど木は浅くなります [4]。ディスクではノード 1 つを 1 ページに入れるので、読み込みの回数は段数と同じです。

記号: $h$ は段数、$n$ はキーの数です。

ページの大きさと次数

次数はページに入るキーとポインタの組の数で決まります。「データベースの段数」の枠は組の大きさを 16 バイトとし、枠の 69 % が埋まるとして求めています。ランダムな順に追加すると、次数の大きい B木の充填率は $\ln 2\approx 0.69$ に近づきます [6]。

追加と分割

根から葉へ下り、葉にキーを入れます。枠を超えたら中央のキーを親へ上げ、ノードを 2 つに分けます。親があふれたら同じことを繰り返し、根が分かれたときだけ段数が 1 増えます。木は根の側へ伸びるので、全部の葉は同じ段のままです [1]。

削除と併合

途中のノードのキーは左の部分木の最大と入れ替え、葉から消します。キーが下限を割ったら、隣に余裕があれば親を通して 1 個借ります。余裕がなければ親のキーを下ろして 2 つを 1 つへ併合します [4]。根のキーがなくなると段数が 1 減ります。

種類ごとの違い

• 2-3 木・2-3-4 木: 次数 3・4 の B木。2-3-4 木は赤黒木と同じ形を表せる [5]
• B+木: 値を葉だけに置き、途中のノードは道案内のキーの複製だけを持つ。葉を横につなぐので、範囲を親へ戻らずに読める [2]
• B*木: あふれたらまず隣へ分け、隣も満杯なら 2 つを 3 つへ分ける。根以外のノードの枠を 2/3 以上埋める [3]
• トップダウン分割: 下りる途中で満杯のノードを先に分ける。親に空きが残るので、葉から親へ戻らない [4]
• コピーオンライト: ページを書き換えず別のページへ書く。親のポインタも変わるので根まで書き直し、古い版を読み続けられる [8]
• Bε木: 途中のノードにバッファを置き、追加と削除の印をためてまとめて下へ流す。1 回の書き込みで多くのキーが動く [9]

B*木の根は分けたときに両方が下限を満たすよう、他のノードより多いキーを持ちます。枠の下限と根の上限は次の式です [3]。

追加と削除の方法

• まとめて構築: キーを整列してから葉を左から詰める。分割がなく、ページがほぼ埋まる [10]
• 半分で併合: キーが下限を割ったら借りるか併合する。充填率は保たれるが、構造の変更が増える
• 空で解放: 葉が空になるまで放っておき、空になったら親から外す。追加が削除より多ければ充填率はあまり下がらず、構造の変更は少ない [7]

計算量

ノードを読み書きする回数で表します。$k$ は範囲で読むキーの数です。* は償却で、操作を続けたときの 1 回あたりを表します。Bε木はバッファをページの大きさ $m^2$ ほどまで広げたときの値です [9]。二分探索木は整列したデータで 1 本に伸びるので、最も遅い場合を載せています。

音

音の高さはキーの値で決めます。動かしたキーと比べているキーを鳴らします。$v$ はキーの値、$v_{\max }$ はキーの最大値です。

出典

1. B木R. Bayer, E. McCreight, Organization and maintenance of large ordered indexes, Acta Informatica, Vol. 1, No. 3, pp. 173–189, 1972
2. B+木と B*木の整理D. Comer, The Ubiquitous B-Tree, ACM Computing Surveys, Vol. 11, No. 2, pp. 121–137, 1979
3. B*木の定義D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1973, Section 6.2.4
4. B木の操作とトップダウンの分割T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, Chapter 18
5. 赤黒木へのつながりR. Bayer, Symmetric binary B-Trees: Data structure and maintenance algorithms, Acta Informatica, Vol. 1, No. 4, pp. 290–306, 1972
6. ランダムな追加での充填率A. C.-C. Yao, On random 2–3 trees, Acta Informatica, Vol. 9, pp. 159–170, 1978
7. 半分で併合と空で解放T. Johnson, D. Shasha, B-trees with inserts and deletes: Why free-at-empty is better than merge-at-half, Journal of Computer and System Sciences, Vol. 47, No. 1, pp. 45–76, 1993
8. コピーオンライトO. Rodeh, B-trees, shadowing, and clones, ACM Transactions on Storage, Vol. 3, No. 4, pp. 1–27, 2008
9. Bε木M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, B. C. Kuszmaul, D. E. Porter, J. Yuan, Y. Zhan, An Introduction to Bε-trees and Write-Optimization, ;login:, Vol. 40, No. 5, 2015
10. まとめて構築G. Graefe, Modern B-Tree Techniques, Foundations and Trends in Databases, Vol. 3, No. 4, pp. 203–402, 2011

このツールで決めたこと

• 読み込みはノードを読んだ回数で、根も毎回数える
• 書き込みはノードを書き換えた回数で、分割は 3 回、2 つを 3 つへは 4 回と数える
• 比較はノードの中を二分探索してキーを比べた回数
• 範囲で親へ戻るときは、読み終えたノードを読み直さない
• 回数は工程ごとに 0 から数える
• B+木の途中のキーは、葉から消えても道案内として残す
• 2-3 木と 2-3-4 木は次数 3・4 の B木として動かす
• トップダウン分割は次数が奇数なら 1 つ上の偶数で動かす
• Bε木の根のバッファはメモリの上にあるものとし、入れるだけなら読み書きに数えない
• Bε木のバッファの大きさは次数と同じにする。計算量の表の値より書き込みは多くなる
• Bε木の削除は消す印を流すだけで、葉の併合はしない
• 二分探索木は木の形を整えない
• 操作の表の回数は、31 個で 8 通りのデータを試した 1 回の平均