B-tree、composite、covering indexはどのように機能しますか。また、leftmost-prefixルールとは何ですか。

Question

IT Interview Practice · Accepted Answer

InnoDBのインデックスは**B+tree**です。すべてのリーフが同じ深さにあり、リーフが連結されて高速な範囲スキャンを可能にする、平衡木です。検索はO(log n)で、巨大なテーブルでもわずかなページ読み取りで済みます。

## composite indexとleftmost prefix

composite index `(a, b, c)`は、まず`a`、次に`b`、次に`c`の順で行をソートします。使えるのは列の**leftmost prefix**（左端からの接頭）に対してだけです。すなわち`a`、`(a, b)`、`(a, b, c)`は使えますが、`b`単独や`(b, c)`は**使えません**。これらの列は`a`が固定されるまでソートされないためです。

```sql
CREATE INDEX idx_abc ON events (user_id, status, created_at);

-- USES the index (leftmost prefix, range on the last column)
SELECT * FROM events
WHERE user_id = 7 AND status = 'open' AND created_at > '2026-01-01';

-- Does NOT use it: skips the leftmost column
SELECT * FROM events WHERE status = 'open';
```

列は選択性の高いもの/等値条件を先に、範囲条件の列を最後に並べます。範囲（`>`、`BETWEEN`）に当たると、それより後ろの列はシーク（探索）には使えなくなります。

## covering index

インデックスが**クエリの読むすべての列**を含んでいれば、InnoDBはインデックスだけで応答でき、clustered indexへ戻る必要がありません。EXPLAINには`Using index`と表示されます。

```sql
CREATE INDEX idx_cover ON events (user_id, status, id);

EXPLAIN SELECT id FROM events WHERE user_id = 7 AND status = 'open';
-- Extra: Using index      <- covering, no clustered-index lookup
```

## なぜ重要なのか

compositeとcovering indexは、遅い複数条件クエリを1回のindex seekに変える手段です。列の順序を誤ること、あるいは2番目の列だけを条件とするクエリがインデックスを使うと期待することは、「存在する」インデックスがそれでも使われない最もよくある理由です。

composite indexとleftmost prefix

covering index

なぜ重要なのか

関連する質問