インデックス
検索を高速化するデータ構造。本の索引にあたる、性能設計の第一歩。
概要
インデックスは、テーブル全体を頭から読まなくても目的の行へ素早くたどり着けるようにする、データベースの補助的なデータ構造です。分厚い本から特定の用語を探すとき、1ページ目から順にめくる人はいません。巻末の索引で用語を引き、書かれたページへ直接飛びます。インデックスはまさにこの「索引」をRDBMSのテーブルに対して作る仕組みです。
インデックスがない列を条件に検索すると、データベースは全行を順に調べるフルテーブルスキャンを行います。行数が1万件なら一瞬でも、1億件になれば深刻な遅さになります。インデックスがあれば、対象がどれだけ増えても検索コストの伸びはごくゆるやかです。「このクエリが遅い」という実務の問題の大半は、最終的にインデックスの有無と使われ方の話に行き着きます。
なぜ生まれたか
データ量が小さいうちは、全件走査でも十分に速く、問題は表面化しません。しかしデータベースは使い続けるほどデータが蓄積し、検索時間はデータ量に比例して伸びていきます。ディスクからの読み取りはメモリよりはるかに遅いため、「100万行を全部読む」ことそのものが許容できないコストになります。かといって、検索を速くするためにデータ全体を並べ替えて保持し直すのは、書き込みのたびに大移動が発生して現実的ではありません。
そこで「本体のデータはそのまま、検索したいキーだけを別途整列した構造で持ち、本体への場所情報を添える」という発想が生まれました。これがインデックスです。特に1970年代に考案されたB木（B-tree）は、ディスクへのアクセス回数を最小化しながら、検索・挿入・削除をバランスよくこなせる構造で、以来ほぼすべてのRDBMSの標準インデックスとして使われ続けています。
詳細
B木による検索の仕組み
RDBMSの標準的なインデックスの実体はB木（正確にはその変種のB+木）です。値の範囲でデータを振り分ける「ルートノード」を頂点に、枝分かれを数段たどると目的の値を持つ「リーフノード」に到達する、浅く幅の広い木構造をしています。各ノードはディスクの読み取り単位（ページ）に合わせた大きさで、1億行のテーブルでも3〜4回のページ読み取りで目的の行にたどり着けます。
たとえば WHERE id = 12345 という検索は、ルートから値の範囲で枝を選びながら下りていき、全件走査なしに数回の読み取りで目的のエントリへ到達します。
B+木はリーフノード同士が順にリンクされているため、WHERE price BETWEEN 1000 AND 2000 のような範囲検索や ORDER BY にも強いのが特長です。等値検索しかできないハッシュインデックスとの大きな違いはここにあります。
同じ値を「インデックスあり」と「全行走査」の両方で探して、読む量の違いを見比べてみてください。
12行なら差はわずかですが、木の深さは行数の対数でしか増えません。100万行でも B木なら3〜4ノードで到達し、全行走査は平均50万行を読みます。この差がインデックスの正体です。
インデックスの種類と設計
主キーには自動的にインデックスが作られますが、それ以外は開発者が CREATE INDEX で明示的に設計します。複数の列を組み合わせる複合インデックスでは列の順序が重要で、「(user_id, created_at) のインデックスは user_id 単独の検索には効くが、created_at 単独には効かない」という左端一致の原則があります。よく使うSQLのWHERE句・JOIN条件・ORDER BY句を観察し、それに合わせて張るのが基本です。
このほか、値の重複がないことを保証するユニークインデックス、条件を満たす行だけを対象にする部分インデックス、全文検索用の転置インデックスなど、用途に応じた種類があります。PostgreSQLのGINインデックスのように、JSON型の中身を検索対象にできるものもあります。
書き込みコストとのトレードオフ
インデックスは無料ではありません。行をINSERT・UPDATE・DELETEするたびに、その表に張られたすべてのインデックスも更新する必要があるため、インデックスを増やすほど書き込みは遅くなります。さらにディスク容量も消費します。「検索を速くしたいから全部の列に張る」は典型的なアンチパターンで、読み取りと書き込みのバランスを見て取捨選択するのが設計の勘所です。
もう一つの落とし穴が「張ったのに使われない」ケースです。インデックス列に関数を適用した条件（WHERE UPPER(name) = ...）や前方一致でないLIKE検索（LIKE '%abc'）ではインデックスが効きません。また、絞り込み効果が薄い列（性別のように値の種類が少ない列）では、オプティマイザがあえて全件走査を選ぶこともあります。
実行計画で確かめる
インデックスが実際に使われているかは、推測ではなく EXPLAIN で確かめます。実行計画に「Index Scan」と出れば使われており、「Seq Scan（全件走査）」なら使われていません。遅いクエリに出会ったら、まず実行計画を見る——この習慣がバックエンド開発の性能問題の8割を解決します。なお、頻繁に読むデータを速くする手段としてはキャッシュもありますが、キャッシュが「結果の使い回し」であるのに対し、インデックスは「検索そのものの高速化」であり、両者は補完関係にあります。