B+木とディスク指向インデックスの内部

なぜ赤黒木ではなくB+木なのか

二分探索木の世界では赤黒木やAVL木が王様です。高さを O(log n) に保ち、n が10億でも比較は約30回。CPU上のソート済みマップとしては申し分ありません。ところがディスクやSSDに載るデータベースのインデックスでは、これらはほぼ採用されません。理由は一点に尽きます。コストを支配するのが比較回数ではなくページI/Oの回数だからです。

赤黒木は1ノードに1キーしか持ちません。10億件なら木の高さは約30段。各ノードがディスク上のバラバラな位置にあるなら、1回の検索で最悪30回のランダムなページ読み込みが要ります。HDDのシークは数ミリ秒、SSDでも1ページ読み込みは数十マイクロ秒。一方メモリ内の比較はナノ秒です。つまり「30回の比較」は無視できても「30回のランダムI/O」は致命的に遅い。B+木（B-treeの変種、1970年代に確立）はこの不均衡を1ノードに数百キーを詰めて木を低くすることで解消します。

1ノードを1ページに合わせる

B+木の設計はストレージのページ（ブロック）という最小転送単位から逆算されます。ディスクやSSDは1バイトだけを読むことができず、4KBや8KB、16KBといった固定サイズのページ単位でしか読み書きしません。ならば1ノード＝1ページにして、1回のI/Oで取り込んだページを最大限に使い切るのが合理的です。これは仮想メモリがページ単位でしか動かないのと同じ事情です。

1ノードに収まるキー数の上限を**ファンアウト（fan-out）**と呼びます。内部ノードは「キー」と「子ページへのポインタ」を交互に持つので、ファンアウト f はおおよそ次で決まります。

f ≒ ページサイズ / (キー1個 + 子ポインタ1個 のバイト数)
例: 16KBページ, キー16B + ポインタ8B = 24B
    f ≒ 16384 / 24 ≒ 680

ファンアウトが f なら木の高さ h は約 log_f(n)、つまり対数の底が f まで跳ね上がります。f = 680 のとき、葉まで含めて3段で 680^3 ≒ 3.1億、4段で 680^4 ≒ 2100億件を収容できます。どんなに巨大なテーブルでも、検索は3〜4回のページI/Oで葉に到達する。赤黒木の30回との差がそのまま性能差です。

B木とB+木の決定的な違い — データを葉に集める

「B木」と「B+木」は混同されがちですが、データの置き場所が違います。

B+木が値を葉だけに置く狙いは二つです。第一に、内部ノードが値を持たないぶん同じページにより多くのキーとポインタを詰められ、ファンアウトが最大化して木がさらに低くなる。第二に、全データが最下段に一列に並ぶため、葉同士をリンクで繋げば範囲検索が自明になります。内部ノードは「目的の葉はどっちの子か」を示す道標に徹し、値は一切持ちません。だから内部ノードに現れるキーは「区切り（separator）」であって、必ずしも実データの完全なコピーである必要すらありません。

葉のリンク走査 — 範囲検索が速い理由

B+木では全ての葉が双方向リンクリストで左右に連結されています。これが範囲検索の威力の源泉です。WHERE age BETWEEN 20 AND 40 を考えます。

1. ルートから内部ノードを辿り、age=20 を含む葉まで降りる   （ページI/O 3〜4回）
2. その葉から右隣の葉へリンクを辿りながら順に読む
3. age=40 を超えた時点で打ち切る

最初に目的の左端へ降りるところだけが木の探索で、あとは葉のリンクを横に辿るシーケンシャルアクセスです。木を上り下りする必要がありません。物理的にも葉ページが近接配置されていればプリフェッチが効き、連続I/OはランダムI/Oより桁違いに速い。これはLSM木が範囲検索で複数ファイルをマージせねばならず不利になりがちなのと、ちょうど裏表の関係です。ORDER BY やインデックスを使った整列出力も、葉が既にキー順に並んでいるので追加のソートなしに実現できます。

ノード分割 — 上へ伝播する挿入

B+木の平衡は、回転ではなく分割（split）と併合（merge）で保たれます。挿入はまず該当する葉まで降り、そこへキーを入れます。葉に空きがあれば終わり。問題は葉が満杯のときです。

満杯の葉に挿入が来ると、葉をほぼ半分に割って2つの葉にします。そして分割の境目のキーを親の内部ノードへ押し上げ（push up）、新しい葉を指すポインタを親に追加します。ここでB+木らしさが出ます。押し上げるのは「キーのコピー（区切り）」であり、実データは両方の葉に残ります（B木なら中央キーは上へ移動して葉から消える）。

満杯の葉 [10 20 30 40]   ← 25 を挿入したい
   分割 → [10 20] [25 30 40]
   区切りキー 25 を親へコピーして押し上げ
   親に「25 未満は左、25 以上は右」という道標が増える

押し上げによって今度は親が満杯になるかもしれません。その場合は親も分割し、さらにその親へ押し上げる。これが連鎖してルートまで到達すると、ルート自身が分割されて新しいルートが1段上に生まれます。木の高さが増えるのはこの瞬間だけです。重要なのは、二分探索木のように葉に偏って伸びるのではなく、常に根の側から1段ずつ均等に高くなる点。だからB+木は挿入順に関わらず完全な平衡を保ち、最悪でも高さは O(log_f n) に収まります。

ノード併合 — 削除と再平衡

削除は分割の逆です。葉からキーを消した結果、その葉の使用率が下限（一般に約半分）を割るとアンダーフローが起き、平衡を回復する必要があります。手段は二つです。

• 借用（再分配）: 左右どちらかの兄弟ノードに余裕があれば、兄弟から1キーを分けてもらう。同時に親の区切りキーを更新する。
• 併合（merge）: 兄弟にも余裕がなければ、自分と兄弟を1ノードに併合し、その間を仕切っていた親の区切りキーを引きずり降ろす（pull down）。

併合すると親の区切りキーが1つ減るので、今度は親がアンダーフローするかもしれません。これも分割と対称に上へ伝播し、ルートの子が1つだけになればその子が新しいルートになって木の高さが1段縮みます。

なぜ比較回数ではなくI/O回数で設計するのか

ここまでの設計判断はすべて**「遅いのはランダムページI/Oであって、ページ内の比較ではない」という前提から導かれます。1ページを読み込むコストに比べれば、そのページ内で数百キーを二分探索する比較コストは無視できるほど小さい。だから「1ノードに数百キーを詰めて比較回数を増やしてでも、I/O回数（＝木の高さ）を減らす」のが正解になります。計算量とBig-Oの素朴な感覚では「比較が O(log n) なら何でも同じ」ですが、実機では操作の種類ごとにコストの桁が違う**ため、I/Oを定数倍ではなく支配項として扱う必要があります。

しかもDBはたいてい上位2〜3段（ルートと上位内部ノード）をメモリ上のバッファプールにキャッシュします。すると実際にディスクへ取りに行くのは下位1〜2段だけ。3〜4段の木のうちキャッシュ外は実質1〜2回のI/Oで済み、これがインデックス検索が体感的に「一瞬」で返る正体です。連続したメモリ・I/Oアクセスがハードウェアに優しいという原則はメモリレイアウトとデータ局所性と通底します。

まとめ

B+木の核心は「遅いのはランダムページI/Oだ」という現実から逆算した設計にあります。1ノードを1ページに合わせて数百キーを詰め、ファンアウトを上げて木を3〜4段に低く保つことで、どんな巨大テーブルでも検索を数回のI/Oに収めます。値を葉だけに集めて内部ノードを道標に専念させ、葉を双方向リンクで連結することで、範囲検索と整列出力をシーケンシャルな葉走査だけで実現します。平衡は分割と併合の上方伝播で保たれ、木は常に根の側から均等に高くなり縮みます。赤黒木が「メモリ内の1要素1ノードの構造」なら、B+木は「ディスクのページI/Oを最小化するための多分木」であり、両者を分けるのはアルゴリズムの優劣ではなく、コストを支配するのが比較かI/Oかという土俵の違いです。