【仕組み解説】データベースのインデックスはなぜ速い？ — B-Treeの仕組みを図解

本当だよ。まず「インデックスがない状態」を想像してみよう。100万行のテーブルから1件探すとき、DBは先頭から1行ずつ全部チェックしていく。これを「フルテーブルスキャン」というんだ。本で言えば、目次も索引もなしに1ページ目から全ページめくって探すようなものだね。

インデックスは、まさに「本の索引（さくいん）」と同じ仕組みだよ。索引には「キーワード → ページ番号」が並んでいるよね。DBのインデックスも「カラムの値 → 行の場所」を整理して保持しているんだ。だから全行を見なくても、索引をたどるだけで目的のデータに一発でたどり着ける。

最も一般的なのが「B-Tree（ビーツリー）」という木構造だよ。根（ルート）から枝分かれしていって、葉（リーフ）に実際のデータへのポインタがある。たとえば100万件のデータでも、B-Treeなら約20回の比較で目的の行にたどり着ける。計算量でいうと O(log n) で、フルスキャンの O(n) と比べると桁違いに速いんだ。

その通り！100万件で約20回、200万件でも約21回。これがB-Treeの強さだね。ちなみに木の各ノードは複数のキーを持てるから、ディスクの読み取り回数も最小限に抑えられる設計になっているんだ。

複合インデックスは、複数のカラムをまとめて1つのインデックスにしたものだよ。たとえば「姓」と「名」で複合インデックスを作ると、「姓＝田中 AND 名＝太郎」の検索が1つのインデックスだけで済む。ただし順番が重要で、「姓, 名」の順で作ったインデックスは「姓」だけの検索にも使えるけど、「名」だけの検索には使えない。電話帳が「姓 → 名」の順で並んでいるのと同じ理屈だね。

カバリングインデックスは、クエリが必要とするカラムがすべてインデックスに含まれている状態のことだよ。通常はインデックスで行の位置を見つけてから、テーブル本体にデータを取りに行く。でもカバリングインデックスなら、インデックスだけで結果が返せるからテーブルへのアクセスが不要になる。これが最速パターンだね。

それが落とし穴なんだ。インデックスは「読み取りを速くする代わりに、書き込みを遅くする」というトレードオフがある。INSERT や UPDATE のたびに、テーブル本体だけでなくインデックスも更新しなきゃいけないからね。インデックスが10個あれば、1回のINSERTで11箇所（テーブル＋インデックス10個）を更新することになる。ストレージ容量も食うし、貼りすぎは逆効果だよ。

EXPLAINコマンドを使うといいよ。SQLの先頭に EXPLAIN をつけると、DBがそのクエリをどう実行するか（実行計画）を教えてくれる。「Seq Scan」と出たらフルスキャン、「Index Scan」と出たらインデックスが使われている。PostgreSQLなら EXPLAIN ANALYZE をつけると実際の実行時間も表示されるから、インデックスの効果を数値で確認できるんだ。

あるよ。代表的なのが「ハッシュインデックス」だね。ハッシュ関数で値を変換して、直接データの場所を割り出す方式だ。完全一致検索（WHERE id = 100）なら O(1) で B-Tree より速い場合もある。ただし範囲検索（WHERE id BETWEEN 1 AND 100）や ORDER BY には使えないという大きな制約がある。だから汎用性の高い B-Tree がデフォルトで使われることがほとんどだね。

基本方針は3つ。まず WHERE 句や JOIN 条件に頻繁に使うカラムにインデックスを貼ること。次に、カーディナリティ（値の種類数）が高いカラムを優先すること。性別のように2種類しかない列はインデックスの恩恵が薄い。最後に、定期的に EXPLAIN で実行計画を確認して、不要なインデックスは削除すること。「必要なものだけを、必要な順序で」が鉄則だよ。