44.8 索引原理 (B+ 树 / 哈希 / 覆盖索引 / 最左前缀)
一句话
索引是用写放大和空间换更少的页读取：B+ 树赢了范围查询，哈希赢了等值点查，覆盖索引赢在“不回表”——选型不是比谁先进，而是算清“这类查询要读几页”。
四种结构，四种胜负
| 结构 | 等值 | 范围 | 排序 | 写放大 | 典型场景 |
|---|---|---|---|---|---|
| B+ 树 | O(log n) | ✅ 叶子有序、区间扫描 | ✅ 天然有序 | 页分裂 | 绝大多数 OLTP 索引 |
| 哈希 | O(1) | ❌ 完全无序 | ❌ | 低 | 内存表、等值查找 |
| 倒排（全文） | 按词 | ❌ | ❌ | 高 | 搜索（45.1 倒排索引与分词） |
| 位图 | 按集合 | ⚠️ 低基数 | ❌ | 中 | 数仓低基数维度 |
🔑 B+ 树的本质是**“让叶子节点按 key 有序，并且用兄弟指针串起来”**：所以
BETWEEN、ORDER BY、LIMIT都能在索引上顺序扫，不用回表排序。哈希把 key 打散，天然丢失顺序，所以只能等值。
聚簇索引与二级索引：回表的代价
| 索引类型 | 叶子存什么 | 查一行要几次 I/O |
|---|---|---|
| 聚簇索引（主键） | 整行数据 | 树高次（3–4 页），拿到就是整行 |
| 二级索引 | 索引列 + 主键值 | 树高次 + 回表（按主键再查一次聚簇索引） |
| 覆盖索引 | 查询需要的全部列 | 树高次，不回表 |
package main
import "fmt"
const (
rows = 1_000_000 // 表行数
rowsPerPage = 100 // 每页 100 行
treeHeight = 3 // 扇出约 500 时，1M 行约 3 层
randReadMs = 0.10 // 随机读一页
seqReadMs = 0.01 // 顺序读一页
)
func pages(n int) int {
p := n / rowsPerPage
if n%rowsPerPage != 0 {
p++
}
return p
}
func main() {
tablePages := pages(rows) // 全表扫描要读的页数
type result struct {
name string
desc string
pages int
rand int // 其中随机读的页数
}
cases := []result{
{"主键点查", "B+ 树 3 层", treeHeight, treeHeight},
{"二级索引查 1,000 行（非覆盖）", "3 页索引 + 1,000 次回表", treeHeight + 10 + 1000, treeHeight + 1000},
{"二级索引查 1,000 行（覆盖索引）", "3 页索引 + 10 页叶子", treeHeight + 10, treeHeight + 10},
{"索引下推（索引层过滤）", "扫 1,000 条，仅 120 条回表", treeHeight + 10 + 120, treeHeight + 120},
{"哈希等值点查", "1 页定位", 1, 1},
{"哈希做范围查询", "不支持，退化为全表扫描", tablePages, 0},
{"B+ 树范围查 1,000 行", "3 页索引 + 10 页顺序叶子", treeHeight + 10, treeHeight},
}
fmt.Printf("表 %d 行、每页 %d 行、全表 %d 页；随机读 %.2fms、顺序读 %.2fms\n\n",
rows, rowsPerPage, tablePages, randReadMs, seqReadMs)
fmt.Printf("%-32s %-28s %-8s %-10s %s\n", "场景", "做什么", "页数", "估算耗时", "备注")
for _, c := range cases {
seq := c.pages - c.rand
ms := float64(c.rand)*randReadMs + float64(seq)*seqReadMs
note := ""
if c.name == "二级索引查 1,000 行（非覆盖）" {
note = "回表是主要成本"
}
if c.name == "二级索引查 1,000 行（覆盖索引）" {
note = "省掉 1,000 次随机读"
}
if c.name == "索引下推（索引层过滤）" {
note = "回表从 1,000 降到 120"
}
fmt.Printf("%-32s %-28s %-8d %-10s %s\n", c.name, c.desc, c.pages,
fmt.Sprintf("%.1fms", ms), note)
}
}
本机实测（macOS，Apple M1，Go 1.27）：
表 1000000 行、每页 100 行、全表 10000 页；随机读 0.10ms、顺序读 0.01ms
场景 做什么 页数 估算耗时 备注
主键点查 B+ 树 3 层 3 0.3ms
二级索引查 1,000 行（非覆盖） 3 页索引 + 1,000 次回表 1013 100.4ms 回表是主要成本
二级索引查 1,000 行（覆盖索引） 3 页索引 + 10 页叶子 13 1.3ms 省掉 1,000 次随机读
索引下推（索引层过滤） 扫 1,000 条，仅 120 条回表 133 12.4ms 回表从 1,000 降到 120
哈希等值点查 1 页定位 1 0.1ms
哈希做范围查询 不支持，退化为全表扫描 10000 100.0ms
B+ 树范围查 1,000 行 3 页索引 + 10 页顺序叶子 13 0.4ms
读数：
| 对比 | 差距 | 结论 |
|---|---|---|
| 非覆盖 vs 覆盖索引 | 1,013 页 vs 13 页（78 倍） | 查的列都在索引里，就不要回表 |
| 索引下推前后 | 回表 1,000 → 120（8 倍） | 把过滤条件下推到索引层，能少 88% 的回表 |
| 哈希等值 vs B+ 树等值 | 1 页 vs 3 页 | 哈希点查只读 1 页，但代价是丢掉范围与排序 |
| 哈希做范围查询 | 10,000 页（全表） | 不支持就是全表，索引等于没用 |
🔑 所以“加索引”之前先问：这条查询的列，能不能被一个索引完全覆盖？ 能 → 覆盖索引（最优）；不能 → 至少把过滤条件下推到索引（联合索引把过滤列放在前面）；范围查询与排序 → 只能 B+ 树。
最左前缀：不是规则，是物理事实
联合索引 (a, b, c) 在 B+ 树里是按 (a, b, c) 的字典序排列的：
(a=1,b=1,c=1) → (1,1,2) → (1,1,3) → (1,2,1) → (1,2,2) → (2,1,1) → ...
所以：
| 查询条件 | 能否用索引 | 为什么 |
|---|---|---|
a=1 | ✅ | 按 a 有序 |
a=1 AND b=2 | ✅ | 前缀连续 |
a=1 AND b=2 AND c=3 | ✅ | 完整前缀 |
b=2 | ❌ | b 在 a 相同的前提下才有序，跨 a 无序 |
a=1 AND c=3 | ⚠️ 只用 a，c 靠回表过滤 | c 跳过了 b |
a>1 AND b=2 | ⚠️ 只用 a 的范围 | 范围之后 b 不再有序 |
⚠️ 最常见的误解：“把选择性最高的列放最左”。真正的最左规则是**“等值条件放前面、范围条件放最后”**——因为范围一旦出现，它右边的列在索引里就不再有序，无法继续用于定位。
反模式
| 反模式 | 后果 |
|---|---|
| 给每个列都建单列索引 | 写放大、优化器选择困难，回表依旧 |
| 联合索引顺序按“选择性”而不是“查询形态”排 | 范围列放前面，后面的列全废 |
用 SELECT * 导致覆盖索引失效 | 每次查询都回表 |
在索引列上做函数/隐式转换（WHERE DATE(ts)=...） | 索引失效，全表扫描 |
| 用哈希索引做范围/排序 | 退化为全表 |
| 索引列太多（超宽联合索引） | 索引本身比数据大，写放大严重 |
自检
Q1 为什么“二级索引查 1000 行”比“覆盖索引查 1000 行”慢几十倍，而“点查一行”两者差不多？
▸ 答案：因为回表是按行数线性增长的：每回表一次就是一次随机 I/O（查聚簇索引的另一棵 B+ 树）。点查时回表只有 1 次，占比小；1000 行时回表 1000 次，直接主导成本。覆盖索引把查询需要的列都放在二级索引叶子里，回表次数为 0，所以行数越多差距越大。
Q2 WHERE b=2 用不上 (a,b,c) 联合索引，加一个 (b) 单列索引就好了吗？
▸ 答案：取决于查询形态。如果这条查询很频繁且只需要 b，加 (b) 或 (b, 查询需要的列) 覆盖索引是合理的；但如果它只是偶尔出现，多一个索引会带来写放大与空间成本（每个索引都要维护 B+ 树）。更常见的做法是调整查询或联合索引顺序，让高频查询走同一个索引。索引是写路径的成本，不是免费的读优化。
Q3 索引下推（ICP）到底省了什么？为什么它不能省掉“回表”本身？
▸ 答案：ICP 把“能在索引列上判断的条件”下推到存储引擎层，在回表之前先过滤掉不满足的行，从而减少回表次数（本节 1000 → 120）。但它仍然要回表取“索引里没有的列”，所以只能减少、不能消除回表。要消除回表，只能让索引覆盖查询需要的全部列。
- 下游：44.6 关系模型与范式
Q4 为什么在索引列上做函数运算（如 WHERE date(created_at)='2026-01-01'）会让索引用不上？
▸ 答案：因为 B+ 树索引存的是列的原值，不是 “函数结果”。对列做函数后，优化器无法用原值的有序性定位，只能逐行计算再比较（全表扫描）。解法是 “改写成范围查询”（created_at >= '2026-01-01' AND < '2026-01-02'）或建 “函数索引/生成列索引”。
Q5 一张表建了 10 个索引，写入会付出什么代价？怎么判断 “索引太多”？
▸ 答案：每个索引都是一棵 B+ 树：每次写入要更新所有索引，写放大与锁开销随索引数线性增长，还会占缓冲池。判据是 “索引的使用次数”——把长期零命中（或只被低效查询用到）的索引删掉；通常单表 5–6 个索引以上就要逐个 review。