Index 與 B+Tree:從磁碟頁面到複合索引、索引失效與 keyset 分頁
System Design 系列 Part 3-2|上一篇:SQL vs NoSQL|下一篇:B-Tree vs LSM-Tree|系列地圖
情境與問題
會員中心的「我的訂單」API 背後是一張 5,000 萬筆的 purchase_order 表,每列約 200 bytes,資料本身約 10 GB。上線後陸續出現:
- 查某位會員最近 20 筆訂單要 8 秒
- 加了
member_id的索引後變快了,但「某位會員已付款的訂單,依時間排序」還是慢 - 後台的
WHERE DATE(created_at) = '2026-11-11'不管怎麼加索引都沒用 - 客服用手機號碼查會員,
WHERE phone = 0912345678每次都掃整張表 - 為了加速,有人一口氣加了 12 個索引,結果大促時寫入變慢、replica 延遲飆高
- 第 5,000 頁的分頁要 3 秒
六個問題都和索引有關,但原因各不相同。要能判斷,得先知道索引在磁碟上長什麼樣子。
最簡單的做法與它的極限
沒有索引時,資料庫只能全表掃描:讀完 5,000 萬列,逐一檢查條件。成本和資料量成正比,資料多 10 倍就慢 10 倍;同時有 10 個這種查詢,就是 10 倍的 I/O。
資料若依某個欄位排好序,就能用二分搜尋:log₂(5,000 萬) ≈ 26 次比較。但排序好的陣列插入很貴,而且只能依一種順序排。改用二元搜尋樹可以兼顧插入,但樹高約 26 層,如果每一層都在磁碟上的不同位置,一次查詢就是 26 次隨機讀取。磁碟(就算是 SSD)的隨機讀取比記憶體慢上百倍以上,26 次太多了。
資料庫需要的是一種又矮又胖的樹:每個節點剛好是一個磁碟頁面,一次讀取就能拿到上千個分支。這就是 B+Tree。
核心機制
B+Tree:為磁碟頁面設計的樹
flowchart TD
R["根節點(一個 16 KB 頁面)
約 1,170 個分支"] --> I1[內部節點]
R --> I2[內部節點]
R --> I3["…"]
I1 --> L1["葉節點:id 1–76 的整列資料"]
I1 --> L2["葉節點:id 77–152"]
I2 --> L3["葉節點:…"]
L1 -. 雙向串列 .-> L2
L2 -. 雙向串列 .-> L3
- 每個節點就是一個頁面:InnoDB 預設 16 KB。內部節點只存「鍵 + 指向子節點的指標」,所以一頁能放上千個分支
- 資料只放在葉節點,而且葉節點之間用串列相連。範圍查詢(
BETWEEN、ORDER BY ... LIMIT)找到起點後,沿著串列往下讀就好
一棵 B+Tree 能裝多少資料?假設主鍵是 BIGINT,內部節點每個分支約 14 bytes:
計算程式(java BPlusTreeCapacity.java)
| |
| |
(忽略了頁面標頭等額外開銷,是量級估算。)
三層就能裝下約一億列。而且根節點和內部節點加起來只有一千多個頁面(約 20 MB),幾乎一定常駐在 InnoDB 的 buffer pool 裡。所以用主鍵查一筆資料,實際的磁碟讀取通常只有最後那一個葉節點,甚至連它也在記憶體裡。這就是「用主鍵查詢很快」的物理原因。
從表中也看得出:每列越寬,同樣的樹高能裝的列數越少。把大欄位(長文字、JSON)拆到另一張表,能讓主表的樹更矮、每頁裝更多列。
聚簇索引與次要索引
InnoDB 的整張表就是一棵以主鍵排序的 B+Tree(聚簇索引),葉節點存的是整列資料。其他索引(次要索引)是另外的 B+Tree,葉節點存的是「索引欄位 + 主鍵值」,而不是資料本身:
flowchart LR
Q["WHERE member_id = 42"] --> S["次要索引 (member_id)
葉節點:member_id, id"]
S -- "拿到 id = 918273" --> P["主鍵索引(聚簇)
葉節點:整列資料"]
P --> Row[完整的一列]
所以透過次要索引查詢,要走兩棵樹:先在次要索引找到主鍵,再回主鍵索引拿整列(俗稱「回表」)。如果查詢需要的欄位全部都在次要索引裡,就不必回表,這叫覆蓋索引,EXPLAIN 的 Extra 欄會顯示 Using index。
這個結構帶來三個重要的推論:
- 主鍵越寬,所有索引都越大:每個次要索引的每一筆都夾帶主鍵。用 36 字元的 UUID 字串當主鍵,等於每個索引的每一筆都多了 36 bytes
- 主鍵的順序就是資料的實體順序:遞增主鍵的插入永遠在樹的最右邊,頁面依序填滿;隨機的 UUIDv4 則會插在樹的任意位置,造成大量頁面分裂與隨機 I/O。分散式環境下如何產生「大致遞增」的 ID,見 分散式 ID 篇
- 次要索引的最後其實隱含了主鍵:
INDEX (member_id, created_at)在 InnoDB 裡等於(member_id, created_at, id)。後面的 keyset 分頁正好用得上
複合索引與最左前綴
複合索引 (member_id, status, created_at) 的排序方式就像電話簿:先依第一欄排,第一欄相同再依第二欄排,以此類推。所以只有「從最左邊開始、連續的欄位」能用來定位範圍。
用 TreeSet 模擬這個索引:2,000 位會員、每人 100 筆訂單、共 20 萬筆,比較不同條件需要掃描的筆數:
模擬程式(java LeftmostPrefixDemo.java)
| |
| |
- 前三個查詢都只掃描剛好符合的筆數:條件從最左欄開始連續,範圍一路縮小
- 第四個跳過了中間的
status:只有member_id能定位,created_at只能逐筆過濾,掃 100 筆才找到 18 筆。MySQL 的 Index Condition Pushdown(Using index condition)會在索引層先過濾,省下回表,但掃描範圍不變 - 第五個跳過了最左欄:無法定位,只能整份索引看一遍。MySQL 8.0.13 起的 skip scan 在第一欄種類很少時是例外,但不能依賴
由此得出設計複合索引的規則:
- 等值條件的欄位放前面,範圍條件的欄位放最後:範圍條件之後的欄位無法再用於定位
ORDER BY跟著索引順序:情境 2 的「已付款訂單依時間排序」,用(member_id, status, created_at)時資料本身就已排好序,不需要額外排序(EXPLAIN不再出現Using filesort),加上LIMIT 20讀 20 筆就停- 「選擇性高的欄位放第一個」不是鐵律:真正決定順序的是查詢模式。一個所有查詢都會帶的等值條件,即使選擇性低,放在第一個也合理
優化器不一定會用你的索引
MySQL 的優化器依成本做決定。如果條件符合的列很多(例如 status = 'DONE' 佔了 80%),每一筆都要回表的成本會高過直接全表掃描,優化器就會選全表掃描。這是正確的行為,不是 bug。
用 EXPLAIN 確認執行計畫,重點看這幾欄:
| 欄位 | 看什麼 |
|---|---|
type | 由好到差大致是 const、eq_ref、ref、range、index(掃整份索引)、ALL(全表掃描) |
key | 實際用了哪個索引;NULL 代表沒用 |
rows | 預估要檢查的列數 |
Extra | Using index(覆蓋索引)、Using index condition(ICP)、Using filesort(額外排序)、Using temporary(暫存表) |
EXPLAIN 是預估值。MySQL 8.0.18 起的 EXPLAIN ANALYZE 會實際執行查詢,列出每一步實際花的時間和列數。統計資訊過舊時,預估會失準,可以用 ANALYZE TABLE 更新。
讓索引失效的寫法
| 寫法 | 為什麼用不到索引 | 改寫 |
|---|---|---|
WHERE DATE(created_at) = '2026-11-11' | 欄位被函式包住,索引裡存的是原始值 | created_at >= '2026-11-11' AND created_at < '2026-11-12' |
WHERE phone = 0912345678(phone 是 VARCHAR) | 字串和數字比較時,MySQL 會把每一列的字串轉成數字再比 | 加上引號;Java 端用 String 綁定參數 |
WHERE name LIKE '%陳' | 開頭是萬用字元,無法定位起點 | LIKE '陳%' 可以用索引;任意位置搜尋要用全文索引(見 全文搜尋篇) |
WHERE created_at + INTERVAL 1 DAY > NOW() | 欄位參與運算 | 把運算移到另一邊:created_at > NOW() - INTERVAL 1 DAY |
WHERE a = ? OR b = ? | 一個索引無法同時依兩個欄位定位 | 兩欄各自有索引時可能用 index merge;不行就改成 UNION |
| JOIN 兩邊欄位的字元集或 collation 不同 | 比較前要逐列轉換 | 統一欄位定義 |
情境 3、4 就是前兩種。最後一種常出現在新舊系統整合時,舊表是 utf8、新表是 utf8mb4。
索引的代價
每個索引都是一棵要維護的 B+Tree:
- 寫入放大:每次
INSERT,主鍵索引和每一個次要索引都要各寫一次。12 個次要索引,就是每筆插入要改 13 棵樹;UPDATE改到索引欄位,該索引就要刪一筆、插一筆 - 空間:索引總大小超過資料本身很常見,而且它們也要搶 buffer pool 的記憶體
- replica 延遲:主庫寫入變重,replica 重放的工作也跟著變重
- 唯一索引比較貴:唯一索引每次寫入都要先把頁面讀出來檢查是否重複。非唯一的次要索引在 MySQL 8.0 可以靠 change buffer 先暫存修改、稍後合併;但 MySQL 8.4 起
innodb_change_buffering預設改為none,所有次要索引的修改都要即時讀到對應頁面
所以情境 5 的 12 個索引不是免費的。找出沒在用的索引:MySQL 的 sys.schema_unused_indexes 會列出自啟動以來沒被使用過的索引;要刪除前,可以先用 MySQL 8.0 的 invisible index(ALTER TABLE ... ALTER INDEX ... INVISIBLE)讓優化器看不到它,觀察一段時間沒問題再刪。
深分頁:OFFSET 的代價
LIMIT 20 OFFSET 100000 的意思是「找出前 100,020 筆,丟掉前 100,000 筆」。資料庫沒辦法直接跳到第 100,001 筆,只能一筆一筆數過去(而且可能每筆都回表)。頁數越深越慢,就是情境 6。
Keyset 分頁改用「上一頁最後一筆的位置」當起點:
| |
不管第幾頁,都是從索引的某個位置往下讀 20 筆。id 是為了讓排序唯一:同一毫秒可能有兩筆訂單,只用 created_at 會漏掉或重複。前面說過,INDEX (member_id, created_at) 在 InnoDB 裡本來就隱含了 id,所以這個查詢完全走索引。
方案比較
分頁方式
| OFFSET 分頁 | Keyset 分頁 | |
|---|---|---|
| 深頁效能 | 越深越慢 | 每頁都一樣 |
| 跳到任意頁 | 可以 | 不行,只能上一頁、下一頁 |
| 翻頁時有新資料插入 | 可能重複或漏掉 | 不受影響 |
| 排序要求 | 無 | 排序欄位組合必須唯一(加上主鍵) |
| 適合 | 後台管理、資料量小、需要頁碼 | 無限捲動、API、匯出大量資料 |
Spring Data JPA 的 Pageable 分頁另見 Spring Data JPA 分頁篇。
索引類型
| 類型 | 適合 | MySQL 中的形式 |
|---|---|---|
| B+Tree | 等值、範圍、排序、前綴比對 | InnoDB 預設 |
| Hash | 只有等值查詢 | InnoDB 的 adaptive hash index 會自動為熱點建立,不能手動指定 |
| 全文索引 | 文字中任意位置的關鍵字 | FULLTEXT(見 全文搜尋篇) |
| 空間索引 | 地理位置範圍 | SPATIAL(R-Tree,見 Geohash 篇) |
| Functional / Multi-valued | 運算式結果、JSON 陣列 | 8.0.13+ / 8.0.17+(見 SQL vs NoSQL 篇) |
Java 落地
1. 用 migration 管理索引
| |
InnoDB 的 online DDL 可以在建索引的同時繼續接受讀寫,明確寫出 ALGORITHM = INPLACE, LOCK = NONE,萬一這個操作不支援線上執行,會直接報錯,而不是默默鎖表。JPA 的 @Table(indexes = ...) 只在讓 Hibernate 產生 schema 時才有作用,正式環境的索引應該由 Flyway 這類 migration 工具管理,@Index 頂多當作文件:
| |
2. Keyset 分頁
| |
回傳 List 而不是 Page,Spring Data 就只套用 LIMIT,不會多跑一次 COUNT(*)(在大表上,COUNT(*) 本身就可能很慢)。
游標要交給前端,下一頁時帶回來:
| |
| |
游標實際的樣子:
| |
Spring Data 3.1 起也有內建的 Scroll API(Window、ScrollPosition.keyset()),用 derived query 時會自動產生同樣的條件,並在排序最後補上主鍵確保唯一。
3. 衍生查詢的 IgnoreCase 陷阱
Spring Data 的 findByEmailIgnoreCase 會產生 UPPER(email) = UPPER(?),欄位被函式包住,email 的索引就用不到了。MySQL 的預設 collation(例如 utf8mb4_0900_ai_ci)本來就不分大小寫,直接用 findByEmail 即可。
踩坑與 Gotchas
- 索引越多越好:每個索引都讓寫入變慢、佔記憶體、加重 replica 負擔
- 低選擇性欄位單獨建索引:
status只有 5 種值,單獨的索引幾乎不會被選用 - 重複的索引:已經有
(a, b),再建(a)就是多餘的 - 測試環境資料太少:幾千筆資料時優化器常選全表掃描,正式環境的執行計畫可能完全不同。關鍵查詢要用接近正式環境的資料量看
EXPLAIN - 用 UUID 字串當主鍵:每個次要索引都變大,隨機插入造成頁面分裂
- 大表直接加索引:就算是 online DDL,replica 也要重做一次同樣的建索引,期間後面的變更都卡住,造成和建索引時間一樣長的延遲。大表改用 gh-ost 這類工具,或安排在離峰時段
- 深分頁用 OFFSET:越後面越慢,而且在大表上
COUNT(*)本身就很貴 - 衍生查詢用了
IgnoreCase:欄位被UPPER()包住,索引失效 - 只看
rows,不看實際執行:預估可能失準,用EXPLAIN ANALYZE或 slow query log 的Rows_examined確認
資安相關
- 排序欄位直接拼進 SQL:
ORDER BY不能用參數綁定,把 client 送來的欄位名稱直接接進 SQL,就是 SQL injection。Spring Data 的Sort會檢查屬性名稱是否存在於 domain model,但JpaSort.unsafe(...)會關掉這層保護。最穩的做法是只接受代號,對應到預先定義好的排序:
| |
- 任意篩選條件就是廉價的 DoS:允許 client 對任意欄位做
LIKE '%...%',每個請求都是一次全表掃描,攻擊者不需要大流量就能拖垮資料庫。可篩選的欄位要限定在有索引的範圍內,並設定查詢逾時(MySQL 的max_execution_time可以限制SELECT的執行時間) - 游標不等於授權:游標只決定從哪裡開始讀,查詢條件裡的
member_id必須來自驗證過的身分。如果改成「游標裡記著 member_id」,攻擊者改一下游標就能翻別人的訂單,這就是 BOLA(Part 8) - 唯一索引的錯誤訊息洩漏帳號是否存在:註冊時直接回傳「此 email 已被使用」,攻擊者就能逐一試出哪些 email 是會員(帳號列舉)。對外統一回應「確認信已寄出」,再由信件內容告知對方已有帳號
何時用/何時別用
- 該建索引:查詢頻繁、條件的選擇性夠高、讀遠多於寫的欄位組合;
WHERE、JOIN、ORDER BY常一起出現的欄位做成複合索引 - 不必建索引:幾千筆的小表(全表掃描就夠快)、寫入極重而查詢很少的表、只有少數幾種值的欄位
- 重新評估的時機:slow query log 中
Rows_examined遠大於Rows_sent的查詢;索引總大小接近或超過 buffer pool;寫入延遲或 replica 延遲上升;sys.schema_unused_indexes出現長期未使用的索引
參考資料
- Rudolf Bayer, Edward McCreight, “Organization and Maintenance of Large Ordered Indexes”, Acta Informatica, 1972
- Douglas Comer, “The Ubiquitous B-Tree”, ACM Computing Surveys, 1979
- Markus Winand, Use The Index, Luke!:https://use-the-index-luke.com/
- MySQL Reference Manual — Clustered and Secondary Indexes:https://dev.mysql.com/doc/refman/8.0/en/innodb-index-types.html
- MySQL Reference Manual — Multiple-Column Indexes:https://dev.mysql.com/doc/refman/8.0/en/multiple-column-indexes.html
- MySQL Reference Manual — EXPLAIN Output Format:https://dev.mysql.com/doc/refman/8.0/en/explain-output.html
- MySQL Reference Manual — Index Condition Pushdown Optimization:https://dev.mysql.com/doc/refman/8.0/en/index-condition-pushdown-optimization.html
- MySQL Reference Manual — Online DDL Operations:https://dev.mysql.com/doc/refman/8.0/en/innodb-online-ddl-operations.html
- MySQL Reference Manual — Invisible Indexes:https://dev.mysql.com/doc/refman/8.0/en/invisible-indexes.html
- MySQL 8.4 Reference Manual — Change Buffer:https://dev.mysql.com/doc/refman/8.4/en/innodb-change-buffer.html
- Spring Data JPA Reference — Query Methods(Sort、Scrolling):https://docs.spring.io/spring-data/jpa/reference/jpa/query-methods.html
- OWASP — SQL Injection Prevention Cheat Sheet:https://cheatsheetseries.owasp.org/cheatsheets/SQL_Injection_Prevention_Cheat_Sheet.html
- 互動圖解延伸:Dilum Sanjaya,System Design — an interactive course:https://designed-to-scale.vercel.app/
留言討論