Tech Learning Daily — DB のインデックスはなぜ速いのか？ B+Tree の中を覗く

DB 🌿 基礎 ⏱ 約 7 分

DB のインデックスはなぜ速いのか？ B+Tree の中を覗く

遅いクエリに CREATE INDEX を 1 本足しただけで、実行時間が数秒からミリ秒台まで落ちた経験は誰にでもあるはずだ。だが「なぜ速くなるのか」を聞かれると、「O(log N) になるから」で説明を終えてしまいがちではないか。それは結果の言い換えであって、中で何が起きているかの説明にはなっていない。

🎯 3 行まとめ

多くの DB のインデックスの正体は B+Tree で、1 ノードに数百のキーを詰め込み木を横に広く浅く保つことで、探索を数回のページアクセスで終わらせる
リーフノードはデータの並び順に横方向へ連結されており、範囲検索（BETWEEN や ORDER BY）が速いのはこの連結リスト構造のおかげ
インデックスを増やすと書き込みのたびに複数の B+Tree を更新することになり、ページが満杯になると分割が親ノードへ連鎖して余計な I/O を生む

全表探索と木構造、何が違うのか

インデックスがないテーブルへの WHERE 検索は、先頭行から最後の行まで順に条件を確認する全表探索（フルスキャン）になる。行数を N とすると比較回数は N に比例し、行数が 10 倍になれば探索時間もおよそ 10 倍になる。これを避けるために使われるのが、値を整列した木構造をたどって目的の行にたどり着く探索木の発想だ。

単純な二分探索木なら 1 ノードにキーが 1 つしかなく、N 件のデータを格納すると木の深さは log₂N になる。100 万行でも深さは 20 段ほどで済むが、ディスク上のインデックスでは 1 段たどるごとに 1 回のページ読み込みが発生しうるため、20 回のディスクアクセスはまだ重い。そこでB+Tree（1 つのノードに複数のキーと子への参照を持たせ、実データはすべて末端の葉ノード（リーフノード）に集める木構造）では 1 ノードに数百のキーを詰め込み、木を縦ではなく横に伸ばす。この「1 ノードあたりの子の数」をファンアウトと呼び、ファンアウトが数百あれば 100 万行でも木の深さは 3〜4 段で収まる。

🍱 たとえるなら

郵便物の仕分けを思い浮かべてほしい。1 通ずつ全国の住所と照合していたら日が暮れるが、実際の仕分けは都道府県 → 市区町村 → 地域の集配局という数段階の絞り込みで届く。仕分けの拠点をどれだけ増やしても、絞り込みの段階数はほとんど変わらない。B+Tree のファンアウトが高いというのは、この「1 段階あたりの分岐先」を数百に増やすことに相当し、だからこそ対象件数が増えても木の深さ（絞り込みの段階数）はほとんど増えない。

InnoDB の実装で見る、クラスタ化インデックスとセカンダリインデックス

MySQL の InnoDB では、B+Tree のノードはディスク上のページという単位で管理され、デフォルトのページサイズは innodb_page_size で 16KB だ。主キーに対応するクラスタ化インデックスは葉ノードに行データそのものを格納するため、主キー検索はこの木を 1 回たどるだけで完結する。一方、主キー以外の列に貼るセカンダリインデックスの葉ノードには、インデックス対象の列の値と主キーの値だけが入っており、行の全カラムは持たない。

そのためセカンダリインデックスで検索すると、まずそのインデックスの木をたどって主キー値を得て、次にその主キー値でクラスタ化インデックスをもう一度たどって行データを取得する、という 2 段階の探索になる。SELECT * でセカンダリインデックスの列を検索条件にした場合に、インデックスを使っているはずなのに主キー検索単体より遅く感じるとしたら、この二段引きが理由であることが多い。

        ┌────────┐
        │  root  │ ← 1ノードに数百キー
        └───┬────┘
      ┌─────┼─────┐
      ▼     ▼     ▼
   ┌────┐ ┌────┐ ┌────┐
   │leaf│▶│leaf│▶│leaf│ ← 横に連結
   └────┘ └────┘ └────┘

範囲検索が速いのは、葉が横につながっているから

B+Tree の葉ノードは、値の昇順で互いにポインタを持ち合う連結リストになっている。WHERE age BETWEEN 20 AND 30 のような範囲検索では、まず 20 以上の最初の行を木を上からたどって見つけたあと、そこから先はルートに戻らず葉ノードのリンクを右へたどるだけで 30 を超えるまでの行を拾い続けられる。ORDER BY で並び替えが必要なクエリも、この葉の並び順をそのまま使えれば別途ソート処理を挟まずに済む。

これは B+Tree が単純な二分探索木より優れている理由の一つでもある。二分探索木は木構造の中に実データを分散して持つため、範囲検索のたびに木を行ったり来たりする必要があるが、B+Tree は実データ（またはそこへの参照）をすべて葉に集めて横に並べているため、範囲検索を「一度だけ木を降りて、あとは横に歩く」という単純な操作に還元できる。

書き込みが遅くなる理由 ― ページ分割の連鎖

インデックスは検索を速くする代わりに、書き込みに新たなコストを課す。1 回の INSERT や UPDATE は、対象テーブルに貼られたインデックスの数だけ B+Tree の更新を必要とする。インデックスが 5 本あれば、行データの更新に加えて 5 本分の木を辿ってページを書き換えることになり、書き込みコストはインデックス数にほぼ比例して増える。

インデックスを増やすと書き込みが線形に遅くなるだけ、と思われがちだが、実際にはそれだけでは済まない。挿入先のページがすでに満杯だと、DB はページを 2 つに分割して半分のキーを新しいページへ移すページ分割を行う。このとき親ノードにも新しいページへのポインタを追加する必要があり、親ノードまで満杯なら分割はさらに上の階層へ連鎖する。ランダムな値（UUID など）を主キーやインデックス列にすると、挿入位置が木全体に分散するためこのページ分割が頻発しやすい。PostgreSQL は 14 以降、この連鎖を減らすために不要になった行の痕跡を分割前に葉ページから間引く「ボトムアップ削除」を自動で行っているが、書き込みコストそのものをゼロにする仕組みではない。

💼 実務でどう出会うか

EXPLAIN や EXPLAIN ANALYZE の実行計画に Seq Scan（全表探索）と Index Scan の違いが出てくるのは、まさにここで見た木構造をたどっているかどうかの差だ。また大量データを一括インポートする ETL 処理では、先にインデックスを外してから流し込み、最後に CREATE INDEX を張り直す手法がよく使われる。挿入のたびにページ分割を繰り返すより、全件が揃った状態で一度に木を組み立てるほうが総コストが小さいからで、これも今回見た書き込みコストの構造をそのまま利用した最適化だ。

⌨️ 手を動かす（5 分）

同じ検索条件でも、インデックスの有無で実行計画がどう変わるかを手元の SQLite で確かめる。sqlite3 は macOS に標準で入っている。

sqlite3 /tmp/idx-demo.db <<'SQL'
DROP TABLE IF EXISTS users;
CREATE TABLE users(id INTEGER PRIMARY KEY, email TEXT);
INSERT INTO users(email)
  WITH RECURSIVE seq(n) AS (
    SELECT 1 UNION ALL SELECT n+1 FROM seq WHERE n < 100000
  )
  SELECT 'user' || n || '@example.com' FROM seq;
EXPLAIN QUERY PLAN
  SELECT * FROM users WHERE email = '[email protected]';
CREATE INDEX idx_users_email ON users(email);
EXPLAIN QUERY PLAN
  SELECT * FROM users WHERE email = '[email protected]';
SQL

1 回目の EXPLAIN QUERY PLAN は SCAN users と表示され、10 万行を先頭から順に確認していることが分かる。CREATE INDEX のあとの 2 回目は SEARCH users USING INDEX idx_users_email (email=?) に変わり、B+Tree をたどる探索に切り替わったことが実行計画の文言そのものから確認できる。

🙅 よくある誤解

インデックスは貼れば貼るほど得 — 検索は速くなるが、INSERT・UPDATE・DELETE のたびに貼った本数だけ B+Tree を更新するコストがかかる。使われないインデックスは書き込みを遅くするだけの負債になる。
インデックスは 1 ノードに 1 件のキーを持つ二分探索木 — 実際の DB のインデックスは 1 ページに数百件のキーを詰め込む B+Tree で、木の深さは数百万行のテーブルでも 3〜4 段程度に収まる。
インデックス対象の列を WHERE に書けば必ずインデックスが使われる — オプティマイザは統計情報からコストを見積もって使うインデックスを選ぶ。対象列に関数をかけている場合や、値の種類が少なく絞り込み効果が薄い列では、全表探索の方が安いと判断されインデックスが使われないことがある。

📖 用語ミニ辞典

B+Tree: 1 ノードに複数のキーと子への参照を持たせ、実データを末端の葉ノードに集める木構造。多くの RDB のインデックス実装の基盤。
リーフノード: B+Tree の末端にあたるノード。行データそのもの、または行データへの参照を保持する。
ファンアウト: 1 つのノードが持つ子ノードの数。値が大きいほど木は横に広く浅くなり、探索に必要な段数が減る。
クラスタ化インデックス: 葉ノードに行データそのものを格納するインデックス。InnoDB では主キーがこれにあたる。
セカンダリインデックス: クラスタ化インデックス以外のインデックス。葉ノードには対象列の値と主キー値だけを持つ。
ページ分割: 挿入先のページが満杯のときに、キーを 2 つのページへ分けて空きを作る操作。親ノードへの更新が連鎖することがある。

🔗 もっと深く

InnoDB Cluster and Secondary Indexes - MySQL 8.4 Reference Manual — クラスタ化インデックスとセカンダリインデックスの構造・二段引きの仕組みを一次情報で確認できる。
65.1. B-Tree Indexes - PostgreSQL Documentation — PostgreSQL の B-Tree の内部構造、ページ分割、重複排除の仕組みを解説する公式ドキュメント。
B+Tree index structures in InnoDB - Jeremy Cole — 実際のページダンプ付きで InnoDB の B+Tree の物理構造を掘り下げたエンジニアリングブログ。