お疲れ様です！
シリーズで計算量やレースコンディションを書いてきましたが、今回は DBインデックス です
「indexを貼ると速くなる」は知っていても、なぜ速いのか／どこに貼るべきかまで説明できると強いので、そこをまとめてみました。
興味ある方は読んでいただけると嬉しいです

indexがないとどうなる？（フルスキャン = O(n)）

indexが無いと、DBは目的の行がどこにあるか分からないので、全行を先頭から1つずつ確認します。これがフルテーブルスキャンです。

SELECT * FROM users WHERE email = 'a@example.com'
-- index なし → 100万行を1行ずつ「これ？違う…」と全部見る = O(n) 💥

件数が増えるほど線形に遅くなります。前回までの計算量でいう O(n) です。

indexは「探し方の地図」（O(log n)）

indexを貼ると、DBはその列専用の探しやすい索引を別に持ちます。多くのDB（MySQL/PostgreSQL）では、この索引が B-tree（B+tree） という常にソートされた木です。

# マイグレーション
add_index :users, :email

SELECT * FROM users WHERE email = 'a@example.com'
-- index あり → B-treeをたどって一気に絞る = O(log n) 🙆

O(log n) =「毎回、半分に絞る」

O(log n) のイメージは 「1回調べるごとに、候補が半分になる」 です。
100万件から目的の1件を探す様子を比べてみます。

【index なし】O(n) … 1件ずつ全部確認
 1 → 2 → 3 → 4 → ... → 1,000,000     最悪 100万回 💥

【index あり】O(log n) … 毎回「半分」に絞る
 1,000,000 件
    ↓ 半分
   500,000
    ↓ 半分
   250,000
    ↓ 半分
   125,000
    ↓ 半分の半分の半分…
      … 
      1 件   ← たった約20回で到達！🙆

「半分 → その半分 → さらに半分…」を繰り返すと、100万件でもたった約20回（log₂ 1,000,000 ≈ 20）で1件まで絞れます。これが O(log n) の正体です。

件数を増やすと、差はさらに劇的になります。

件数	index なし（O(n)）	index あり（O(log n)）
1,000	最悪 1,000 回	約 10 回
1,000,000	最悪 100万回	約 20 回
1,000,000,000	最悪 10億回	約 30 回

件数が 1000倍→100万倍→10億倍 と爆発しても、O(log n)は 10→20→30 としか増えません。
「データが増えても、ほぼ増えない」——これがindexの威力です。

B-treeは各階層で「大きい？小さい？」で枝を選び、関係ない枝を丸ごと捨てて降りていきます。
1段降りるごとに探す範囲が半分（実際はもっと）に減るので、上のように少ないステップで到達します。
「全部見ない＝枝を捨てる」からこそ O(log n)。まさに 二分探索のDB版 です。

なぜハッシュじゃなくB-tree？

「一発で引くならハッシュ（O(1)）の方が速いのでは？」と思いますよね。実際 Redis はハッシュで O(1) です。
でもDBが B-treeを選ぶのは、= 以外の検索も当たり前に使うからです。

WHERE age > 20               -- 範囲（>, <, BETWEEN）
ORDER BY created_at          -- 並び替え
WHERE name LIKE 'tan%'       -- 前方一致

ハッシュは値を散らばして置くので 「順番」が無く、=（完全一致）専用。上のような検索が全部できません。
B-treeはソート済みなので、範囲も並び替えも前方一致も得意。多少遅くても（O(log n)）、何でもできる方を選んでいるわけです。

	ハッシュ	B-tree
完全一致 `=`	O(1) 最速	O(log n)
範囲・並び替え・前方一致	不可	得意

B-treeは「型」ではなく「順序（大小比較）」で並べます。整数＝数値順、日付＝時系列、文字列＝辞書順（1文字ずつ照合）。
文字列の並びは collation（照合順序） 次第で、大文字小文字の扱いなどが変わります。

index、貼るべき？貼らないべき？

ここが本題。「とりあえず全部に貼る」は間違いです。indexにはコストもあるので、効く場所に絞ります。

貼るべき（効く）

WHEREで頻繁に検索する列（検索条件になる列）
外部キー（user_id など）… JOINや関連の絞り込みで多用。Railsは t.references :user（= belongs_to）でデフォルトでindexが付きます
ORDER BY / GROUP BY で使う列
一意にしたい列（add_index ..., unique: true）… 重複防止＋検索高速化。前回のレースコンディション対策そのもの
カーディナリティが高い列（＝値の種類が多い列）… email, user_id など。絞り込めるほどindexは効く

貼らないべき / 効きにくい

カーディナリティが低い列（値の種類が少ない）… boolean, status(数種), 性別など。絞り込めないので、DBが「全走査した方が速い」と判断しindexを使わないことも
更新が非常に多い列… indexは書き込み（INSERT/UPDATE/DELETE）のたびに更新が必要。貼りすぎると書き込みが遅くなる
小さいテーブル… 数百行ならフルスキャンでも一瞬。indexの旨味が薄い
中間一致 LIKE '%xxx%'… B-treeは前方一致('xxx%')には効くが、先頭が%の中間・後方一致には効かない

indexはタダではありません。 貼るほど ①書き込みが遅くなる ②ストレージが増える ③オプティマイザが迷う、というコストがあります。
「よく検索する × 絞り込める列」に絞って貼るのが鉄則です。

複合index（複数列）は「電話帳」

複数列をまとめて貼るときは、順序が命です。

add_index :users, [:last_name, :first_name]

これは電話帳と同じで「まず姓で並べ、姓が同じなら名で並べる」。
なので last_name 単体の検索には効きますが、first_name 単体には効きません（＝左端一致の原則）。よく使う条件を左に置くのがコツです。

EXPLAIN で「効いているか」を確認する

貼ったつもりでも、実際に使われているかは EXPLAIN で確認しましょう！

EXPLAIN SELECT * FROM users WHERE email = 'a@example.com';

PostgreSQL：Seq Scan（全走査）が出たら要注意。Index Scan ならindexが効いている
MySQL：type: ALL（全走査）は危険信号。ref / const ならindexが効いている

JOINの `Nested Loop` と `loops` にも注意

JOINをすると Nested Loop（外側の行1件ごとに、内側を繰り返し引く方式）がよく出ます。ここが index の効き目で天と地に分かれます。

内側の結合列にindexがある → 外側の行ごとに O(log n) で引ける ✅
内側にindexが無い → 外側の行ごとに内側を全走査 → 「外側の行数 × 内側の全件」= O(n×m) で激重 💥

EXPLAIN ANALYZE を使うと、各ノードに loops=N（実際に何回実行されたか） が出ます。

Nested Loop
  -> Seq Scan on users        (rows=1000)
  -> Seq Scan on orders  (loops=1000)   ← 内側が1000回フルスキャン！💥

loops が大きいノードが Seq Scan になっていたら、そこに index が足りていないサインです。

チェックの流れ：遅いクエリを見つけたら、まず EXPLAIN（できれば EXPLAIN ANALYZE）。
① フルスキャン(Seq Scan/type: ALL)していないか、② Nested Loop の内側で loops が多い割にindexが効いていないか、を見ることが多いです！

最後に

indexが無いとフルスキャン（O(n)）、あるとB-treeで一気に絞る（O(log n)）
ハッシュじゃなくB-treeなのは、範囲・並び・前方一致もこなす万能型だから
「よく検索する × 絞り込める列」に貼る。カーディナリティが低い列・更新が多い列・小さいテーブルは慎重に
効いているかは EXPLAIN で確認

そしてこれからは、AIが出したクエリやマイグレーションに"効かないindex"や"フルスキャン"が潜んでいないか見抜けるのもエンジニアの役目 です。AIは動くSQLは書いてくれますが、「その検索、100万件でフルスキャンになりますよ」までは言ってくれないことがあります。ぜひ EXPLAIN を覗く習慣を持ってみてください！