インデックス

概要

インデックスは、テーブル全体を頭から読まなくても目的の行へ素早くたどり着けるようにする、データベースの補助的なデータ構造です。分厚い本から特定の用語を探すとき、1ページ目から順にめくる人はいません。巻末の索引で用語を引き、書かれたページへ直接飛びます。インデックスは、この「索引」をRDBMSのテーブルに対して作る仕組みです。

インデックスのない列を条件に検索すると、データベースは全行を順に調べるフルテーブルスキャン（全件走査）を行います。1万行なら一瞬でも、1億行になれば深刻な遅さになります。インデックスがあれば、行がどれだけ増えても、読むページ数はほとんど増えません。「このクエリが遅い」という実務の問題の多くは、最終的にインデックスの有無と使われ方の話に行き着きます。

ただし、インデックスは無料ではありません。行を書き換えるたびにインデックスも書き換える必要があり、ディスクも消費します。どの列に、どんな順番で張るかを決めるのは、読み取りと書き込みの損得を見積もる設計の仕事です。

なぜ生まれたか

データベースの検索が遅くなる根本の原因は、ディスクがメモリよりけた違いに遅いことです（メモリ階層）。データベースはデータを「ページ」（PostgreSQL は 8KB、MySQL の InnoDB は 16KB）という単位でディスクに置き、ページ単位で読み書きします。全件走査では、行が増えるのに比例して読むページも増えます。かといって、検索を速くするためにデータ全体を並べ替えて持ち直すと、書き込みのたびに大移動が起こります。

そこで「本体のデータはそのまま、検索に使うキーだけを整列した別の構造に持ち、本体の場所を添える」という発想が生まれました。問題は、その整列した構造自体もディスクに置くしかなく、挿入や削除のたびに並びを保つ必要があることです。二分探索木のように1つの節に2つの枝しか持たない構造では、100万件で約20段になり、1段ごとにディスクを1回読むことになります。

1970年、Boeing の研究所にいた Rudolf Bayer と Edward McCreight は、1つの節に数百のキーを詰めて、ディスクの1ページを1つの節にする B木（B-tree）を考案しました（論文は1972年）。枝分かれが数百あれば、1億件でも3〜4段で底に届きます。挿入でページがあふれたら2つに分け、木は根の側に1段伸びるので、どの葉までの段数も常にそろいます。この B木と、その変種である B+木は、以来ほぼすべてのRDBMSの標準のインデックスとして使われ続けています。

詳細

B+木で探す — 1段に1ページ

RDBMS の標準的なインデックスの実体は B+木です。根（ルート）の節から値の範囲で枝を選び、数段たどると、キーと行の場所を持つ葉（リーフ）に着きます。節の1つ1つがディスクの1ページで、1ページには数百のキーが入ります。枝分かれ（ファンアウト）が数百あると、2段で数万、3段で数千万、4段で数十億のキーを振り分けられます。1億行のテーブルでも、3〜4回のページ読み取りで目的の行にたどり着けるのはこのためです。しかも上の段のページはよく使われるので、ほとんどがメモリ上のバッファに載っており、実際にディスクまで行くのは葉と本体の1〜2回で済むことが多くなります。

たとえば WHERE id = 12345 は、根から値の範囲で枝を選びながら下りていき、全件走査なしに数回の読み取りで目的のエントリに届きます。

B+木は葉同士が順につながっているので、WHERE price BETWEEN 1000 AND 2000 のような範囲検索や ORDER BY にも強いのが特長です。最初の葉を見つけたら、あとは隣の葉へ順にたどるだけで済みます。

挿入とページの分割 — 木は根の側に伸びる

B+木の巧みさは、挿入の扱いにあります。新しいキーは、探索と同じ道をたどって入るべき葉に置かれます。葉のページがあふれたら、キーを半分ずつ2枚のページに分け、境目のキーを1つ上の節へ持ち上げます。上の節もあふれたら同じように分割し、根まであふれたら新しい根を作ります。木が1段深くなるのはこの瞬間だけで、しかも根の側で伸びるので、すべての葉までの段数は常に同じです。偏った順番でキーを入れても、片側だけが深くなることはありません。

キーを次々に入れて、ページがあふれて割れ、木が根の側に伸びる様子を確かめてください。下の段では、行を1万から1億まで増やしたときに、全件走査と索引で読むページ数がどう変わるかを比べられます。

分割にはコストもあります。連番のキー（自動採番の id や時刻）は常に右端の葉に入るので分割が1か所に集中し、ランダムなキー（UUID v4 など）はあちこちの葉を分割してページを半分ずつ空けていきます。書き込みの多い表で主キーに UUID を使うと、インデックスが膨らみ、キャッシュに載りにくくなるのはこのためです。時刻順に並ぶ UUID v7 などが好まれるようになった背景には、この事情があります。

クラスタ化インデックスとカバリングインデックス

葉に「行そのもの」を置くか、「行の場所」だけを置くかで、インデックスは2種類に分かれます。MySQL の InnoDB では、テーブル自体が主キーの B+木になっていて、葉に行のすべての列が入っています。これをクラスタ化インデックスと呼びます。それ以外のインデックス（セカンダリインデックス）の葉には、キーと主キーの値だけが入っています。セカンダリインデックスで探すと、見つけた主キーでもう一度クラスタ化インデックスをたどって行を取りに行きます。PostgreSQL は表の本体（ヒープ）とインデックスを別に持ち、どのインデックスの葉も行の物理的な場所を指します。

クエリが必要とする列がすべてインデックスの葉に入っていれば、本体を見に行く必要がありません。これをカバリングインデックスと呼び、PostgreSQL の実行計画では Index Only Scan として現れます。CREATE INDEX … INCLUDE (name) のように、検索には使わない列を葉にだけ載せて、カバリングにすることもできます。逆に SELECT * は、どのインデックスでもカバーできないので、毎回2回目の探索を強いられます。

複合インデックスと列の順序

主キーには自動でインデックスが作られますが、それ以外は CREATE INDEX で明示的に張ります。複数の列を組み合わせる複合インデックスでは、列の順序が重要です。(user_id, created_at) のインデックスは、電話帳が「姓→名」の順に並んでいるのと同じで、user_id で並べたうえで、同じ user_id の中を created_at で並べています。そのため user_id 単独の検索や「user_id が一致し、created_at が範囲」の検索には効きますが、created_at 単独の検索には基本的に効きません。これを左端一致の原則と呼びます。

ただし例外もあります。先頭の列の値の種類が少ないときに、その値ごとに2列目を探し直す「スキップスキャン」を使えるデータベースがあります（Oracle、MySQL 8.0.13 以降、PostgreSQL 18 以降）。とはいえ先頭の列の種類が多いと効果はなく、よく使うSQLの WHERE 句・JOIN の条件・ORDER BY を観察して、その形に合わせて列の順序を決めるのが基本です。

B+木以外にも、用途に応じた種類があります。等値検索だけに使えるハッシュインデックスは、キーをハッシュ化した値で直接バケットを引くので速い一方、並びを持たないため範囲検索や並べ替えには使えません。文章の中の単語で探す全文検索には、語から文書を引く転置インデックスを使います。PostgreSQL の GIN インデックスは、この転置インデックスの仕組みで配列や JSON の中身を検索対象にできます。値の重複を禁止するユニークインデックス、条件を満たす行だけを対象にする部分インデックスもよく使います。

書き込みコストと「張ったのに使われない」

インデックスを増やすほど、INSERT・UPDATE・DELETE のたびに更新するインデックスが増え、書き込みは遅くなります。ディスク容量も消費し、メモリのバッファも奪い合います。「検索を速くしたいから全部の列に張る」は典型的なアンチパターンで、読み取りと書き込みの割合を見て取捨選択します。

もう1つの落とし穴が「張ったのに使われない」ケースです。インデックスの列に関数をかけた条件（WHERE UPPER(name) = ...）や、前方一致でない LIKE（LIKE '%abc'）では、並びをたどれないのでインデックスが効きません（関数の結果に張る式インデックスで対処できます）。また、該当する行が表の大部分を占める条件では、索引をたどって1行ずつ拾うより全件を順に読むほうが安いので、オプティマイザはあえて全件走査を選びます。

実行計画で確かめる

インデックスが実際に使われているかは、推測ではなく EXPLAIN で確かめます（実行計画）。「Index Scan」「Index Only Scan」と出れば使われており、「Seq Scan（全件走査）」なら使われていません。遅いクエリに出会ったら、まず実行計画を見る習慣が、性能問題の多くを解決します。なお、よく読むデータを速くする手段にはキャッシュもありますが、キャッシュが「結果の使い回し」であるのに対し、インデックスは「探す作業そのものを短くする」仕組みで、両者は補い合う関係です。

試問

B+木の索引に、キーを1つずつ入れて育てます。1つの箱がディスクの1ページで、ページがあふれると2枚に割れます。葉のキーを押すと、そのキーを根から探す索引の読み方と、葉を左端から1枚ずつ読む全件走査の読み方で、読んだページ数が比べられます。