データベースのインデックスがやっていること — B-tree、検索コスト、書き込みのコスト

2026年8月5日水曜日

読了 5分

データベースが遅くなるときと API の診断で繰り返し登場した処方がインデックスでした。今回はそのインデックスそのものを扱います。インデックスとはいったい何なのか。なぜ 400 万行のスキャンを数回のアクセスに変えられ、代わりに何をコストとして取っていくのか、原理から実務の基準まで整理します。例はリレーショナルデータベースの標準インデックスである B-tree 基準です。

インデックスがないとき — すべての検索は全件走査 #

インデックスのないテーブルで WHERE email = '...' を探す方法は一つだけです。最初の行から最後の行まで全部読みながら比較するフルスキャンです。100 万行なら 100 万回の比較で、テーブルがディスクで占めるページ全部を読む必要があります。データが 2 倍になればコストも 2 倍、成長に正比例して遅くなる構造です。

インデックスはこの構造を変える別の、ソートされたデータ構造です。本の巻末の索引のように「値 → 位置」の対応を値の順序でソートして別に管理し、検索はこの索引を先に探索して、本文(テーブル)の正確な位置へジャンプします。

B-tree — なぜよりによってこの構造か #

ソートされたリストでの速い探索なら二分探索が浮かびますが、データベースはディスクの上で挿入・削除が絶え間なく起きる環境です。B-tree はこの環境に合わせた選択です。

広くて浅い木 — ノード一つがディスクのページ一枚に対応し、ページ一枚にキーが数百個入るので、枝が数百方向に伸びます。その結果、100 万行でも 10 億行でも木の高さは普通 3〜4 段に収まります。検索コストが「行数に比例」から「木の高さの分(事実上の定数)」に変わること、これがインデックスの効果の本質です。
ソートを維持 — リーフノードが値の順序でつながっているので、等値検索だけでなく範囲検索(BETWEEN、>、ORDER BY、前方一致の LIKE 'kim%')も、開始点を見つけた後に横へ読めば済みます。
挿入・削除に耐える — ページが満杯になれば分割されてバランスを保ちます。ソート済み配列のように挿入のたびに全体を押しずらすコストがありません。

100 万行のテーブルでフルスキャンがページ数千枚を読むとき、B-tree の検索はページ 3〜4 枚を読みます。データベースの記事で見た「しきい値の突破」の現象もこの構造で説明できます。テーブルがキャッシュを超えた瞬間、フルスキャンはディスク数千回になりますが、インデックスの検索は相変わらず数回です。

複合インデックス — カラムの順序がすべてです #

複数のカラムを束ねた複合インデックス (team_id, created_at) は、「team_id でソートし、同じ値の中で created_at でソート」した構造です。電話帳が(姓、名)の順なのと同じで、ルールも同じです。

WHERE team_id = 3 AND created_at > ... — 完璧に使えます。
WHERE team_id = 3 — 先頭のカラムだけでも使えます(姓だけで探す)。
WHERE created_at > ... — 使えません。 名前だけ知っていて電話帳をめくるのと同じです。

だから複合インデックスのカラムの順序は「等号の条件でよく使うカラムを前に、範囲の条件を後ろに」が基本ルールです。(A, B) のインデックスがあれば (A) のインデックスはたいてい重複だという点も一緒に覚えておく価値があります。

ここから一歩進んだのがカバリングインデックスです。検索に必要なカラムが全部インデックスの中にあれば、本文のテーブルへジャンプする必要すらなくなり(インデックスオンリースキャン)、頻繁に回る一覧のクエリをもう一段減らせます。

ただではありません — インデックスの請求書 #

インデックスが万能なら全カラムに作ればいいはずですが、そうしない理由があります。

書き込みのたびの税金 — INSERT はすべてのインデックスに項目を追加し、UPDATE は変わったカラムが含まれるインデックスを更新し、DELETE も同様です。インデックス 10 個のテーブルの INSERT は、本文 1 回 + インデックス 10 回の書き込みです。書き込みの多いテーブルの過剰なインデックスは、それ自体が性能の問題です。
保存領域 — インデックスもディスクとキャッシュのメモリを食います。インデックスがテーブルより大きくなったシステムも珍しくありません。
低いカーディナリティには効果が小さい — 値の種類が少ないカラム(性別、ブール値の状態)はインデックスで絞っても半分が残るので、オプティマイザがインデックスを捨ててフルスキャンを選ぶほうがむしろ合理的です。

だから実務の基準はこう要約されます。WHERE・JOIN・ORDER BY に繰り返し登場する、値が十分に多様なカラムに張ります。そして実際に使われているか(各 DB のインデックス使用統計)、書き込みの負荷に見合っているかを定期的に見ます。使われないインデックスは税金だけ払うインデックスです。

張ったのに使われないとき — 最後の関門 #

インデックスがあってもオプティマイザが使わないケース(カラムの加工、型変換、古い統計)はデータベースの記事で扱いました。判定の道具はいつも EXPLAIN で、ORM 観点の活用は Django 上級 #3 を参照してください。「インデックスを作った」と「クエリ実行でインデックスが使われる」は別の話だ、ということだけここで改めて強調しておきます。

まとめ #

インデックスは「値 → 位置」をソート状態で保つ別のデータ構造で、検索コストを行数比例から木の高さ(3〜4 段)に変えます。
B-tree は広くて浅いのでディスクの環境に合い、ソートを維持するので範囲検索と ORDER BY までカバーします。
複合インデックスはカラムの順序がすべてです。等号の条件を前に、範囲を後ろに置き、先頭のカラムのない条件はインデックスを使えません。
インデックスは書き込みのたびに税金を取り、領域を食います。よく検索され値が多様なカラムにだけ張り、使われないインデックスは整理します。
張って終わりではありません。EXPLAIN で実際に使われるかを確認するところまでで一つのサイクルです。