インデックスは、値と行の保存先を整理した検索用のデータ構造です。B+木を使うと、多数の行から少数のページを読んで目的の行を探せます。
B+木検索とテーブル全件走査の比較
1. 検索値と方法を選択
範囲~
今回読むページ読込済みページ一致した値
上の木はid列のインデックス、下の5枠は実際の行が入るテーブルページです。テーブルの行は整列していません。
検索O(log n)
範囲検索リーフのリンクをたどる
100万行の高さ約3～4
代償書込みコスト増加
B+木の3つの特徴
各ノードは整列済みキーと子ポインタを持ち、1ページで多数のキーを扱うため木が浅くなります。行の保存先はリーフにあり、リーフ同士のリンクをたどれば範囲検索できます。
インデックスが常に速いとは限りません
一致する行の取得に多数のテーブルページを読むなら、全件走査の方が速い場合があります。範囲を広げて読込数を比較してください。オプティマイザはこうしたコストを見積もります。
インデックスが効きにくい条件
列に関数や演算を適用すると（WHERE YEAR(joined_at) = 2024, WHERE price * 2 > 100）、通常の列インデックスを検索に使えない場合があります。 LIKE '%term'のような先頭ワイルドカードも同様です。(a,b)の複合インデックスはaから整列するため、bだけでは効率的に検索できないことがあります。インデックスが増えるほど更新時の保守コストも増えます。