B木とB+木：データベースインデックスはなぜこんなに速いのか

ディスク I/O を最小化する木構造を深掘りする。

なぜデータベースは数千万、あるいは数億件のレコードから目的のデータを一瞬で見つけられるのか。その裏側にあるのが「インデックス」という仕組みで、これを支える中心的なデータ構造が B-Tree と B+Tree だ。本記事では単純な二分探索木から出発し、リレーショナルデータベース（RDB）がなぜ最終的に B+Tree を選んだのか、その進化の過程と内部構造を掘り下げる。

1. 二分探索木（BST）の限界

データ検索を高速化するデータ構造として、まず思い浮かぶのは「二分探索木（BST）」だろう。二分探索木では各ノードが最大 2 つの子ノードを持ち、左の子は親より小さく、右の子は親より大きい。理想的な状態なら探索の時間計算量は $O (\log N)$ で、非常に速い。

 graph TD
 A["50"] -- "left" --> B["25"]
 A -- "right" --> C["75"]
 B -- "left" --> D["10"]
 B -- "right" --> E["30"]

しかし、二分探索木をそのままデータベースのインデックスに使うには致命的な問題がある。

木の平衡の崩壊

ソート済みの状態でデータを挿入し続けると、二分探索木は一本の連結リストになってしまい、探索効率は $O (N)$ まで劣化する。これを防ぐために AVL 木や赤黒木といった「平衡二分探索木」が生まれ、自動的に平衡を調整して木の高さを $\log N$ に保つ。

ディスク I/O の壁

最大の課題はディスク I/O（Input/Output）にある。メモリ上の操作なら平衡二分探索木で十分速いが、データベースのインデックスは通常ディスク（HDD や SSD）に置かれる。 CPU の計算やメモリへのアクセスと比べると、ディスクからの読み出しは桁違いに遅い。しかもディスクは 1 バイトずつではなく、「ブロック（block）」や「ページ（page）」単位（例えば 4KB、8KB）で読み書きする。二分探索木は 1 つのノードが保持するデータ量が少なく、木の「高さ（深さ）」が深くなりがちだ。木が深いということは、根から目的の葉まで多くのノードをたどるということで、ノードごとに別々のディスクページを読む必要があれば膨大なディスク I/O が発生し、性能は急激に落ちる。

2. B-Tree：高さと I/O を最小限に抑える

ディスク I/O の回数を減らす方針は明快だ。木の高さをできるだけ低く（浅く）する。そのためには、1 つのノードが持つ子ノードを 2 つではなく、数十から数百にする必要がある。

これが B-Tree の基本思想だ。B-Tree は「多分岐木」に分類され、特徴は次のとおり：

1 つのノードに複数のキー（データ）を格納する。
ノードのサイズをディスクページのサイズ（例えば 4KB や 8KB）に合わせ、1 回のディスク I/O で大量のキーをメモリに読み込む。
常に完全な平衡を保つ（すべての葉ノードの深さが等しい）。

 graph TD
 Root["[ 40 , 80 ]"]
 Root -- "< 40" --> Child1["[ 10 , 20 , 30 ]"]
 Root -- "40 - 79" --> Child2["[ 50 , 60 , 70 ]"]
 Root -- ">= 80" --> Child3["[ 90 , 100 ]"]

B-Tree の探索手順

ディスクから根ノードを読み込む。
ノード内でキーの配列を走査（または二分探索）し、目的の値を含む子ノードへのポインタを見つける。
そのポインタが指す子ノードをディスクから読み込み、同じ手順を繰り返す。
目的のキーが見つかったら、関連するデータ（またはディスク上の実データへのポインタ）を取り出す。

例として、B-Tree の 1 ノードに 100 個のキーが入るとしよう。高さ 3（根、中間、葉）の B-Tree なら $100 \times 100 \times 100 = 1,000,000$ （100 万）件のレコードを格納できる。つまり 100 万件の中から 1 件を探すのに、ディスク I/O は最大 3 回で済む。二分探索木の高さは約 20 で 20 回の I/O が発生するから、これは桁違いの改善だ。

3. B+Tree：RDB の最終形

B-Tree はすでに非常に優れたデータ構造だが、MySQL（InnoDB）や PostgreSQL といった現代のリレーショナルデータベースがインデックスに使っているのは、B-Tree の派生構造である B+Tree だ。なぜ B-Tree ではなく B+Tree なのか。理由は「範囲クエリ」と「順次アクセス」の効率が圧倒的に高いことにある。

B-Tree と B+Tree の違い

B+Tree は B-Tree にいくつか重要な変更を加えている：

すべてのデータは葉ノードにのみ存在する。B-Tree では根ノードや中間ノードにも実データ（または実データへのポインタ）が入る。
B+Tree の根ノードと中間ノードは「道しるべ（インデックスキー）」だけを保持し、実データは一切持たない。実データはすべて最下層の葉ノードに置かれる。
葉ノード同士が双方向連結リストでつながっている。隣り合う葉ノードが互いにポインタを持ち、データを横方向に一気にたどれる。

 graph TD
 Root["[ 50 ]"]
 Root --> Node1["[ 25 ]"]
 Root --> Node2["[ 75 ]"]

 Node1 --> Leaf1["[ 10, 20 ]"]
 Node1 --> Leaf2["[ 30, 40 ]"]

 Node2 --> Leaf3["[ 60, 70 ]"]
 Node2 --> Leaf4["[ 80, 90 ]"]

 Leaf1 -- "Next" --> Leaf2
 Leaf2 -- "Next" --> Leaf3
 Leaf3 -- "Next" --> Leaf4

なぜ B+Tree が RDB に最適なのか

1. 1 ノードに格納できるキー数（ファンアウト）が大幅に増える

根ノードと中間ノードが実データを持たないため、1 つのノードに収まる「キーとポインタ」の数は大きく増やせる。例えばページサイズが同じ 4KB でも、B-Tree はデータも持つので 1 ノードに 50 個しか入らないのに対し、B+Tree はキーだけなので 500 個入る。木の高さが下がり、ディスク I/O も減る。

2. 範囲クエリの速度が爆発的に向上する

データベースでは SELECT * FROM users WHERE age BETWEEN 20 AND 30; のような範囲クエリを頻繁に実行する。これを B-Tree でやろうとすると、条件に合うデータをすべて集めるために木の中を上下に行き来することになり、無駄な I/O が大量に発生する。 B+Tree の場合はこうだ：

まず根から下へたどり、age = 20 がある開始葉ノードを見つける。
あとは葉ノード同士を横につなぐ「連結リスト」を順に読み進め、条件（age <= 30）が終わるまで続ける。ディスクの順次アクセス（連続読み出し）は非常に速く、この特性がディスク I/O にもたらす優位性は圧倒的だ。

4. ノード分割と挿入・削除アルゴリズム

データを追加・削除するたびに、インデックスはバランスを保たなければならない。B+Tree には、バランスを自動で維持するアルゴリズムが備わっている。

挿入と分割

新しいキーを挿入するときは、まず検索と同じ経路をたどって目的のリーフノードを見つけ、そこにキーを追加する。そのノードがすでに満杯（上限に達している）なら、ノード分割が起きる。

満杯のノードのキーを二つに分け、新しいノードを二つ得る（あるいは元のノードと新しいノード一つにする）。
分割の境目にある中央のキーを親ノードへ引き上げる。
親ノードも満杯なら、親も同様に分割し、分割は連鎖的に上へ伝播する。
分割が最終的にルートノードまで届くと、新しいルートノードが作られ、木の高さが一段増える。

このように下から上へ構築していくことで、B+Tree は常に「完全なバランス」、つまりどのリーフノードまでの距離（深さ）も完全に等しい状態を保つ。

5. おわりに

データベースが高速な検索を実現できるのは、ひとえに B+Tree のおかげである。B+Tree はディスク I/O という物理的なボトルネックを設計上深く見据え、それを最小限に抑え込む。

木の「高さ」を極限まで抑え、より少ない読み取り回数でデータに到達する。
データをリーフノードに集約し、インデックスノードの密度を高める。
リーフノードを連結リストでつなぎ、範囲クエリでディスクへ順次アクセスできるようにする。

B+Tree が最適化しているのは「アルゴリズムの計算量」だけではない。「ハードウェアの特性（ディスクページアクセス）」でもある——これこそが、B+Tree が何十年にもわたってデータベースの王座に君臨し続ける最大の理由だ。