お辛了！
前面幾篇系列文章已經寫過計算量與 race condition，這次要來談的是 資料庫索引（DB Index） 
就算知道「加上 index 會變快」，如果還能進一步說明 為什麼會變快／應該加在哪裡，就更有說服力，所以我把這部分整理了一下。
如果你有興趣，歡迎讀下去 
沒有 index 會怎樣？（全表掃描 = O(n)）
如果沒有 index，資料庫就不知道目標資料列在哪裡，因此只能從頭開始一筆一筆檢查所有資料列。這就是全表掃描（full table scan）。
SELECT * FROM users WHERE email = '[email protected]'
-- 沒有 index → 100 萬筆資料一筆一筆「是這個嗎？不是…」全部看過 = O(n) 💥資料量越大，速度就會線性變慢。以先前談過的計算量來說，就是 O(n)。
index 是「尋找方式的地圖」（O(log n)）
加上 index 之後，資料庫會另外保有一份針對該欄位更容易搜尋的索引。多數資料庫（MySQL／PostgreSQL）中，這個索引是 B-tree（B+ tree），也就是永遠保持排序的樹狀結構。
# migration
add_index :users, :emailSELECT * FROM users WHERE email = '[email protected]'
-- 有 index → 沿著 B-tree 一路縮小範圍 = O(log n) 🙆O(log n) =「每次都縮小一半」
O(log n) 的概念就是 「每查一次，候選範圍就少一半」。
我們來看看從 100 萬筆中找出目標那 1 筆時的差別。
【沒有 index】O(n) … 一筆一筆全部確認
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 會在每一層依照「比較大？比較小？」來選擇分支，並且把不相關的分支整個捨棄後往下走。
每往下一層，搜尋範圍就會減少一半（實際上常常還更多），所以才可以用很少的步驟找到目標。
正是因為「不看全部資料＝捨棄分支」，所以才是 O(log n)。這根本就是 資料庫版的二分搜尋。
為什麼不是 hash，而是 B-tree？
你可能會想：「如果要一次查到，那 hash（O(1)）不是更快嗎？」實際上 Redis 就是用 hash 做到 O(1)。
但資料庫選擇 B-tree，是因為它除了 = 之外，還常常要做其他型態的查詢。
WHERE age > 20 -- 範圍查詢（>, <, BETWEEN）
ORDER BY created_at -- 排序
WHERE name LIKE 'tan%' -- 前綴比對hash 會把值分散存放，因此沒有順序，也就只能用在 =（完全相等）查詢上。像上面這些查詢就無法全部支援。
B-tree 因為是排序好的，所以範圍查詢、排序、前綴比對都很擅長。也就是說，雖然速度稍慢一點（O(log n)），但它是功能更全面的選擇。
hashB-tree完全相等 =O(1) 最快O(log n)範圍查詢・排序・前綴比對不行**擅長B-tree 排序的依據不是「型別」，而是「順序（大小比較）」。整數依數值順序、日期依時間順序、字串依字典順序（逐字元比較）。
字串的排列方式會依 collation（排序規則／字元對照序）** 而改變，例如大小寫是否視為相同等。
該不該貼 index？何時該貼，何時不該貼？
這才是重點。「先全部都貼上」是錯的。index 也有成本，所以要針對真正有效的地方使用。
該貼的（有幫助的）
- 經常出現在 WHERE 的欄位（作為搜尋條件的欄位）
- 外鍵（例如
user_id）…… JOIN 或關聯篩選時很常用。Rails 在t.references :user（=belongs_to）時，預設就會加 index - ORDER BY / GROUP BY 會用到的欄位
- 需要唯一性的欄位（
add_index ..., unique: true）…… 可防止重複，也能加速查詢。這其實就是前一篇 race condition 的對策 - 基數（cardinality）高的欄位（也就是值的種類很多）…… 像
email,user_id之類。越能篩選，index 越有效
不該貼的 / 效果較差的
- 基數低的欄位（值的種類很少）…… 例如
boolean、status（只有幾種）、性別等。因為篩不太掉資料，資料庫甚至可能判斷「全掃描比較快」，而不使用 index - 更新非常頻繁的欄位…… index 在 INSERT／UPDATE／DELETE 時都要一起維護。貼太多會讓寫入變慢
- 很小的資料表…… 只有幾百筆時，全掃描也幾乎是瞬間完成，index 的效益不大
- 中間比對
LIKE '%xxx%'…… B-tree 對前綴比對（'xxx%'）有效，但對開頭是%的中間／後綴比對無效
index 不是免費的。 貼越多，會帶來 ① 寫入變慢 ② 儲存空間增加 ③ 查詢最佳化器更難判斷等成本。
原則就是只對 「常查詢 × 能有效縮小範圍」 的欄位加上 index。
複合 index（多欄位）就像電話簿
當你要把多個欄位一起建立索引時，順序非常重要。
add_index :users, [:last_name, :first_name]這就像電話簿一樣，會先依姓氏排序，再依名字排序。
所以它對 last_name 單獨搜尋有效，但對 first_name 單獨搜尋無效（＝最左前綴原則）。把常用的條件放在左邊是關鍵。
用 EXPLAIN 確認 index 有沒有真的生效
就算以為自己有加，實際上有沒有被用到，還是要用 EXPLAIN 來確認！
EXPLAIN SELECT * FROM users WHERE email = '[email protected]';- PostgreSQL：如果出現
Seq Scan（順序掃描／全掃描）就要注意；Index Scan則表示 index 有生效 - MySQL：
type: ALL（全掃描）是警訊；ref/const代表 index 有被用到
也要注意 JOIN 的 Nested Loop 和 loops
做 JOIN 時，常常會出現 Nested Loop（外層每一筆資料，都去反覆查內層）這種做法。這裡會因為 index 有沒有生效而有天壤之別。
- 內層的 join 欄位有 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)），有 index 時則可透過 B-tree 快速縮小範圍（O(log n)）
- 之所以不是 hash，而是 B-tree，是因為它是能處理範圍、排序、前綴比對的萬用型
- 只在常查詢 × 能有效縮小範圍的欄位加 index。對於基數低、更新頻繁、很小的資料表要特別小心
- 是否真的生效，要靠
EXPLAIN來確認
而且接下來，能看出 AI 產生的查詢或 migration 裡有沒有潛藏「沒用的 index」或「全掃描」問題，也是工程師的工作之一。AI 可以幫你寫出可執行的 SQL，但不一定會提醒你「這個查詢在 100 萬筆資料時會變成全掃描」。建議你養成看 EXPLAIN 的習慣！
1) --- 會變成分隔線（上一行必須是空白）
2) # 會變成一級標題
3) ## 會變成二級標題
4) ### 會變成三級標題
5) **粗體文字**會顯示粗體文字
6) ```當第一行與最後一行會顯示程式碼
7) 請搜尋 Markdown 語法，了解各種格式
