B+ 木
B+ 木は、順序付けたキーをページに分けて保存する。内部ノードの区切りキーが探索先を決め、葉ノードがレコードのキーを持つ。すべての葉は同じ深さにあり、キー順のリンクでもつながる。点検索は木を下り、範囲検索は開始位置を見つけてから葉のリンクをたどる。等値検索、範囲検索、インデックス順と一致する ORDER BY に使える。
B+ 木の仕組み
このレッスンの次数 m は内部ノードの最大子数を表す。安定状態のノードは最大 m−1 個のキーを持つ。次数 3 なら 2 個までで、3 個目が分割を起こす。
内部ノード [15,30] の子が担当する区間は <15、15≤key<30、≥30。区切りキーと等しければ右へ進む。レコードのコピーが右の葉にあるためだ。内部キーは探索用で、別のレコードではない。
葉があふれたら左右に分け、右葉の先頭キーを親へコピーする。そのキーは右葉にも残す。内部ノードの分割では中央の区切りキーを親へ移動し、分割後の左右の内部ノードには残さない。
葉リンクも更新する。新しい右葉の next に旧後続を保存してから、旧葉の next を新右葉へ向ける。順序を逆にすると後続を失いかねない。内部ページの分割では子ポインターもキーとともに振り分ける。親もあふれれば分割を上へ伝える。根の分割は新しい根を作り、全葉の深さを同時に一つ増やす。
ステップ実行
既定値は次数 3 で、次を実行する。
insert 10, insert 20, insert 5, insert 15, insert 25, insert 30, search 25, range 9 27
- 10 と 20 を挿入すると、根の葉は
[10,20]になる。 - 5 の挿入で
[5,10,20]があふれる。[5,10]と[20]に分け、20 をコピーして新しい根を作る。 - 15 を挿入すると左葉
[5,10,15]を[5,10]と[15]に分ける。新葉[15]に旧後続[20]を引き継ぎ、[5,10]から新葉へつなぐ。15 を根にコピーする。 - 25 を挿入すると右葉は
[20,25]になる。 - 30 の挿入で右葉を
[20,25]と[30]に分け、30 を根へコピーする。根の[15,20,30]もあふれるため、中央の 20 を新根へ移動する。左右の内部ノードにはそれぞれ 15 と 30 が残る。
最終形は次のとおり。
[20]
/ \
[15] [30]
/ \ / \
[5,10] [15] [20,25] [30]
└────→────→────→
葉リンクは [5,10] -> [15] -> [20,25] -> [30]。各レコードキーは葉層に一度だけ現れる。内部の 15、20、30 は区切りキーだ。
25 の検索は、根の 20 で右、内部キー 30 で左へ進み、葉 [20,25] 内を二分探索する。訪問するページは 3 枚。
閉区間 [9,27] の検索では左葉へ下り、lower bound で 10 を見つける。10 を出力し、リンク先で 15、次で 20 と 25 を出力する。次の葉の 30 は上限を超えるので終了する。結果は [10,15,20,25]、葉間の移動は 3 回。結果ごとに根へ戻ると、葉リンクによる連続走査の利点を失う。
用途
B+ 木は等値検索と順序付き範囲検索の両方に対応する。ハッシュインデックスは等値検索に向くが、ハッシュバケットだけでキー順の走査はできない。B+ 木は子数を増やして高さを抑える。実際のページは図より多くの子を持つため、多数のレコードでも数層に収まることがある。
計算量
レコード数を n、次数を m、返すレコード数を k とする。点検索が訪問するページの層数は O(log_m n)。分割なしの挿入も同じ経路を下る。分割は各層で最大一度なので、ページ層単位では O(log_m n)。範囲検索は開始位置の特定と結果の出力を合わせて O(log_m n+k) となる。
これは次数を固定したモデル、またはページ層の訪問回数としての評価だ。ページ内の二分探索やキー、ポインターの移動には別の CPU コストがある。m を変数とする場合、それらを無視できない。ページがキャッシュにあれば物理ディスク読み取りは不要なので、ページ訪問数はディスク I/O 数ではない。画面の次数 3–5 は分割を見せるための設定で、運用時の推奨値ではない。
境界ケース
- 空の木は根の葉だけを持つ。検索は未検出、範囲結果は空になる。
- 最初の葉分割で新根を作り、高さが一層増える。
- モデルは一意キーのみを扱う。重複挿入では変化しない。実際のインデックスはレコード識別子などで重複を扱える。
- 存在しないキーは選ばれた候補葉で判定でき、全葉の走査は不要。
- 開始位置の lower bound が範囲上限を超えれば、リンクをたどらず終了する。
- 最大キーを超える範囲は末尾の空 next で終了する。
range 1 99は既定の挿入キーをすべて返す。出力件数 k のコストも必要だ。- 画面は最大 12 レコードを表示する。上限後も挿入ボタンは押せるが、制限を説明する。アルゴリズムの容量上限ではない。
よくある間違い
- 葉の区切りキーを移動してレコードを消す。右葉の先頭キーはコピーする。
- 親へ移した中央キーを内部ノードにも残し、子の区間を崩す。
- 区切りキーと等しいとき左へ進み、右葉のレコードを見落とす。
- 旧 next を上書きしてから後続を取得し、葉リンクを切る。
- 範囲内の各キーを根から検索し、一度の下降と連続走査の利点を失う。
- 図のページを PostgreSQL や MySQL の実際のバイト配置と見なす。
モデルの範囲
メモリ内の一意な整数キー、固定次数、あふれた時点の分割を扱い、削除は実装しない。バッファープール、物理 I/O、充填率、圧縮、重複キー、並行処理のラッチ、WAL、MVCC、復旧、ディスク形式は省略する。実際の葉はレコード本体やレコード位置を持つ場合があり、子数も大きい。画面で追うのは探索経路、分割、葉リンクの制約だ。
続けて学ぶ
同じ手法につながるレッスンや、次の概念への入口です。
鍵マークのあるレッスンの操作には有料アクセスが必要です。解説はすべて無料で読めます。
誤りや気になる点を見つけましたか？ フィードバックを送る。