データベースのインデックス — 半分ずつ捨てて探す巻末索引
100万件のテーブルから「name が Tanaka の人」を探すとき、データベースは先頭から1行ずつ全部見ていくこともできます。これが全表スキャン（フルスキャン）。確実ですが、目的の行が後ろにあるほど遅くなります。
そこで使うのがインデックス（索引）。本の巻末索引と同じで、あらかじめ名前順に並べた「見出し表」を別に持っておき、そこから一気に該当箇所へ飛びます。下の図1で、同じ検索を「全表スキャン」と「索引」の両方で走らせ、何回比べたかを見比べてください。
探す名前:
TABLE — 顧客テーブル（挿入順 = id順）
1 Sato
2 Suzuki
3 Takahashi
4 Tanaka
5 Watanabe
6 Ito
7 Yamamoto
8 Nakamura
9 Kobayashi
10 Kato
11 Yoshida
12 Yamada
INDEX — name の索引（名前順にソート済み）
Ito → id 6
Kato → id 10
Kobayashi → id 9
Nakamura → id 8
Sato → id 1
Suzuki → id 2
Takahashi → id 3
Tanaka → id 4
Watanabe → id 5
Yamada → id 12
Yamamoto → id 7
Yoshida → id 11
READY
2つの探し方を走らせてみよう
まず「全表スキャンで探す」を押すと、本体テーブルを上から1行ずつ照合します。次に「索引で探す」を押すと、名前順の索引を半分ずつ絞り込み、該当行へ直行します。比べた回数を見比べてください。
全表スキャン — 回
vs
索引 — 回
図1 — 同じ検索でも「比べた回数」が桁違い。索引は半分ずつ候補を捨てて絞り込む
なぜ索引はそんなに速いのか
全表スキャンは、目的の行が n 番目にあれば n 回照合します（最悪は全件）。一方、索引は名前順に並んでいるので、真ん中を見て「探す名前はそれより前か後か」を判定し、毎回候補を半分に捨てられます。12件なら全表スキャンで最大12回、索引なら4回ほど。100万件なら、全表スキャンの100万回に対して索引はたった20回程度。これが索引の威力です（この半分ずつ絞る木構造が B+Tree です）。
ではなぜ最初から全部に索引を張らないのか。索引はタダではないからです。名前順の見出し表を別に保管するので容量を食い、さらに行を1件追加・更新するたびに索引も並べ直して同期しなければなりません。つまり読み取りは速くなるが、書き込みは少し重くなる。よく検索する列にだけ索引を張る——この見極めがデータベース設計の勘どころです。
用語ミニ辞書
- 全表スキャン
- テーブルを先頭から1行ずつ全部調べる方式。索引が無いときの最終手段。
- インデックス
- 特定の列を並べ替えて作る「見出し表」。本体の行へのポインタを持つ。
- B+Tree
- 多くのDBの索引に使われる木構造。各段で候補を絞り、少ない回数で目的に届く。
- 書き込みコスト
- 行の追加・更新時に索引も同期する必要があり、その分だけ書き込みが重くなる。
まとめ
インデックスは、「あらかじめ並べておいて、半分ずつ絞り込む」ことで検索を劇的に速くする仕組みです。図1で見たように、件数が増えるほど全表スキャンとの差は開きます。ただし索引は容量と書き込みコストを伴うトレードオフ——よく検索する列を見極めて張るのが、速いデータベースの第一歩です。