索引とB木 — なぜ一瞬で見つかるのか

100万件の表から1件を探すのに、上から順に全部見ていたら日が暮れます。索引（インデックス）は、探すためだけの「並べ替えた地図」を裏で持っておく工夫。その地図の正体が、データベースの心臓部 B+木です。全行スキャンとの速さの違い、木を根から降りる探索、あふれたノードが分割して育つ様子を、動かして理解します。

1. 索引なし vs 索引あり — 探す手間が桁違い

索引がなければ、DBは目的の行を見つけるまで先頭から1行ずつ全部確認します（フルスキャン）。件数 n に比例して遅くなる O(n) の世界です。いっぽう索引があると、並べ替え済みの地図を半分ずつ絞り込みながらたどれるので、確認回数は 約 log₂n 回で済みます。

下で同じ値を左右で同時に探させ、確認した回数を見比べてください。右の「索引を張る」を切り替えると、遅い全行スキャンが一気に速くなります。

同じ値を探す競走 — 全行スキャン vs 索引
左＝索引なし（バラバラに置かれた行を先頭から順に確認）。右＝索引あり（並べ替え済みなので、真ん中と比べて範囲を半分に折りたたむ）。オレンジ＝今見ているセル、緑＝発見。下の数字が確認したセル数です。索引を外すと右も左と同じ全行スキャンに戻ります。
POINT — 索引の効きめは対数 索引は「探すための並べ替えた副本」。1回比べるごとに候補が半分（一般には木の分岐数ぶんの1）になるので、確認回数は件数の対数に比例する。100万件でもわずか20回ほど。だから索引ありとなしは、件数が増えるほど差が爆発的に開く。
全行スキャン O(n)　　vs　　索引探索 O(log n) n=1,000,000 のとき、全行なら平均50万回、索引なら約20回。ただし索引は書き込みのたびに更新コストがかかる（万能ではない）

2. B+木の探索 — 根から葉へ、範囲は葉のリンクで

DBの索引はただの並べ替えではなく、ディスク向けに設計された多分岐の木 B+木です。中間ノードは「この値より小さいなら左、大きいなら右」の道しるべ（区切りキー）だけを持ち、実際のデータは一番下の葉に集められています。探索は根から区切りキーと比べて枝を選び、葉まで一直線に降りるだけ。

さらに葉どうしは横に鎖でつながっています。だから「20〜60の範囲」のような範囲検索は、先頭の葉を見つけたら鎖をたどるだけで連続して読めます。下で探す値を変え、範囲スキャンも試してください。

B+木を降りる — 探索と範囲スキャン
紫＝根、青の道＝たどった枝。各ノードで「値 ≥ 区切りキー？」を判定して1本の枝だけ選びます。値が4の倍数なら葉に存在（緑）、なければ行き止まり（赤）。範囲スキャンをオンにすると、見つけた葉から下の鎖を右へたどり、連続した値をまとめて拾います。
注意 — B木とB+木のちがい 素のB木は途中のノードにもデータを置く。対してB+木はデータを葉だけに集め、葉を鎖でつなぐ。この一手間のおかげで範囲検索とソート済み読み出しが速いため、実際のRDBの索引はほぼB+木。「B木索引」と呼ばれていても中身はたいていB+木。

3. あふれたら分割 — 挿入とノード分割

木はどうやって低いまま育つのでしょう。鍵はノード分割です。値を挿入すると、まず根から降りて正しい葉に差し込みます。その葉が入りきる上限を超えてあふれたら、ノードを2つに割り、真ん中のキーを1段上へ押し上げます。上の段もあふれれば同じことが連鎖し、根まで割れると木の高さが1段だけ伸びる——だから木は常にバランスを保ちます。

下でスライダーの値を追加してみてください。あふれた瞬間ノードが赤くなり、押し上げられたキーが上の段で光ります。

挿入とノード分割 — 真ん中のキーが上へ昇る
1ノードに入るキーは最大3個（＝4分岐）。あふれると赤く光り、真ん中のキーが親へ昇って分割します（連鎖して根まで割れることも）。緑＝ちょうど追加された/昇ったキー。何度も入れても木がほとんど高くならないことに注目。
あふれ（キー > 上限）→ 中央値を親へ押し上げて2分割 分割は下から上へ連鎖しうるが、増える高さはせいぜい1段。全ノードが半分以上埋まる不変条件が、木を常に O(log n) の高さに保つ

4. 浅くて広い木 ＝ 少ないディスク読み込み

なぜ二分探索木ではなく、わざわざ多分岐の木を使うのでしょう。答えはディスクにあります。ディスクは1回の読み込みで1ページ（数KB）をまとめて運びます。そこで1ノードを1ページに詰め、数百個のキーを1ノードに持たせる——すると分岐数が数百になり、木は驚くほど浅くなります。木の高さ＝ディスク読み込み回数なので、浅い木ほど速いのです。

下で分岐数と件数を動かし、木の高さ（＝読み込み回数）がどれだけ縮むか確かめてください。

分岐数を上げると木が浅くなる
1ノード＝1ディスクページ。分岐数 b を上げるほど、同じ件数 n を保つのに必要な木の高さ h＝⌈logbn⌉ が小さくなります。棒グラフは1回の探索に要するディスク読み込み回数の比較。二分木（b=2）や全行スキャンとの差に注目。
一歩先へ — 索引は「速さと引き換え」の道具 索引は読み取りを劇的に速くするが、タダではない。行を挿入・更新・削除するたびに索引も直す必要があり、書き込みは遅くなる。索引ぶんのディスク領域も食う。だから「よく WHERE や JOIN や ORDER BY に使う列」にだけ張るのが定石。複数列をまとめた複合索引、条件を絞る部分索引、書き込み重視の LSMツリー（RocksDB・Cassandra）など、用途ごとに索引の形も進化している。「何に索引を張るか」はDB設計者の腕の見せどころ。

5. まとめ — 索引の設計図