B+Tree インデックスの内部構造

なぜ B+Tree なのか

PostgreSQL・MySQL(InnoDB)・SQL Server・Oracle など、主要 RDB の標準インデックスはほぼ例外なく B+Tree です。二分探索木やハッシュではなく B+Tree が選ばれる理由は、ただ一点に集約されます。ディスク I/O の回数を最小化する ことです。

メモリ内なら1回のポインタ参照は数ナノ秒ですが、ディスク(特に HDD、SSD でも相対的に)へのランダムアクセスは桁違いに遅い。したがって索引構造の良し悪しは「比較回数」ではなく「何回ディスクを叩くか」で決まります。B+Tree はこの I/O 回数を木の高さに抑え込み、しかもその高さを極端に低く保つように設計されています。

ページと扇出し(fan-out)

B+Tree のノードは、DB のストレージ単位である ページ(PostgreSQL なら 8KB、InnoDB なら 16KB)とほぼ1対1で対応します。1ノードの読み込み = 1ページの読み込み = 原則1回のディスク I/O、という関係が出発点です。

二分木は1ノードに子が2つしかありませんが、B+Tree は1ページに 多数のキーと子ポインタ を詰め込みます。1ノードが持てる子の数を 扇出し(fan-out) と呼びます。

扇出し f のとき、行数 N に対する木の高さ h は
  h ≒ log_f(N)

例) ページ 8KB、キー+ポインタが 1 件 16 バイトなら
    f ≒ 8192 / 16 ≒ 500
    N = 1億 のとき h ≒ log_500(1億) ≒ 3

つまり扇出しが大きいほど対数の底が大きくなり、高さが劇的に下がります。1億行でもわずか3〜4回の I/O で葉に到達できる のはこのためです。二分木(底2)なら同じ1億行で高さ27、すなわち最悪27回のランダム I/O が必要で、勝負になりません。

構造：内部ノードと葉ノード

B+Tree は役割の違う2種類のノードで構成されます。

点検索(WHERE id = 42)は、ルートから内部ノードの区切りキーを二分探索して子を選び、葉に着いたらそこで目的のキーを探します。高さぶんの I/O で必ず葉に着く、つまり 全件で探索コストが一定(平衡木) なのが B+Tree の強みです。

ノード分割(split)

挿入でノードが満杯になると、そのままでは入りません。このとき行うのが 分割(split) です。

1. 満杯の葉ノードを、ほぼ半分ずつの2つの葉に分ける。
2. 中央(または右側先頭)のキーを 親の内部ノードへ押し上げる(コピーアップ)。
3. 親もそれで満杯になれば、親をさらに分割し、必要なら根まで伝播する。
4. 根まで分割が伝播すると、新しい根が作られ、木の高さが1段増える。

B+Tree の高さが増えるのは、この「根の分割」が起きるときだけです。だからこそ高さは滅多に増えず、低く保たれます。分割は局所的(高々 高さ ぶんのノード書き換え)で済むため、挿入コストも対数に抑えられます。

マージ・再配分とフィルファクタ

削除でノードのキー数が下限(一般に容量の半分)を割ると、過疎なページが増えて空間効率が落ちます。これを防ぐのが マージ(merge) と 再配分(redistribution) です。

• 再配分: 隣の兄弟ノードに余裕があれば、キーを借りてきて両者を半分前後に均す。親の区切りキーも更新する。
• マージ: 兄弟も過疎なら2ノードを1つに統合し、親から区切りキーを1つ削除する。これが伝播すると木の高さが1段減ることもある。

満杯まで詰め込まず、各ページに意図的に空き(余白)を残す割合を フィルファクタ(fillfactor) と呼びます。PostgreSQL の B+Tree は既定で 90% です。

葉ノードのリンクリストと範囲検索

B+Tree 最大の実務的利点が、葉ノード同士が左右の双方向リンクで繋がっている ことです。葉をキー順に辿るだけで、全データを昇順(または降順)に列挙できます。

-- created_at に B+Tree インデックスがある前提
SELECT * FROM orders
WHERE created_at BETWEEN '2026-06-01' AND '2026-06-30'
ORDER BY created_at;

DB はまず木をたどって範囲の先頭(2026-06-01)の葉を1回で見つけ、あとは葉リンクを順次たどって 末尾までスキャンします。ランダムアクセスは最初の1回だけで、残りは隣接ページの順次読み(シーケンシャル I/O)です。これが範囲検索・ORDER BY・GROUP BY・MIN/MAX を B+Tree が得意とする理由です。ハッシュインデックスは等値(=)は速くても、この順序性が無いため範囲検索に一切使えません。

なぜディスク I/O に最適なのか(まとめ)

B+Tree がストレージ向きである理由を整理します。

設計上の特徴	もたらす効果
1ノード=1ページ	ノード参照=1 I/O に対応し、計算量がそのまま I/O 回数になる
大きな扇出し	木の高さが log_f(N) に圧縮され、数億行でも数 I/O で葉に到達
常に平衡(高さ一定)	どのキーでも最悪計算量が同じで、性能が予測可能
分割・マージが局所的	挿入・削除も対数コストで、構造が自動で整う
葉の双方向リンク	範囲・整列が順次 I/O で処理でき、ランダムアクセスを排除

点検索も範囲検索も低い I/O で捌け、書き込みでも構造が自律的に平衡を保つ。この 読み・書き・範囲のバランスの良さ こそが、半世紀にわたり B+Tree が索引の標準であり続ける理由です。

なお、実行計画でこのインデックスが実際に使われるかは書き方次第です。索引が効く・効かない条件は クエリ最適化 を、巨大表をさらに分割して扱う手法は パーティショニング を参照してください。全文検索のように B+Tree が不得手な領域では 全文検索 の転置インデックスが使われ、同時更新時の整合性は ロックと MVCC が担います。