データベースは、なぜ索引を使うのか

リレーショナルデータベースに大量のデータを保存したとき、探したい行を素早く見つけ出す仕組みが「索引（インデックス）」です。日常の書籍にある巻末索引のように、特定の列の値をあらかじめ整理しておくことで、検索の効率を高めることができます。

結論から言えば、適切な索引があると、表の広い範囲を順に調べる代わりに、条件に合う候補へ少ない参照回数で近づける場合があります。ただし、索引を設ければどのような条件でも検索が一瞬で終わるわけではありません。検索条件の絞り込み具合やデータの並び方、ストレージの読み書き特性など、前提条件が整って初めて効果が発揮されます。

全件走査の基本と、データ量が増えたときの課題

データベースがテーブルから目的の行を探す際、最も基本的な手法が「全件走査（シーケンシャルスキャン / テーブルスキャン）」です。テーブルの先頭から末尾に向かってすべての行を順番に読み出し、条件に合うかを一つずつ判定します。

全件走査は事前の準備や特別な補助構造を必要とせず、すべてのデータを確実に検証できます。全行を取得するクエリやテーブル全体の集計では最も無駄のない手法です。また、条件に合致した時点で走査を打ち切るクエリ（LIMIT 1など）で先頭付近に見つかった場合や、対象データがメモリ上のバッファキャッシュに読み込まれている場合は、ディスクへの物理アクセスを伴わずに高速に処理されることもあります。

しかし、データ量が増加すると全件走査には構造的な負担が生じます。探索対象の行数を N と置いたとき、最悪の場合や全体集計では全行を走査する必要があり、作業量はデータ量に比例して増大する傾向を持ちます。計算量理論ではこれを O(N) と表記しますが、実時間の厳密な比例関係を示すものではありません。実際の処理時間は、CPU速度だけでなくストレージのデータ配置、バッファキャッシュの命中率、並列処理の有無によって大きく変動します。

ストレージからの読み出しに関する単純化した試算を考えてみます。十進単位で200GBのテーブルが存在し、管理情報やキャッシュ、並列処理を考慮しない単一スレッドの連続読み出しを仮定します。仮にストレージの転送速度が秒間500MBであれば、表全体を物理的に読み通すだけで理論上400秒（約6分40秒）を要します。

ブロック単位の先読みや並列走査などの最適化技術があっても、データ規模が数千万行、数億行と拡大するにつれ、表全体の膨大なブロックをディスクから読み出す手法には物理的な限界が生じます。そこで、あらかじめ特定の値の順序を整理した別枠の案内図を用意し、目的のデータへ少ない手順で近づく仕組みとして索引が活用されます。

B-treeの仕組みと多分岐による絞り込み

リレーショナルデータベースで最も標準的に使われる索引構造が「B-tree」です。B-treeは「高さが偏りにくい多分岐の探索木（平衡木）」であり、データの追加や削除が行われても、根（ルートノード）から末端の葉（リーフノード）までの距離が均等に保たれます。

二分探索木は、メモリ上での探索には適していますが、データベースのストレージ管理には適していません。データベースはディスクとメモリの間で「ページ（またはブロック）」と呼ばれる固定サイズ（一般に8KBや16KBなど）の単位でデータをやりとりします。分岐数が2しかない木構造では、データ量が増えると階層が深くなり、目的のデータへ至るまでに多数のページを読み出す必要があります。

そこでB-treeは、1つのノード（1ページ）に多数のキーと子ノードへのポインタを格納し、1つのノードから数十から数百の方向へ分岐する「多分岐構造」をとります。分岐数を大きくすることで、木の高さを低く抑えられます。

理解を助けるための理想化された数値モデルを考えます。内部分岐数が100、葉ノード1ページあたり100件のキーを格納できるB-treeを想定します。

• ルートノード（高さ1）：1ページで100個の子ノードを指す
• 第2層（高さ2）：100ページで10,000個の子ノードを指す
• 第3層（高さ3）：10,000ページで1,000,000個の子ノードを指す
• 第4層（高さ4）：1,000,000ページで100,000,000個の子ノードを指す
• 葉ノード（高さ5）：100,000,000ページ × 100件 ＝ 最大100億件

この理想モデルでは、高さ5ページの探索木で最大100億件のデータを網羅できます。ルートからキーの大小を比較して子ノードを辿れば、最大でも5ページの参照で目的の葉ページに到達できます。

ただし、「10億行から1行を絞り込む」といった表現は説明上の理想化であり、索引を使った検索であっても木構造の複数ノード（ページ）を参照する必要があるため、すべての検索が一定時間で完了するわけではありません。また、ノードの移動回数（参照ページ数）と、ストレージに対する物理的なI/O回数は区別する必要があります。ルートや中間層のノードは頻繁にアクセスされるため、バッファキャッシュ上に常駐している可能性が高く、物理ディスクへのアクセスを伴わないメモリ内参照で済む場合が多いからです。

整列された探索木による範囲の絞り込みを直感的に把握するために、以下の教材ツールを活用してください。

この教材ツール（database-indexes--tool-01）は、固定された16個のキーを題材にして、先頭から1つずつ照合する線形走査と、整列された範囲の中央値との比較によって探索範囲を半減させていく分岐絞り込みの違いを視覚的に体験するための教育用モデルです。

ツールの画面に表示される探索ステップや比較回数は、アルゴリズムの考え方を理解するための教育用教材としての数値であり、実データベースのB-tree実装やディスクI/Oベンチマークそのものではない点に留意してください。実際のデータベースでは多分岐構造やページ単位のキャッシュ管理、充填率が働くため、単純な二分探索の比較ステップとは異なる階層的・物理的な挙動を示します。画面上の比較回数をディスクI/Oや物理読み取り回数と混同しないことが重要です。

葉ノードからデータ本体へ――本体参照の仕組みと違い

B-tree索引を辿って目的のキーを含む葉ノードを見つけた後、データベースは行全体のデータを取得するために本体へアクセスします。

索引の葉ノードには「検索キーの値」と「データ本体の場所を示す参照情報（ポインタ）」が対で記録されています。この参照情報をもとにテーブル本体へアクセスする処理を「本体参照（ヒープフェッチ / テーブル参照）」と呼びます。

本体参照の仕組みは、データベースのアーキテクチャによって異なります。代表的な2つの方式があります。

第1の方式は、PostgreSQLなどに代表される「ヒープタプル参照」です。テーブル本体は「ヒープ」と呼ばれるページ群に格納されます。索引の葉ノードには「TID（Tuple ID）」と呼ばれる識別子（該当行が存在するヒープのページ番号とオフセット位置）が記録されています。探索時はTIDを読み取り、対応するヒープページを直接参照して行データを取得します。

第2の方式は、MySQLのInnoDBなどに代表される「クラスタ化索引とセカンダリ索引」による再探索方式です。InnoDBでは、テーブル本体そのものが主キーをキーとするクラスタ化索引の葉ノードに格納されています。主キー以外の列に作成されたセカンダリ索引の葉ノードには、物理位置ではなく「その行の主キー値」が格納されます。そのため、セカンダリ索引でキーを見つけた後、その主キー値を用いてクラスタ化索引をもう一度探索し直す（インデックスルックアップ）ことで行データに到達します。

なお、本体がヒープ構造の製品における非クラスタ化索引と、クラスタ化索引への参照を保持するセカンダリ索引とでは、内部の参照パスが構造的に異なる点に留意が必要です。

本体参照で性能上の課題となるのが「ランダムI/O」です。索引上でキーが整列していても、テーブル本体側のブロックは分散して配置されているのが一般的です。抽出された行が複数ある場合、ディスクの不連続な領域へのアクセスが繰り返され、処理遅延の原因となります。

この本体参照の負荷を回避する設計手法が「カバリングインデックス（Covering Index）」です。これは、特定のクエリが要求する列（SELECT句やWHERE句に含まれる列）をすべて網羅した索引の構造的性質を指します。そして、本体への参照を行わず索引の葉ノードの情報だけでクエリを完結させる実行計画を「Index-Only Scan（索引オンリースキャン）」と呼びます。

ただし、カバリングインデックスを作成しても常に本体参照がゼロになるとは限りません。例えばPostgreSQLでは、多版型同時実行制御（MVCC）を採用しており、行の可視性情報はヒープ側に保持されています。PostgreSQLにはページ内の全タプルがすべてのトランザクションから可視であることを示す「Visibility Map」があり、該当ページがall-visibleであると確認できた場合に限りヒープアクセスが省略されます。未確認の変更が残るページについては、依然としてヒープを参照して可視性を検証する必要があります。

索引の維持コストと更新時の内部挙動

索引は検索性能を向上させる一方で、ストレージ容量の消費と、データ更新時における処理オーバーヘッドという恒常的なコストを伴います。

テーブルに行を挿入（INSERT）、削除（DELETE）、更新（UPDATE）するたびに、データベースはテーブル本体だけでなく、関連するすべての索引構造の整合性を維持しなければなりません。索引は常にキーがソートされた状態を保つ必要があるため、新しいキーを正しい位置へ挿入する処理が発生します。

特に負荷が高い内部処理が「ページ分割（Page Split）」です。B-treeの葉ノードで新しいキーを挿入しようとしたページがすでに満杯だった場合、データベースはそのページを2つに分割し、キーを再配置します。さらに分割された子ノードの情報を親ノードに反映させる必要があり、連鎖的なページ分割が発生することもあります。ページ分割が起きると、複数のディスクブロックへの書き込みや排他ロックが生じ、書き込み応答時間が一時的に悪化します。

ただし、データを更新するたびに毎回すべての索引が書き直されるわけではありません。例えばPostgreSQLの「HOT（Heap-Only Tuple）更新」では、更新された列がどの索引にも含まれず、更新後のデータが元と同じヒープページ内の空き領域に収まる場合、索引へのポインタ追加を省略してヒープページ内だけにポインタチェーンを構築します。これにより索引の肥大化と更新I/Oを大幅に抑制できます。

このように、索引設計は「検索によって得られる速度向上」と「書き込み性能の低下や容量消費」のバランスを取るトレードオフの管理です。

索引が期待通りに使われない典型的な条件

テーブルの列に索引を作成していても、実行計画を確認すると全件走査が選ばれることがあります。オプティマイザはコスト予測に基づいて最も効率的と判断した実行計画を選択するため、全件走査の方が有利と判断されれば索引走査は採用されません。

オプティマイザが索引の使用を見送る、あるいは通常のB-tree索引では絞り込めない代表的な条件を整理します。

1. 条件に一致する行が多い場合（選択度とカーディナリティの区別）

検索条件によって抽出される行の割合（選択度）が高い場合、オプティマイザは全件走査を選択します。非クラスタ化索引を経由して多数の行を取得すると、膨大なランダムI/Oが発生するためです。テーブル全体の10%〜20%以上を読み出す場合、飛び飛びのアクセスを繰り返すよりも、テーブル全体をシーケンシャルI/Oで順次読み出した方がトータルの所要時間が短くなります。

混同しやすいのが「カーディナリティ（値の種類数）」と「選択度」の違いです。「値の種類数が少ない列には索引が効かない」と一概には言えません。重要なのは「検索条件が抽出する行の割合」です。例えば、注文テーブル全体の中で「未処理」ステータスの行が全体の1%しか存在しない場合、ステータス列の値が3種類しかなくても、WHERE status = '未処理' という検索は高い絞り込み効果を持ち、索引が有効に機能します。逆に、値の種類が多くても大量の行が該当する範囲検索では優位性が失われます。また、テーブル全体のサイズが極めて小さい場合も、木構造を辿るオーバーヘッドを避けて全件走査が選ばれます。

2. 検索条件における列の加工と式に対する索引

WHERE句で列に対して関数や演算を適用すると、列に作成された通常のB-tree索引は利用できません。B-treeは「格納された素の値」の順序で整列しているため、変換後の値の順序までは保証できないからです。

例えば、WHERE EXTRACT(YEAR FROM created_at) = 2026 のような条件では列単位の索引は使えません。この場合は WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01' のように、列を加工せず範囲条件として記述し直す必要があります。

なお、加工した値による検索が必要な場合、PostgreSQLなどでは「式に対する索引（Expression Indexes）」を作成できます。CREATE INDEX idx_orders_year ON orders (EXTRACT(YEAR FROM created_at)); のように式そのものをキーとする索引を構築すれば、該当する式条件に対して索引走査を適用できます。

3. 文字列のパターン検索（LIKE検索）の制約

LIKE句を用いた文字列検索で通常のB-tree索引が利用できるのは、原則として先頭文字列が固定されている「前方一致（例：LIKE 'abc%'）」に限られます。

ただし、前方一致であっても無条件に機能するわけではありません。照合順序（Collation）や演算子クラスの設定に依存し、例えばPostgreSQLの標準Cロケール以外では、B-tree作成時に text_pattern_ops などの演算子クラスを指定しなければ前方一致の範囲走査が適用されない場合があります。

一方、「後方一致（LIKE '%abc'）」や「中間一致（LIKE '%abc%'）」では先頭文字が決まっていないため、通常のB-treeによる範囲絞り込みは機能しません。ただしPostgreSQLの pg_trgm モジュールなどを導入し、文字列を3文字ずつの並びに分解してGiSTやGINといった索引を作成すれば、中間一致検索でも索引走査を活用できます。

4. 複合索引の列順序とスキップ走査

複数の列を組み合わせた「複合索引」では、列を指定する順番が重要です。例えば (A, B) という順序の複合索引は、まず第一列 A の値で整列され、A の値が同一の行同士の中で初めて第二列 B の値で整列されます。

そのため、検索条件に A を含めず B だけを指定した場合、通常の二分探索のように絞り込むことは困難になります。一般には先頭列を指定するクエリの方が効率的に候補を絞り込めます。

ただし、先頭列が指定されていないと絶対に利用できないわけではありません。第一列 A の種類数が少ない場合に A の各値ごとに B の探索を繰り返す「インデックススキップスキャン（Skip Scan）」や、複合索引の葉ノード全体を走査する「インデックスフルスキャン」として利用されるケースもあります。

よくある疑問と実践的な判断

索引の導入や運用において頻出する3つの疑問について、判断の基準を整理します。

Q1: 主キーを設定していれば、他の列に索引を追加する必要はありませんか？

主キー（PRIMARY KEY）を定義すると一意性を保証するために自動で一意性索引が作成されます。主キーを指定する検索にはこの索引が使われます。

しかし、主キー以外の列（顧客の電話番号や注文日など）を条件とする検索では主キーの索引は機能しません。検索、結合（JOIN）、並べ替え（ORDER BY）で頻繁に使われる列については、クエリパターンに応じた適切な索引を個別に検討する必要があります。

Q2: 検索を速くするため、頻繁に参照される列すべてに索引を作成すべきでしょうか？

すべての参照列に網羅的に索引を作成することは推奨されません。索引を追加するごとにINSERT、UPDATE、DELETE時の更新処理が増え、ページ分割やストレージ消費の負荷が高まるためです。

特に更新頻度が高いテーブルでは、過剰な索引によってシステム全体の書き込み性能が低下します。実行頻度が高くボトルネックとなっているクエリに対象を絞り、複数の条件をカバーできる複合索引への集約を検討することが重要です。

Q3: 開発環境では索引走査だったのに、本番環境で同じSQLを実行すると全件走査になるのはなぜですか？

オプティマイザは固定的なルールではなく、行数やページ数、値の分布を記録した「統計情報」をもとにコストを計算して実行計画を決定します。

データ件数が少ない開発環境では全件走査のコストが低く見積もられることがあります。逆に本番環境ではデータの偏りによって検索条件の選択度が高くなり（該当行が多くなり）、ランダムI/Oを避けるために全件走査が選ばれることもあります。本番相当のデータ規模と分布環境で、定期的に統計情報を更新した上で EXPLAIN や EXPLAIN ANALYZE を用いて検証することが不可欠です。

索引を適切に扱うための視点

データベースにおける索引は、検索を無条件に速くする魔法の仕組みではありません。「あらかじめデータを整列して保持し、木構造の案内図を提供することで、走査するブロック数を抑える」という明確なアルゴリズムに基づく工学的トレードオフです。

索引の効果を活かすには、全件走査の特性、多分岐B-treeの探索経路、本体参照に伴うランダムI/O、そして書き込みオーバーヘッドという裏面のコストを正しく理解する必要があります。データ規模、選択度、更新頻度のバランスを見極め、オプティマイザの判断を支援する設計を行うことが重要です。