中身はだいたい B+Tree#

MySQL（InnoDB）や PostgreSQL の標準的なインデックスは、B+Tree という木構造で実装されています。ルートから葉までの段数が少ないため、件数が億単位になっても、数回のディスク／メモリアクセスで該当行にたどり着けます。

全文検索向けには転置インデックス、地理情報向けには R-Tree、メモリ上の高速参照には Hash インデックスなど、用途に応じて別の構造もあります。

効くケース#

• WHERE 句に出てくるカラム
• JOIN で結合キーになるカラム
• ORDER BY / GROUP BY のキーになるカラム
• 一意性制約（PRIMARY KEY、UNIQUE）

効かない／逆効果なケース#

• カーディナリティが低い：例えば「性別」のように2値しかない列に貼っても、絞り込みが弱い。
• 関数を噛ませる：WHERE DATE(created_at) = ... のように関数で包むと、B+Tree が使えない。
• 左端一致しない複合インデックス：(a, b, c) のインデックスに対して、WHERE b = ? だけで引いてもインデックスは使われない。
• 書き込みが多い列に貼りすぎる：INSERT/UPDATE/DELETE のたびに索引も更新する必要があるため、書き込み性能が落ちる。

設計の勘所#

• クエリの形に合わせて貼る：先にクエリ、後からインデックス。アプリケーションが投げる SELECT の形を見て、必要なものだけ貼る。
• EXPLAIN で確認する：実際に使われているか、フルスキャンしていないかを必ず確かめる。
• 複合インデックスの順序：等価比較で絞り込む列を左、レンジ検索の列を右に置くと効きやすい。
• 削れるかも検討する：使われていないインデックスは、書き込みを遅くするだけのコストになる。

「とりあえず貼る」は事故の元。投げたいクエリから逆算して、最小限のインデックスで最大の効果を狙うのが理想形です。