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

ひよこ

データベースが遅いって話をよく聞くけど、インデックスを貼ると速くなるって本当？

ペンギン先生

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

ひよこ

それは確かに遅そう…。インデックスがあるとどう変わるの？

ペンギン先生

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

ひよこ

なるほど！でも索引ってどういう構造で整理されているの？

ペンギン先生

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

ひよこ

葉っぱには行の場所が書いてあるんだね。データそのものじゃないの？

ペンギン先生

そこはDBによって違うんだ。MySQLのInnoDBだと主キーの「クラスタインデックス」の葉に行データそのものが入っていて、索引をたどるとそのままデータのページに着く。一方でそれ以外の索引（セカンダリインデックス）の葉には主キーの値が入っていて、そこからもう一度クラスタインデックスを引き直すんだよ。「葉＝ポインタ」と丸暗記せず、使っているDBの構造を確認するのが大事だね。

ひよこ

O(log n) ってことは、データが倍に増えても比較回数は1回しか増えないってこと？

ペンギン先生

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

ひよこ

複合インデックスっていうのも聞いたことがあるけど、普通のインデックスと何が違うの？

ペンギン先生

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

ひよこ

カバリングインデックスっていうのもあるって聞いたけど、それは何？

ペンギン先生

カバリングインデックスは、クエリが必要とするカラムがすべてインデックスに含まれている状態のことだよ。通常はインデックスで行の位置を見つけてから、テーブル本体にデータを取りに行く。でもカバリングインデックスなら、インデックスだけで結果を返せる可能性がある。PostgreSQLではこれを「インデックスオンリースキャン」と呼ぶんだ。

ひよこ

「可能性がある」って、必ず速くなるわけじゃないの？

ペンギン先生

そう、ここが誤解されやすいところ。PostgreSQLのインデックスには「その行が今見えていいかどうか」の可視性情報が入っていなくて、テーブル側にしかないんだ。だから可視性マップのビットが立っていないページは、結局テーブルを見に行くことになって普通のインデックススキャンと変わらなくなる。更新が頻繁なテーブルでカラムを詰め込んでも期待どおりには効かない、ということだね。

ひよこ

じゃあ全部のカラムにインデックスを貼れば最強ってこと？

ペンギン先生

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

ひよこ

むやみに貼っちゃダメなんだね…。効果があるか確認する方法ってあるの？

ペンギン先生

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

ひよこ

B-Tree以外のインデックスもあるの？

ペンギン先生

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

ひよこ

インデックスの設計って奥が深いんだね…。実務ではどう判断すればいいの？

ペンギン先生

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

参考資料

確認日：2026年9月23日。挙動はDB製品とバージョンで異なるため、実際の判断は使用中のDBの公式ドキュメントで確認してください。

• PostgreSQL: Index Types — CREATE INDEXの既定はB-Tree。ハッシュインデックスは等価比較（=）のみ扱える
• PostgreSQL: Index-Only Scans and Covering Indexes — 可視性情報はインデックスになく、可視性マップ次第でテーブル参照が発生する
• PostgreSQL: Using EXPLAIN — 実行計画の読み方と EXPLAIN ANALYZE
• MySQL: Clustered and Secondary Indexes — クラスタインデックスの葉に行データが入り、セカンダリインデックスは主キー値を保持する