インデックス — 知識ノート

特定の列で高速に探せるようにする補助データ構造。

索引が無ければ全件走査（ $O (n)$ ）。 B+木の索引があれば $O (\log n)$ 。

100 万行を全件走査 … 数秒
B+木で探索        … ミリ秒未満

B+木#

性質	内容
平衡	すべての葉が同じ深さ
多分岐	1 ノードに数百のキー
葉が連結	範囲検索が速い
高さ	100 万行でも 3〜4 段

多分岐なのは、 ディスクの 1 ページ（数 KB）をまるごと読むため。 1 回の I/O で多くのキーを比較できる方が有利。

代償#

代償	内容
書き込みが遅くなる	更新のたびに索引も更新する
容量	索引自体が場所を取る
保守	断片化する

索引は読みと書きのトレードオフ。 使われない索引は害でしかない。

複合インデックス#

sql

CREATE INDEX idx ON users (status, created_at);

列の順序が決定的に重要。

WHERE status = 'active'                        → 使える
WHERE status = 'active' AND created_at > ...   → 使える
WHERE created_at > ...                         → 使えない（左端が無い）

電話帳が「姓 → 名」の順に並んでいるのと同じ。名前だけでは探せない。

効かない書き方#

sql

WHERE YEAR(created_at) = 2024      -- 関数を掛けると使えない
WHERE created_at >= '2024-01-01'   -- こう書けば使える

WHERE name LIKE '%田%'              -- 前方一致でないと使えない

列そのものが式に現れる形にする。

何に付けるか#

WHERE、JOIN、ORDER BY に頻出する列
選択性が高い列（値の種類が多い）
外部キー

性別のように値が 2 種類しかない列は、索引を使うより全件走査の方が速いことが多い。

参考文献#

PostgreSQL Documentation. Indexes. https://www.postgresql.org/docs/current/indexes.html
Markus Winand. SQL Performance Explained / Use The Index, Luke! https://use-the-index-luke.com/
Raghu Ramakrishnan, Johannes Gehrke. Database Management Systems, 3rd ed. McGraw-Hill, 2003.