データベースインデックス入門 - B-treeの仕組みと、効くクエリ・効かないクエリ

「テーブルが大きくなったら急に遅くなった」——その多くはインデックスの不足や誤りが原因です。インデックスは魔法ではなく、仕組みを知れば「効く/効かない」が予測できるようになります。この記事では、PostgreSQL・MySQL 公式と Use The Index, Luke を一次ソースに、B-tree インデックスの基礎を整理します。

インデックスとは

インデックスは、テーブル本体とは別に持つ「探索を速くするデータ構造」です。本の巻末索引を思い出してください。全ページをめくる（＝フルスキャン）代わりに、索引から目的のページへ直行します。

• フルスキャン（Seq Scan）: 全行を順に読む。行数 N に比例（O(N)）
• インデックススキャン: 索引をたどって必要な行だけ取得（おおよそ O(log N)）

B-tree はなぜ速いのか

既定のインデックスは B-tree（B+tree）です（PostgreSQL・MySQL とも CREATE INDEX で型を省略するとこれ）。

• ソートされた木構造（ルート → ブランチ → リーフ）。各ノードに数百のエントリが入るため、100万件でも木の深さは10程度
• リーフ同士は双方向リンクで連結され、順序を保持する（物理配置がバラバラでも順序走査できる）

この「ソート済みの木」という性質から、等価・範囲・前方一致・並び替えに強い、という効き方が決まります。

いつ効くか

B-tree インデックスが効く代表例（PostgreSQL 公式より）。

• 等価・比較: = / < / <= / > / >= / BETWEEN / IN
• 前方一致 LIKE: LIKE 'foo%'（先頭が固定の場合）
• ORDER BY / GROUP BY: インデックスが既にソート済みなので並べ替えを省ける
• JOIN のキー列

ただし、選択性（selectivity）が高いほど効くのが原則。「絞り込んだ後に少数の行しか残らない」列ほど価値があります。逆に性別フラグのような低選択性の列は効きにくい（絞っても大量に残るため、オプティマイザはフルスキャンを選ぶ）。

複合インデックスと「左端プレフィックス」

複数列のインデックスは列の順序が決定的です。(last_name, first_name, birth_date) の場合：

CREATE INDEX idx_user ON users (last_name, first_name, birth_date);
 
-- 効く（左端から連続して使う）
WHERE last_name = 'Yamada';
WHERE last_name = 'Yamada' AND first_name = 'Taro';
WHERE last_name = 'Yamada' AND first_name > 'S';   -- 等値 + 範囲
 
-- 効きにくい（左端 last_name を飛ばしている）
WHERE first_name = 'Taro';
WHERE birth_date = '1990-01-01';

左端の列から連続して条件に使われて初めて効きます。よく使う条件の列を左に置くのが設計の勘所です。

カバリングインデックス（Index-Only Scan）

クエリが参照する列がすべてインデックスに含まれていれば、テーブル本体（ヒープ）を見ずに済みます（index-only scan）。PostgreSQL では INCLUDE で「検索キーにはしないが返す列」を足せます。

CREATE INDEX tab_x_y ON tab (x) INCLUDE (y);
-- これがヒープを読まずに済む
SELECT y FROM tab WHERE x = 'key';

効かない / 使われないケース

インデックスのコスト

「とりあえず全列にインデックス」は逆効果です。

• 書き込みが重くなる: INSERT / UPDATE / DELETE のたびにすべてのインデックスを更新する（ノード分割も発生）
• ストレージを消費する
• 大量データ投入時は、一旦インデックスを落として投入後に再作成すると速いことがある

使われないインデックスは負債。読み取りの利益と書き込みの負担のバランスで設計します。

クラスタ化インデックスの違い（MySQL / PostgreSQL）

• MySQL（InnoDB）: 主キーがクラスタ化インデックスで、リーフに行データ本体を持つ。セカンダリインデックスは主キー値を格納するため、主キーは短い連番（AUTO_INCREMENT 等）が有利
• PostgreSQL: テーブルはヒープで、すべてのインデックスはセカンダリ（別領域）。通常は「インデックス → ヒープ」の2段。index-only scan はVACUUM 状態に依存する

EXPLAIN で確かめる

推測せず、EXPLAIN（実測は EXPLAIN ANALYZE）で実行計画を見ます。Seq Scan か Index Scan かを確認するのが第一歩です。

-- 大量ヒット → Seq Scan（インデックス不利）
EXPLAIN SELECT * FROM orders WHERE status = 'shipped';
--  Seq Scan on orders  (cost=0.00..1500.00 rows=9500 width=120)
 
-- 高選択性 → Index Scan
EXPLAIN SELECT * FROM orders WHERE order_id = 12345;
--  Index Scan using orders_pkey on orders  (cost=0.29..8.31 rows=1 width=120)

(cost=起動..総コスト rows=推定行数 ...) を読み、想定どおりインデックスが使われているかを確認します。

まとめ

• インデックスは「探索を速くするソート済みの木（B-tree）」。等価・範囲・前方一致・ORDER BY・JOIN に効く
• 選択性が高い列ほど価値がある。低選択性・小テーブルでは使われない
• 複合インデックスは左端プレフィックス。よく使う列を左に
• 列に関数・前方ワイルドカード・型不一致はインデックスを殺す
• 書き込みコストとストレージとのトレードオフ。使われないインデックスは消す
• InnoDB は主キー＝クラスタ化、PostgreSQL はヒープ＋セカンダリ。最後は EXPLAIN で確認

インデックスは「貼れば速くなる」ものではなく、クエリの形に合わせて設計するものです。仕組みと EXPLAIN を押さえれば、「なぜ遅いのか」を自分で説明できるようになります。

参考リンク

• Indexes（PostgreSQL 公式）
• Index-Only Scans and Covering Indexes（PostgreSQL 公式）
• How MySQL Uses Indexes（MySQL 公式）
• InnoDB Clustered and Secondary Indexes（MySQL 公式）
• Use The Index, Luke
• REST API設計の基礎と冪等性（当ブログ）
• プログラミング学習におすすめの書籍12選（SQLアンチパターン等）（当ブログ）