お疲れ様です！
シリーズで計算量やレースコンディションを書いてきましたが、今回は 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 を覗く習慣を持ってみてください！