クラスタ化インデックスと非クラスタ化インデックスの内部差

二つの索引設計を分ける一点

インデックスの内部設計を分ける本質的な問いは一つです。「行データ本体を、どこに、どの順序で置くか」。この答えの違いが、クラスタ化インデックスと非クラスタ化インデックスを分けます。両者とも探索構造は B+Tree インデックス ですが、葉ノードに何が入るかが決定的に異なります。

クラスタ化インデックス：主キー＝行そのもの

InnoDB では、表は必ず主キー順に整列された 1本のクラスタ化インデックス として格納されます。重要なのは、B+Tree の葉ノードが「行への参照」ではなく 行データ本体そのもの を保持する点です。WHERE id = 42 のような主キー検索は、ルートから葉へ B+Tree を一度下りきれば、その葉ページ上に全カラムが揃っています。追加の参照は一切要りません。

クラスタ化インデックス（主キー id）
  内部ノード: 区切りキー（id の境界値）と子ポインタ
  葉ノード  : [id, col_a, col_b, ... ] ← 行全体が主キー順に並ぶ

副作用として、主キーの選び方が物理 I/O 特性を直接左右します。連番（AUTO_INCREMENT）なら挿入は常に右端の葉へ集中し、ページ分割が局所化してキャッシュも効きます。ランダムな UUID v4 を主キーにすると挿入位置が木全体に散らばり、分割多発とキャッシュミスを招きます。これは主キーが論理キーであると同時に 行の物理配置そのもの を決めているからです。

非クラスタ化（ヒープ）方式：行は順不同、索引は住所だけ

対照的なのが、PostgreSQL・Oracle・SQL Server（既定）などが採る ヒープ方式 です。行データは整列されない ヒープ に挿入順で置かれ、インデックスは独立した B+Tree として別に存在します。索引の葉が持つのはカラム値ではなく RID（Row Identifier）、すなわち「何番ページの何番スロット」という物理アドレスです（PostgreSQL では TID、(ページ番号, タプル番号))。

ヒープ方式のセカンダリインデックス
  葉ノード: [key, RID] ← RID = ヒープ上の物理位置（ページ+スロット）

検索: 索引 B+Tree を下る → 葉で RID 取得 → RID でヒープを1回ランダム参照

つまり索引葉に着いた後、RID を辿ってヒープ本体を読む一回の追加参照 が常に発生します。この追加参照を「ヒープフェッチ」「bookmark lookup」などと呼びます。索引が key 順でも、対応する RID はヒープ上に散在するため、多数行を取り出すと ランダム I/O の連発 になります。

InnoDB のセカンダリインデックス：二段参照の正体

ここが本題です。InnoDB のセカンダリ（非主キー）インデックスは、ヒープ方式とも違う固有の構造を持ちます。葉が指すのは RID（物理アドレス）ではなく 主キー値 です。

InnoDB セカンダリインデックス（例: 列 email の索引）
  葉ノード: [email, 主キー値(id)]   ← RID ではなく主キーを持つ

検索 SELECT * FROM users WHERE email = 'x':
  (1) email 索引の B+Tree を下る → 葉で id を取得
  (2) 取得した id でクラスタ化インデックスの B+Tree を下る → 葉で行本体

行本体に届くまでに B+Tree を二本下る ことになります。これがセカンダリインデックスの二段参照コストです。MySQL のドキュメントではこの主キー再探索を「covering index でない限り発生する二度目の検索」として説明します。1件なら誤差ですが、email LIKE 'a%' で数万行が該当すれば、その一件ごとに主キー B+Tree を下り直すため、コストは件数に比例して効いてきます。

カバリングインデックス：二段目を消す

二段参照を回避する原理的な手段が カバリングインデックス です。クエリが必要とするカラムをすべて索引自身が含んでいれば、葉で答えが完結し、行本体（クラスタ化インデックス）への二段目の参照を 完全に省略 できます。

-- email 索引が (email) のみだと、name 取得で主キー再探索が必要
SELECT name FROM users WHERE email = 'x@example.com';

-- (email, name) の複合索引にすれば索引葉だけで name まで揃い、
-- クラスタ化インデックスを下らずに済む（covering / Using index）
CREATE INDEX idx_email_name ON users (email, name);

実行計画で Using index（MySQL）や Index Only Scan（PostgreSQL）と出れば、二段目が消えた合図です。必要カラムを索引に含める設計は、二段参照という構造コストを正面から打ち消す最も直接的な最適化です。索引が効く条件の全体像は クエリ最適化 を参照してください。

どこで I/O が決まるか

最終的に、両方式の性能差は 「葉に着いた後にもう一回ランダム参照するか」 に集約されます。

検索パターン	クラスタ化（主キー直）	セカンダリ / ヒープ方式
主キー等値・範囲	B+Tree 一本で完結。範囲は葉リンクで順次読み	（対象外）
非キー列での検索	全件走査になりがち	索引一本目で位置特定
行本体の取得	追加参照ゼロ	二段目の参照が1行ごとに発生
該当多数	順次 I/O 中心	ランダム I/O が件数分積み上がる

この二段目のランダム参照こそが、セカンダリインデックスが「効いているのに思ったより速くない」主因です。なお該当行が表の大半に及ぶときは、オプティマイザがあえて索引を捨てて全件走査を選びます。二段ランダム参照の総コストが、ヒープ／クラスタを順番に舐めるコストを上回るからです。

行配置とアクセス特性をさらに突き詰める話題として、ページをメモリに留める仕組みは バッファプールとページ置換、分析系で列単位に置き換える発想は 行指向と列指向ストレージ を参照してください。