# 第 23 章 索引原理与设计
> 索引是数据库里唯一"用空间与写放大换读性能"的结构，本章要能把它从树高算到 key_len。
## 学习目标
读完本章，你应当能够：
1. **推导**为什么 InnoDB 选 B+ 树而不是 B 树、哈希、红黑树、跳表、LSM 树，逐项给出判据而不只是背结论；
2. **计算**给定页大小、键长、行宽下的 B+ 树扇出、树高与可承载行数，并解释"查询稳定"的量化来源；
3. **辨析**聚簇索引与二级索引在页内布局上的差异，并据此解释回表、覆盖索引、主键长度对全部二级索引的连锁影响；
4. **由索引的排序性质推出**最左前缀原则、范围查询截断与 `ORDER BY` 可用条件，而不是背结论；
5. **判断**一条 `WHERE` 是否索引失效、失效在哪一层，并给出等价改写；
6. **设计**联合索引的列顺序、前缀索引长度与索引清理方案，并用 `sys` 库与慢查询验证。
### 前置知识检查
| 你需要知道 | 在哪一节补齐 |
|---|---|
| 页、区、段、表空间与行格式（`COMPACT`/`DYNAMIC`） | 第 20 章 20.2 节 |
| buffer pool 与索引页的载入、淘汰 | 第 20 章 20.3 节 |
| `EXPLAIN` 各字段含义、`type` 等级排序、`key_len` 计算 | 第 25 章 25.1 节 |
| 优化器基于代价选执行计划的基本流程 | 第 20 章 20.1 节 |
| 快照读与当前读的区别 | 第 22 章 22.4 节 |
## 23.1 为什么是 B+ 树：五种候选结构的逐项淘汰
索引被磁盘物理约束钉死：**数据以页为单位读写，一次页 I/O 是 SSD 约 100 μs、机械盘约 5~10 ms，而一次内存访问约 100 ns。** 因此设计目标不是"比较次数少"，而是**"访问页数少且页内顺序"**。目标一变，候选结构的胜负就完全不同。
| 结构 | 点查 | 范围查询 | 排序 | 树高（行数固定） | 被淘汰/胜出的根因 |
|---|---|---|---|---|---|
| B 树 | `O(log n)` | 中序遍历、页跳跃 | 不可用 | 与 B+ 树同 | 非叶也存数据 ⟹ 扇出小；数据散落各层 ⟹ 范围查询无法顺链走 |
| BST / 红黑树 | `O(log n)` | 中序遍历 | 可用但乱序 | 约 48 层 | 度只有 2 ⟹ 树高即 I/O 次数，数十次随机页读 |
| 哈希索引 | `O(1)` | 不支持 | 不支持 | 无树 | 哈希值丢失顺序；冲突退化；扩容需全量 rehash |
| B+ 树 | `O(log n)` | 叶链顺序扫描 | 叶层天然有序 | 3~4 层 | 非叶只存键+页号 ⟹ 扇出约 1170；数据同层 ⟹ 路径恒定 |
**B 树（B-tree）为什么输。** 第一，B 树**每个节点都存数据**，非叶节点在键与指针之外还要塞行或行指针，一次页 I/O 读到的键更少，扇出被数据挤小，树高上升。第二，**数据散落各层节点**，`WHERE id BETWEEN 100 AND 200` 无法顺一条有序链走，只能**中序遍历**：下降、回退、再下降，页访问顺序跳跃，预读（read-ahead）失效。
> [!IMPORTANT]
> 范围查询能力的差别不在"能不能查"，而在**访问顺序**。B+ 树把所有数据行压在叶层，叶页之间用双向链表串起来，范围扫描是一次顺序的链式前进；B 树的中序遍历则是随机的页跳跃。面试官追问"B+ 树比 B 树好在哪"，只答"数据都在叶子节点"是不够的，必须接上"叶层有序链表 ⟹ 范围查询与 `ORDER BY` 变成顺序 I/O"。
**哈希索引（hash index）为什么只做补充。** 哈希把键映射到桶，等值查找均摊 `O(1)`，但哈希值**本身丢失了键的大小顺序**：范围查询（`> < BETWEEN`）、排序（`ORDER BY`）、最左前缀匹配全部失效。它还有两个工程问题：**哈希冲突**在数据倾斜时退化成链式扫描；**桶数不能动态平滑扩展**，扩容要全量重哈希。InnoDB 因此不提供用户可见的哈希索引，只在内部做自适应哈希（见 23.10）；Memory 引擎的 `USING HASH` 是显式哈希索引，代价就是上一条限制。
**二叉搜索树（binary search tree, BST）与红黑树（red-black tree）为什么输在树高。** 红黑树在内存里是优等生（树高约 `2 × log₂N`、旋转代价有界），但放到磁盘上树高就是 **I/O 次数**：`N = 2000 万` 时 `log₂(2×10⁷) ≈ 24`，红黑树约 48 层，每层一次页读就是数十次随机页 I/O（SSD 约 5 ms，机械盘约 240 ms）。**根子在二叉树的度只有 2**，而一页能容纳上千个键 —— 把度提到 1000 以上，树高从 48 掉到 3。
**跳表（skip list）为什么用于内存而非磁盘。** 跳表用概率性多层链表实现 `O(log n)` 查找，实现无锁插入很容易，所以 Redis 的 ZSet 用它。但它的节点是**动态分配的离散内存块**，指针指向的地址在页内/页间毫无连续性，磁盘上每次下降都可能是新的一次随机页读。跳表赢在内存随机访问便宜，输在磁盘局部性。
**LSM 树（log-structured merge tree）为什么不是 InnoDB 的选择。** 它把随机写变顺序写（MemTable → 不可变 MemTable → SSTable），写入吞吐远超 B+ 树，代价是**读放大**：点查要自新到旧逐层找，最坏扫多个 SSTable（靠 Bloom filter 兜底）；合并（compaction）又反复重写数据。判据很干净：**读多写少且要事务与范围查询 ⟹ B+ 树；写多读少、按 key 点查为主 ⟹ LSM**。
## 23.2 B+ 树的布局与树高估算
B+ 树的页（page）分两类角色，两类页的**内容构成决定了扇出**：
```text
三层 B+ 树：扇出 1170、每叶 16 行 ⟹ 约 2100 万行
[ 根页 root：仅键 + 子页号 ]
/ | \
/ | \
[非叶页 L2-a] ... [非叶页 L2-b] ... [非叶页 L2-c] ← 1170 个子页
\ | /
\ | /
┌───────────┬───────────┬───────────┬───────────┐
│ 叶页 P1 │ 叶页 P2 │ 叶页 P3 │ ... │ ← 1170 × 1170 个叶页
│ 行 行 ... │ 行 行 ... │ 行 行 ... │ │
└─────┬─────┴─────┬─────┴─────┬─────┴─────┬─────┘
└───────────┴───────────┴───────────┘
叶页双向链表：范围扫描 = 顺序 I/O
每个非叶页还带前驱/后继页号 + 页目录（page directory）
树高与承载量估算（页 16 KB = 16384 B；非叶条目 = 键 8 B + 页号 6 B = 14 B）
扇出 F = 16384 / 14 ≈ 1170 每叶行数 R = 16384 / 1024 ≈ 16
三层 = 1170 × 1170 × 16 ≈ 2.1×10⁷ 行（二层 1.9 万行，四层 ≈ 2.5×10¹⁰ 行）
定位任意一行的页 I/O 次数 = 树高 = 3 次（根页常驻 buffer pool 时 = 2 次）
```
**为什么非叶页不存数据就能把扇出做大。** 非叶页里全是"键 + 子页号"对：键取子页中最小键的**分隔键（separator key）**，页号按 6 字节计，故 16 KB 页能塞约 1170 个条目。若把整行（1 KB）也塞进非叶页，一页只剩 16 个条目，三层能放的行数从 `2.1×10⁷` 跌到 `16³ ≈ 4096` —— 这就是 B 树的真正代价。
> [!NOTE]
> 这是教材式最小口径，只算"键 + 页号"。真实 InnoDB 页还要扣页头页尾约 200 B、`PAGE_DIRECTORY` 槽位、记录头 5 B，实际扇出低于 1170；键长也不固定（`BIGINT` 是 8 B，`CHAR(36)` UUID 是 36 B）。先说教材口径再主动指出真实值更小，是加分项。
**查询稳定性来自哪里。** 所有数据行都在同一层（叶层），任意一行的定位路径长度都等于树高，因此**单行点查的 I/O 次数恒定**，不带红黑树那种"有的键在浅处、有的在深处"的抖动。量级对比：3 次页 I/O（命中 buffer pool 时是内存访问，未命中时 SSD 约 300 μs）对全表扫描的约 125 万个页读取，差距约 6 个数量级。
## 23.3 聚簇索引与二级索引：物理布局差异
InnoDB 的主键索引就是表的**数据本身**，这一点决定了二级索引的一切行为。
```text
聚簇索引（clustered index）与二级索引（secondary index）的叶页对比
聚簇索引 B+ 树 二级索引 B+ 树（以 idx_name 为例）
┌──────────────────────┐ ┌──────────────────────┐
│ 非叶：键 = id │ │ 非叶：键 = name │
└──────────┬───────────┘ └──────────┬───────────┘
↓ ↓
┌──────────────────────┐ ┌──────────────────────┐
│ 叶页 = 数据页 │ │ 叶页 = (name, id) │
│ (id=1, name='a',... )│ │ ('a', 1) │
│ (id=2, name='b',... )│ │ ('b', 2) │
│ ... 整行都在叶页 │ │ ... 只有键 + 主键 │
└──────────────────────┘ └──────────────────────┘
命中即得整行 命中只得到 id ⇒ 回表
```
**二级索引点查两步走（回表）**：先在二级索引定位到 `('b', 2)`（1~3 次页 I/O），再拿 `id = 2` 去聚簇索引重走一遍 3 层树（再 1~3 次页 I/O）；1000 行命中就重复 1000 次，只有主键恰好有序时才退化为顺序扫描。
**两棵树的关键差异**：聚簇索引的叶页**就是数据页**，叶页里存的是完整行记录（含所有列，超长变长列走溢出页，见第 20 章 20.2 节）；二级索引的叶页只存"索引列 + 主键值"，因此**命中二级索引后必须再查一次聚簇索引才能拿到其他列**，这个动作叫**回表**。
**InnoDB 必须有主键，按"显式主键 → 第一个唯一且非空的索引 → 隐藏列 `DB_ROW_ID`（6 字节自增）"的顺序确定聚簇索引键。** 落到隐藏列最糟：所有二级索引都要拿一个看不见、不可干预的值回表；落到某个唯一索引则意味着那个索引不再是"独立索引"，它本身成了数据。
**自增主键的收益**是链条式的：插入总是落在 B+ 树最右侧，几乎不触发页分裂与页内数据搬移（顺序写）；主键短（`BIGINT` 8 B）使每个非叶条目更小、扇出更大、树高更低；更关键的是**每个二级索引的叶页都要存主键值**，主键短 ⟹ 所有二级索引都更小。
> [!CAUTION]
> 常见错误回答："主键用不用自增无所谓，反正都能查。" 这句话会直接暴露没理解聚簇索引。主键在 InnoDB 里不是"一个约束"，它是**物理存储顺序**，并且被复制进每一个二级索引。用长主键的代价不是"主键索引变大"，而是"所有索引一起变大 + 所有写入都可能页分裂"。
## 23.4 为什么推荐自增主键而不是 UUID
UUID 作为主键有两个独立的缺陷，必须分开讲。
**缺陷一：随机插入导致页分裂与空间浪费。** 自增主键的插入点永远在最右叶页，页满了就在右侧追加新页，老页不动；UUID 随机，插入点均匀落在整个键空间，目标页大概率已满且**满页中间插不进去**，只能做**页分裂（page split）**：一页拆两页并移动约一半记录，于是一次写入变成多次页写、父页要更新、页在文件中不再连续、填充率下降、随机 I/O 上升。
**缺陷二：索引体积全面膨胀。** `BIGINT` 主键 8 B；`CHAR(36)` 形式的 UUID 是 36 B，加上二级索引叶页每个条目都要存主键，二级索引条目从 `索引列 + 8 B` 变成 `索引列 + 36 B`。若索引列本身只有 8 B（如 `user_id BIGINT`），条目从 16 B 涨到 44 B，二级索引体积接近原来的 2.75 倍 —— buffer pool 命中率、页 I/O 次数、备份体积全部受牵连。
| 主键方案 | 键长 | 插入点 | 页分裂 | 二级索引条目 | 分布式友好 |
|---|---|---|---|---|---|
| `AUTO_INCREMENT BIGINT` | 8 B | 最右叶页（顺序） | 极少 | 索引列 + 8 B | 弱（需号段/分片步长） |
| `CHAR(36)` UUID 文本 | 36 B | 全键空间随机 | 频繁 | 索引列 + 36 B | 强 |
| `BINARY(16)` + `UUID_TO_BIN(uuid, 1)` 或有序 UUID | 16 B | 近似顺序 | 少 | 索引列 + 16 B | 强 |
两条缓解路径：一是 `UUID_TO_BIN(uuid, 1)` 把 UUID 转 16 字节二进制，同时把**时间低位与时间高位交换**，使二进制形式按时间单调，从"完全随机"变成"近似顺序"；二是改用按时间递增的有序 UUID（UUIDv7 这类时间前缀方案），从根本上让键有序。
```sql
CREATE TABLE t_order (
id BINARY(16) NOT NULL, -- 用 BINARY(16) 而非 CHAR(36)：索引条目与所有二级索引都小一半以上
amount DECIMAL(10,2) NOT NULL,
PRIMARY KEY (id)
) ENGINE=InnoDB;
-- 第二参数 1 交换时间高位与低位，让二进制按时间有序：目的不是省字节，而是把随机插入点变成近似顺序插入点
INSERT INTO t_order (id, amount) VALUES (UUID_TO_BIN(UUID(), 1), 99.00);
-- 函数作用在常量而非列上，所以不破坏索引；若写成 WHERE BIN_TO_UUID(id) = '...' 则索引失效
SELECT BIN_TO_UUID(id) AS id_text, amount FROM t_order WHERE id = UUID_TO_BIN('...', 1);
```
> [!TIP]
> 面试话术：推荐自增主键的三条理由是"顺序写不分裂、键短扇出大、二级索引只存 8 字节"，比只说"自增性能好"高一个层次。若面试官追问"分库分表下自增怎么用"，答"号段模式或分片步长"并引到第 26 章 26.4 节。
## 23.5 覆盖索引：把回表省掉
回表是二级索引的固有开销，**覆盖索引（covering index）** 就是让这次回表不必发生：当查询需要的**所有列**都能从二级索引的叶页里读到（索引列 + 主键），就无需再查聚簇索引。
触发条件：`SELECT` 列表与 `WHERE`/`ORDER BY`/`GROUP BY` 用到的列**全部**落在同一个索引的列集合（含隐式包含的主键）里。"同一个索引"是硬要求 —— 列横跨两个索引时一次扫描凑不齐（除非走索引合并，见第 25 章 25.4 节）。
```sql
-- 建表：联合索引 (a, b)，叶页实际存 (a, b, id)
CREATE TABLE t (id BIGINT PRIMARY KEY AUTO_INCREMENT, a INT, b INT, c VARCHAR(64), KEY idx_ab (a, b)) ENGINE=InnoDB;
-- 覆盖：需要 a、b、id 三列，全都在 idx_ab 叶页里，Extra 显示 Using index
EXPLAIN SELECT a, b, id FROM t WHERE a = 1 AND b = 2;
-- 不覆盖：c 不在 idx_ab 里，必须回表拿 c，Extra 不出现 Using index
EXPLAIN SELECT a, b, c FROM t WHERE a = 1 AND b = 2;
-- SELECT * 必然不覆盖（除非表只有这几列）：列越多越不可能被单个索引覆盖
EXPLAIN SELECT * FROM t WHERE a = 1 AND b = 2;
```
`EXPLAIN` 的 `Extra = Using index` 表示**索引覆盖**（注意它和 `Using index condition`、`Using where` 是三个不同东西，见 23.7）。覆盖索引的收益是实打实的 I/O 数量减半以上：无覆盖时命中 k 行的成本约 `3 + k` 次页访问（每次回表一次聚簇索引查找），有覆盖时约 `3 + k/16` 次（叶页顺序前进，每页 16 行）。
> [!WARNING]
> 陷阱一：以为"索引覆盖"和"用上索引"是一回事 —— 只有 `Extra = Using index` 才是覆盖，`key` 有值不等于不回表。陷阱二：`SELECT *` 把"只需索引列"变成"需要全部列"，一次性废掉所有覆盖机会。
## 23.6 最左前缀原则的完整推导
结论必须从 B+ 树的排序性质推出来，而不是背。
```text
联合索引 idx_abc (a, b, c) 在 B+ 树中的实际排序
全树先按 a 升序排列；a 相同的记录按 b 升序；a、b 都相同的按 c 升序。
（叶页内部：只存 (a, b, c, id)，id 是隐式附加的最后一列）
叶页示意（每格 = 一条索引记录）：
┌──────────────┬──────────────┬──────────────┬──────────────┐
│ (1, 5, 9, 11)│ (1, 6, 2, 12)│ (1, 6, 3, 13)│ (2, 4, 8, 14)│ ...
└──────────────┴──────────────┴──────────────┴──────────────┘
a=1 段 ─────────────────────→ │ a=2 段 → ...
b: 5 → 6 → 6（a 相同才有 b 有序）
同 a 同 b 时 c: 2 → 3
⟹ 三个可用性判据：
① a 是全局有序的 ⇒ 能用 a 做等值定位（B+ 树下降）
② b 只在 a 固定的子段内有序 ⇒ 必须 a 等值后 b 才可用
③ c 只在 a、b 都固定的子段内有序 ⇒ 必须 a、b 都等值后 c 才可用
```
据此逐条推导常见组合（索引 `(a, b, c)`）：
| 查询条件 | 用于定位的列 | 剩余条件如何生效 | 说明 |
|---|---|---|---|
| `a = 1` / `a = 1 AND b = 2` | a；a, b | 无 | 最左前缀逐列生效 |
| `a = 1 AND b = 2 AND c = 3` | a, b, c | 无 | 全列定位，`key_len` 覆盖三列 |
| `a = 1 AND c = 3` | a | c 在 5.6+ 可下推过滤 | c 不能用于定位，见 23.7 |
| `a = 1 AND b > 2 AND c = 3` | a | b 用于范围，**c 无法定位** | 范围查询截断后续列 |
| `b = 2`；`a > 1 AND b = 2` | 无（跳过 a ／ a 用范围） | 只能全索引扫描或逐段判断 | 最左前缀断裂与范围截断的两种退化形态 |
**范围查询为什么截断后续列。** 下降必须在"每个上层键对应一段连续区间"下进行。a 取范围时命中多个不连续子段（a=2 一段、a=3 一段……），段内 b 有序但**跨段全局无序**，无法用一个连续 b 区间定位，只能扫 a 的范围再逐行过滤 b、c。
**排序与分组能不能用索引。** 条件：索引列顺序与 `ORDER BY` 一致或完全相反，且不混用升降序。
```text
索引 (a, b, c) 下 ORDER BY 的可用性
ORDER BY a, b, c → 叶页天然有序，直接读，无排序
ORDER BY a DESC, b DESC → 整体反向扫描，无排序
ORDER BY a ASC, b DESC → 混合方向，8.0 前必须 filesort（8.0 可建降序索引 idx(a ASC, b DESC) 消除）
ORDER BY b, c / a, c → 跳过 a 或跳列 ⇒ filesort
WHERE a = 1 ORDER BY b → a 已固定，该子段内 b 有序 ⇒ 无排序
WHERE a > 1 ORDER BY b → a 是范围，b 跨段无序 ⇒ filesort
```
> [!IMPORTANT]
> 三条必背判据：**等值列可以任意顺序出现在 `WHERE` 里（优化器会重排），范围列之后的列不能用于定位；`ORDER BY` 要么与索引列顺序一致或全反，要么依赖前面的等值条件把范围收窄成单段；`GROUP BY` 的可用条件与 `ORDER BY` 完全一致**，因为它的实现同样依赖有序输入。`EXPLAIN` 里看到 `Using filesort` 或 `Using temporary` 就说明这条路径没走成。
## 23.7 索引下推：`Using index condition`
索引下推（Index Condition Pushdown, ICP）是 5.6 引入的优化，解决的是"**范围截断后的列条件由谁过滤**"。
没有 ICP 时引擎只按索引前缀定位候选主键，把整行回表交给 Server 层判断 `c = 3`，不合格即丢弃，但回表 I/O 已付掉；有 ICP 时 `c = 3` 被下推到引擎，在索引记录上直接判断，不合格的**不回表**。
```sql
-- 索引 idx_abc (a, b, c)；b 是范围，c 不能用于定位，但可以下推过滤
EXPLAIN SELECT * FROM t WHERE a = 1 AND b > 2 AND c = 3;
-- Extra: Using index condition
-- 含义：c = 3 在引擎层用索引中的 c 列过滤，过滤失败的记录不回表
-- 注意：这不叫覆盖索引。SELECT * 仍需回表，只是回表次数被减少了
```
四个 `Extra` 取值必须分清：`Using index` = 覆盖索引、根本不回表；`Using index condition` = ICP，索引中的列在**引擎层**过滤，不合格的**不回表**；`Using where` = 引擎已把行返回给 Server 层后在 **Server 层**过滤；`Using index; Using where` = 覆盖 + 残留条件仍在 Server 层过滤。
> [!NOTE]
> ICP 的收益取决于"被下推条件的过滤率"。若 `c = 3` 能滤掉 90% 的候选行，回表次数直接降一个量级；若几乎滤不掉任何行，ICP 只是多了一层判断开销。它与覆盖索引的正交关系要记住：**覆盖索引省的是"不需要回表"，ICP 省的是"不合格的不回表"。**
## 23.8 索引失效情形清单
失效的判定方法统一为：**看 `EXPLAIN` 的 key 是否为 NULL、type 是否退化为 `ALL`/`index`、rows 是否接近全表。** 下面逐条给出原因与改写。
| 情形 | 典型写法 | 为什么会失效 | 改写方案 |
|---|---|---|---|
| 索引列上做函数/运算 | `YEAR(create_time) = 2024`、`id + 1 = 100` | 索引存的是列原值，函数或运算的结果在索引中不存在，无法定位 | 改范围 `create_time >= '2024-01-01' AND create_time < '2025-01-01'`；或 `WHERE id = 99` |
| 隐式类型转换（字符串列对数字） | 列 `phone VARCHAR(11)`，写 `WHERE phone = 13800000000` | 数字与字符串比较时 MySQL 把**字符串列转成数字**再比，等于对列做函数 | 加引号：`WHERE phone = '13800000000'` |
| 隐式类型转换（数字列对字符串） | 列 `id BIGINT`，写 `WHERE id = '100'` | 字符串常量转成数字，函数落在常量上，**列仍可用** | 无需改写，方向与上一条相反 |
| 前导模糊匹配 | `WHERE name LIKE '%abc'` | 索引有序性只对前缀有效，通配符开头无法定位起点 | `LIKE 'abc%'`；必须前后模糊则用全文索引 |
| `OR` 含未建索引列 | `WHERE a = 1 OR d = 2`（d 无索引） | 结果集必须含 d=2 的全表行 | 给 d 建索引；或改 `UNION ALL` 各走各的索引 |
| `!=` / `NOT IN` / `IS NOT NULL` | `WHERE status != 1` | "排除少数值"通常仍要扫大部分页（**是选择性判断，不是语法禁用**） | 用 `IN` 枚举少量目标值，或改成正向范围 |
| 联合索引未遵循最左前缀 | 索引 `(a,b)`，写 `WHERE b = 2` | b 在 a 不固定时不全局有序 | 补 a 条件，或另建 `(b)` / `(b,a)` |
| `ORDER BY` 与索引顺序不一致 | 索引 `(a,b)`，写 `ORDER BY b` | 同最左前缀 | 调整 `ORDER BY` 或另建索引 |
| 统计信息过期 / 表太小 / 区分度太低 | 大批量变更后仍选全表；`status` 只有 3 个值 | 优化器据 `rows`/`filtered` 低估收益；回表加随机 I/O 比全表顺序扫描更贵 | `ANALYZE TABLE t;` 刷新统计信息；不加低区分度索引 |
```sql
-- 隐式转换的两个方向必须分清：转换发生在列上才失效（phone VARCHAR(11)，idx_phone）
EXPLAIN SELECT * FROM t WHERE phone = 13800000000; -- 列被转数字 ⇒ key = NULL
EXPLAIN SELECT * FROM t WHERE phone = '13800000000'; -- 常量是字符串 ⇒ key = idx_phone
EXPLAIN SELECT * FROM t WHERE uid = '100'; -- 数字列对字符串常量：key = idx_uid
-- 用 FORCE INDEX 验证"到底是不想用还是不能用"：强制后仍回退全表，说明统计信息判断成本更高
EXPLAIN SELECT * FROM t FORCE INDEX (idx_phone) WHERE phone = 13800000000;
```
> [!CAUTION]
> 把 `!=`、`NOT IN`、`IS NOT NULL` 一律答成"索引失效"是常见错误。它们只是**优化器可能主动放弃**：当被排除的值占绝大多数、且必须回表时才会放弃。`WHERE status IS NOT NULL` 在 `status` 只有极少数 NULL 时确实走全表；而 `WHERE status != 1` 若 1 占全表 99%，剩下的 1% 反而**会走索引**。区分"语法导致不可用"与"代价导致不选"是面试的关键分水岭。
## 23.9 联合索引列顺序、前缀索引与索引维护
### 23.9.1 列顺序的设计方法论
先算**选择性（selectivity）**，再排顺序。区分度的标准口径是 `COUNT(DISTINCT col) / COUNT(*)`，值越接近 1 越"能筛掉人"。
```sql
-- 选择性口径 = 唯一值个数 / 总行数，越接近 1 越能筛掉人（0.001 基本等于没筛）
SELECT COUNT(DISTINCT user_id) / COUNT(*) AS sel_user,
COUNT(DISTINCT status) / COUNT(*) AS sel_status FROM t_order;
-- 前缀长度要"从短到长试"，找选择性逼近全列的最小 N：先定 8 个字符再验证是错的做法
SELECT COUNT(DISTINCT LEFT(email, 6)) / COUNT(*) AS p6,
COUNT(DISTINCT LEFT(email, 10)) / COUNT(*) AS p10,
COUNT(DISTINCT email) / COUNT(*) AS full_sel FROM t_user;
```
列顺序的判据按三类用法排优先级：
```text
列顺序决策树
① 收集高频查询，把每个候选列分类：等值列（= / IN）／范围列（> < BETWEEN LIKE 'x%'）／排序列
② 默认顺序：等值列在前 → 排序列居中 → 范围列在后
（范围列后面的列无法定位，见 23.6；排序列只要前面全等值就仍可免排序）
③ 例外一：选择性极低的等值列（如 status 只有 3 个值）放后面，放最左反而让大片行挤在一起
④ 例外二：ORDER BY + LIMIT 且范围列在排序列之前时，优先保排序列免 filesort，范围列放最后
⑤ 例外三：为了让某条高频查询被覆盖，覆盖需求可以压过选择性优劣
```
**`(a, b)` 与 `(b, a)` 的取舍判据**：两者都能服务 `WHERE a = ? AND b = ?`（条件顺序由优化器重排），差别只在单独用 a 的查询多还是单独用 b 的多 —— 前者多就建 `(a, b)`；两方向都高频时建一个复合索引加一个单列索引，而不是两个复合索引（双份写放大）。
**找该加与该删的索引**：该加的证据来自慢查询日志与 `pt-query-digest` 的 TOP 慢查询（按 `Rows_examined` 排序，而不是按耗时）；该删的证据来自 `sys.schema_unused_indexes`（`performance_schema` 计数为 0）与 `sys.schema_redundant_indexes`（前缀重复）。`pt-index-usage` 从慢日志统计每条索引的实际使用次数，适合做双向核对。
### 23.9.2 前缀索引
对长字符串列（URL、邮箱、`token`），可以只索引前 N 个字符：`KEY idx_email (email(10))`。
| 项目 | 全列索引 | 前缀索引 |
|---|---|---|
| 索引体积 | 与列长成正比 | 约 `N/列长`，长列收益巨大 |
| 区分度 | 100% 精确 | 等于 `COUNT(DISTINCT LEFT(col, N))/COUNT(*)`，可能误命中需回表核对 |
| 覆盖索引 | 可以 | **不能当作覆盖索引**：叶页里没有完整值可返回 |
| `ORDER BY` / `GROUP BY` | 可用 | **不可用**：前缀有序 ≠ 全列有序，必然 `filesort` |
> [!WARNING]
> 前缀索引的"测量—再选长度"顺序经常被答反。正确做法是**先算各长度前缀的选择性，选达到目标（例如全列选择性的 90% 以上）的最短长度**，而不是先定 8 个字符再算。另外前缀索引无法覆盖、无法用于排序，在只读密集且依赖覆盖的查询上可能得不偿失。
### 23.9.3 索引的维护成本
索引不是免费的：**每次写入都要维护该表上的每一个索引**。一条 `INSERT` 改 1 棵聚簇索引树 + N 棵二级索引树；`UPDATE` 改到被索引的列就要删旧条目、插新条目，两个位置可能相距很远 —— 这就是**写放大**。
**change buffer** 缓解的正是这个成本：对**非唯一二级索引**的写，若目标页不在 buffer pool，InnoDB 先把变更记入 change buffer（内存 + 系统表空间持久化），等该页被读入时再合并（merge），把多次随机页读推迟并合并。两个边界：**唯一索引不能用**（插入前必须读页判重，页已被读入就失去延迟的意义）；**聚簇索引也不用**（数据页就是索引页）。
| 成本项 | 表现 | 观测手段 |
|---|---|---|
| 写放大 | 每条 `INSERT` 维护所有索引；`UPDATE` 索引列 = 删 + 插 | `Innodb_rows_inserted`、写入延迟 |
| buffer pool 挤压 | 索引越多，总页数越多，在固定 `innodb_buffer_pool_size` 下命中率越低 | 命中率 = `1 − Innodb_buffer_pool_reads / Innodb_buffer_pool_read_requests` |
| 冗余索引 | `(a)` 被 `(a, b)` 完全覆盖；`(a, b)` 与 `(b, a)` 各占一份 | `sys.schema_redundant_indexes`、`sys.schema_unused_indexes` |
```sql
-- 该删的索引要有量化证据：从未被使用过，或是更长索引的前缀冗余
SELECT * FROM sys.schema_unused_indexes; -- 自 performance_schema 启动以来使用计数为 0
SELECT * FROM sys.schema_redundant_indexes; -- redundant_index 是 covering_index 的前缀
-- 等价手写检查：逐位列名与序号都相同，才说明一个是另一个的前缀
SELECT t1.INDEX_NAME, t2.INDEX_NAME, GROUP_CONCAT(t1.COLUMN_NAME ORDER BY t1.SEQ_IN_INDEX) AS cols
FROM information_schema.STATISTICS t1
JOIN information_schema.STATISTICS t2
ON t1.TABLE_SCHEMA = t2.TABLE_SCHEMA AND t1.TABLE_NAME = t2.TABLE_NAME
AND t1.SEQ_IN_INDEX = t2.SEQ_IN_INDEX AND t2.INDEX_NAME <> t1.INDEX_NAME
WHERE t1.TABLE_SCHEMA = 'demo' AND t1.SEQ_IN_INDEX <= 3
GROUP BY t1.INDEX_NAME, t2.INDEX_NAME;
```
## 23.10 哈希索引与自适应哈希索引
InnoDB **不提供用户可见的哈希索引**，唯一形式是**自适应哈希索引（adaptive hash index, AHI）**：引擎观测到某些索引页被以**相同前缀模式**反复等值访问时，为这些页在 buffer pool 建哈希表，把"B+ 树下降 2~3 层"压成"一次哈希定位"。它的有效条件很窄：
| 维度 | 有效 | 无效 / 有害 |
|---|---|---|
| 访问模式与并发 | 高频重复等值查询、热点页集中，省下 B+ 树下降与 latch 争用 | 范围查询与排序为主（哈希无顺序）、低并发、访问均匀分散 |
| 失效条件 | — | 大量写入或页分裂致哈希表频繁重建，`btr_search_latch` 争用 |
因此**命中率低或写密集时应当关闭**它（`innodb_adaptive_hash_index = OFF`，或分区化 `innodb_adaptive_hash_index_parts`）。Memory 引擎的 `USING HASH` 是显式哈希索引，与 AHI 相反：它自知只能做等值查询，会**主动拒绝**范围查询的索引使用。
> [!NOTE]
> 下一层追问："哈希等值更快，为什么 InnoDB 不做可选显式哈希索引？" 三点骨架：显式哈希无法参与范围查询与排序，会让同一条 SQL 在不同数据分布下出现"用了索引反而更慢"的选择困难；最热的主键等值点查已被聚簇索引覆盖，收益边际小；它需要独立的一致性维护（回滚、崩溃恢复都要改它），而 AHI 是可丢弃、可重建、不参与恢复的缓存层。
## 23.11 索引设计的完整决策流程
```text
索引设计/评审的实际顺序
① 列出全部查询与读写比 → 每条查询标出等值列／范围列／排序列／返回列
② 定主键：自增 BIGINT（单库）或有序 16 B（分布式）
③ 为"最高频且最贵"的查询建第一条联合索引：等值列 → 排序列 → 范围列
④ 看能否覆盖（返回列并入索引，回表次数从 k 降到 k/页行数）
⑤ 其余查询先试复用已有索引的最左前缀，不能复用再新建
⑥ 长字符串列用前缀索引，长度由选择性测量决定
⑦ 上线后用 sys 库视图 + 慢查询复核；新增索引必须回答"它让哪些写入变慢了"
```
> [!TIP]
> 面试收尾话术：**"索引设计不是选一列，而是在一组查询上做贪心集合覆盖，同时受写放大预算约束。"** 这句话能把话题从"背结论"拉到"工程权衡"，通常直接吃到加分。
## 本章小结
| 关键结论 | 一句话表述 | 常见错误 |
|---|---|---|
| B+ 树胜出的根因 | 非叶只存键+页号 ⟹ 扇出约 1170 ⟹ 三层约 2100 万行、点查 3 次页 I/O、路径恒定 | 只答"数据都在叶子节点"，接不上范围查询与扇出的因果 |
| 聚簇索引 | 叶页即数据页，主键即物理顺序，且被复制进每个二级索引 | 把主键当作纯逻辑约束 |
| 二级索引与回表 | 叶页只存索引列 + 主键，命中后必须回表 | 认为"用了索引就不用读表" |
| 覆盖索引 | `Extra = Using index`，所需列全在同一索引内 | 与 `Using index condition` 混为一谈 |
| 最左前缀与范围截断 | 由 B+ 树排序性质推出；范围列之后的列不能定位，只能用 ICP 过滤 | 只会背"最左"，说不出范围截断的原因 |
| 索引失效的两类 | 语法导致不可用 vs 优化器代价判断后不选 | 把 `!=`/`NOT IN` 一律答成"索引失效" |
| 自增主键 | 顺序写免页分裂 + 键短扇出大 + 节省所有二级索引体积 | 只答"自增快"，说不出二级索引也被拖累 |
| 写放大与 change buffer | 每写一行维护所有索引；change buffer 只对非唯一二级索引生效 | 认为唯一索引也能用 change buffer |
## 自测题
**Q1**（计算）页 16 KB，非叶条目 = 键 8 B + 页号 6 B，叶页每行 1 KB。求三层 B+ 树的扇出、可承载行数与点查页 I/O 次数；若主键改为 `CHAR(36)`，扇出变化如何？
答案与解析
扇出 `F = 16384 / 14 ≈ 1170`；每叶行数 `R = 16384 / 1024 ≈ 16`；三层可承载 `1170 × 1170 × 16 ≈ 2.1×10⁷` 行；点查页 I/O 次数 = 树高 = 3（根常驻 buffer pool 则 2）。
主键改 `CHAR(36)` 时分两个方向：如果它只是**叶层数据列**，树高不变，但叶页放不下 16 行（行变宽），叶层能存的行数下降；如果它进入**非叶条目的键**（例如二级索引 `(name)` 的条目变成 `name + 36 B` 主键），非叶条目从 `8+6=14` 涨到 `36+6=42`，扇出从 1170 掉到约 390，树高与叶页数量都要往上走。
**错在哪**：把树高当成"3 层 3 次查找、加上回表 6 次"——回表只发生在二级索引上。**面试官追问**："根页为什么能常驻？" 答"根页被反复访问，LRU 长期保留它，且整棵树只有一个根页，内存可忽略"。
答案与解析
不能用于定位。a 等值后进入 a=1 的连续段；b 是范围，命中的是 b>2 的连续子段；在这个子段内 c 有序，但优化器无法用一个 c 的连续区间去做下降定位（对 c 的约束只在"b 的每个取值内部"成立，跨 b 值不成立）。因此定位只用 a（`key_len` 只体现 a + 可能的部分 b），c 的条件在 5.6+ 由 ICP 下推到引擎层过滤，`Extra` 出现 `Using index condition`；若同时能覆盖则可能同时出现 `Using index`。
**错在哪**：答"能，因为 c 在索引里"——索引里有这一列 ≠ 它能用于定位。**面试官追问**："那什么情况下 c 能用于定位？" 答"`a = 1 AND b = 2 AND c = 3` 全等值，或者 `a = 1 ORDER BY b, c` 这种 b 不再被范围截断的情形"。
答案与解析
首选 `KEY idx_u_s_c (user_id, status, created_at)`：`user_id`、`status` 都是等值列，放最左；`created_at` 是排序列，且在两个等值列固定后其子段内有序，`ORDER BY created_at DESC` 可反向扫描该子段，消除 `filesort`，`LIMIT 20` 直接截断。
第二条 `WHERE user_id = ? ORDER BY created_at DESC` 只有 `user_id` 等值，同一 user 下 status 可取多个值，而在 (user_id, status, created_at) 的序里 `created_at` 只在每个 status 段内有序、**跨 status 无序**，所以不能免排序：可另加 `KEY idx_u_c (user_id, created_at)`，或接受它走 `idx_u_s_c` 定位 + ICP 过滤 + `filesort`（带 `LIMIT 20` 且 user 下数据有限，常可接受）。
**错在哪**：把 `status` 放最左（因为它选择性低），或把 `created_at` 放在范围类列之后导致它失去排序能力。**面试官追问**："新增 `(user_id, created_at)` 会不会造成写放大？" 要能答"会，每多一个索引就多一次随机写与一份 buffer pool 占用，要用 `sys.schema_unused_indexes` 复核后再决定"。
答案与解析
`phone` 是字符串列，与数字比较时 MySQL 按规则把**字符串列转换为数字**再比较，等价于在列上做函数运算，索引失效（`key = NULL`）。加引号后常量是字符串，直接按索引键比较，走索引。
`uid` 是数字列，`'100'` 是字符串常量，比较时把**常量**转换为数字，函数作用在常量上，索引正常可用。
**错在哪**：把两条规则记成一句"隐式转换会导致索引失效"。正确表述是："**转换发生在索引列上才失效**，发生在常量上不影响。"**面试官追问**："怎么快速验证？" 答"`EXPLAIN` 看 `key`，或 `FORCE INDEX` 后仍回退全表说明是不想用而非不能用"。
答案与解析
先测量：依次算 `COUNT(DISTINCT LEFT(email, N))/COUNT(*)`，取达到目标（如全列选择性的 95% 以上）的最小 N，例如 N=12 时选择性 0.999。然后建 `KEY idx_email (email(12))`，索引体积约为全列的 `12/100`。
不可用的两个场景：① **覆盖索引**——叶页里只有前缀，无法返回完整 `email`，`SELECT email FROM t_user WHERE email = ?` 仍需回表取完整值；② **`ORDER BY` / `GROUP BY`**——前缀有序不等于全列有序，`ORDER BY email` 无法由该索引提供有序输入，会出现 `filesort`。
**错在哪**：只说"前缀索引省空间"，说不出它牺牲了覆盖与排序。**面试官追问**："前缀索引下 `email = 'a@b.com'` 精确查会错吗？" 答"不会错，只是命中的候选（前缀相同的）需要回表核对完整值，可能多读几行"。