インデックスはなぜ速いのか

読了目安約3分

インデックスの正体である B+木を競プロの二分探索から理解し、EXPLAIN で実行計画を確かめます。

この章の目次

1000 万行から 1 行を探す

posts に 1000 万行あるとします。

SQL
SELECT * FROM posts WHERE user_id = 42;

何も手を打たなければ、MySQL が 1000 万行を全部読んで 1 行ずつ確かめるフルスキャン（全表スキャン）になります。 O(N) の線形探索が、リクエストのたびに実行されます。

ソートしてあれば二分探索できる

競プロなら、ソート済み配列に二分探索で O(log N)、1000 万件でも 24 回程度の比較です。しかし INSERT や DELETE は絶えず起き、ソート済み配列では挿入が後ろを全部ずらす O(N) です。この二分探索を更新に強くしたデータ構造が B+木です。

値をソートされた状態で木に持ち、探すときは根から枝を選んで降りるだけ。
挿入してもノードを局所的に分割するだけで、配列のような大移動が起きない。
1 つのノードにキーを多数詰め込むので木の高さは数段で済み、数千万行でも根から数回たどれば目的の行に着く。

インデックスとは、指定した列の値から行を引けるように、テーブルとは別に DB が維持するこの探索用データ構造です（本の索引と同じ役割）。主キーには自動で作られるので、問題は user_id のような主キー以外の列です。

EXPLAIN で見比べる

EXPLAIN をクエリの前に付けると、実行の代わりに「どう探すつもりか」という実行計画が返ります。 /sql/04-join/ で作った 6 行の posts で試します（\G は結果を縦表示にする記法です）。

SQL
EXPLAIN SELECT * FROM posts WHERE user_id = 1\G

テキスト
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: posts
         type: ALL
possible_keys: NULL
          key: NULL
         rows: 6
        Extra: Using where

見るのは type と rows です（他の項目は省略）。

type: ALL：フルスキャンの印。
rows：読む見込みの行数。前章で INSERT を試した分があれば、その分だけ増える。

構文 CREATE INDEX 名前 ON テーブル (列) で user_id にインデックスを張り、もう一度 EXPLAIN します。

SQL
CREATE INDEX idx_posts_user_id ON posts (user_id);

テキスト
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: posts
         type: ref
possible_keys: idx_posts_user_id
          key: idx_posts_user_id
         rows: 3
        Extra: NULL

type が ref（一致する行だけを読む探し方）に変わり、rows も 3 行になりました。遅いクエリにまず EXPLAIN を付けて type: ALL を探すのが最初の一手です。

複合インデックスは左端から使われる

複数の列に張るインデックスを複合インデックスと呼びます。

SQL
CREATE INDEX idx_posts_user_created ON posts (user_id, created_at);

中身は「user_id でソートし、同じ user_id の中を created_at でソートした」並びです。姓でソートし、同姓の中を名でソートした名簿と同じ構造で、ここから使える条件が決まります。

WHERE user_id = 1 AND created_at >= '2026-03-06'：効く。姓で絞ってから名で絞る引き方そのもの。
WHERE user_id = 1：効く。左端の列だけの検索は、先頭部分の並びをそのまま使える。
WHERE created_at >= '2026-03-06'：効かない。名だけを頼りに姓順の名簿は引けないのと同じで、結局全部見るしかない。
WHERE user_id = 1 ORDER BY created_at DESC（あるユーザーの投稿を新しい順に）：効く。一致する行がすでに created_at 順に並んでいる。

列の順番に意味があり、(user_id, created_at) と (created_at, user_id) は別物です。

張るほど速くなるわけではない

インデックスは読み取りを速くする代わりに、書き込みを遅くします。 INSERT のたびに全インデックスの B+木を更新するからです。

だから、インデックスは実際に発行される遅いクエリから逆算して張ります。実践は /isucon/04-index-tuning/ でやります。