这是《MySQL 8.0 源码与内核实战》的独立章节版。本章从概念、实操和生产排查三个视角展开，代码块保留了原书可直接运行的版本。 InnoDB 索引本质是 B+Tree。聚簇索引叶子包含完整行记录，二级索引叶子包含索引列和主键。
14.1 结构
root
internal node
leaf page
leaf page
特点：
- 数据按 key 有序；
- 叶子节点通过双向链表连接；
- 内部节点存子页指针；
- 根页固定，可缓存；
- 查找复杂度与树高相关；
- 三层 B+Tree 通常可支撑大量行。
14.2 查找
root
-> choose child by key
-> internal page
-> leaf page
-> page directory binary search
-> record
源码入口：
btr_cur_search_to_nth_level
btr_pcur_open
row_search_mvcc
断点：
b btr_cur_search_to_nth_level
14.3 插入
locate leaf
-> check space
|-- enough: insert record
+-- not enough: split page
-> update parent
-> maybe split upper level
分裂要点：
- 选择分裂点；
- 复制记录到新页；
- 更新兄弟链表；
- 更新父节点；
- 写 MTR redo；
- 维护锁和 latch。
14.4 更新与删除
主键更新通常等价于删除旧记录并插入新记录，可能引起二级索引维护。
删除流程：
delete-mark record
-> commit later
-> purge physically remove
因此大量 DELETE 后文件不一定立即缩小，purge 和页合并滞后会造成空间碎片。
14.5 二级索引回表
CREATE TABLE orders(
id BIGINT PRIMARY KEY,
user_id BIGINT,
amount DECIMAL(10,2),
KEY idx_user(user_id)
) ENGINE=InnoDB;
SELECT * FROM orders WHERE user_id=100;
路径：
idx_user leaf
-> get PK id
-> clustered index lookup
-> return full row
若只查 user_id 和 id，可覆盖索引避免回表。
14.6 页合并
删除或页分裂后，InnoDB 可能合并低填充率页：
page fill below threshold
-> check sibling
-> merge records
-> update parent
-> free page
影响合并的因素：
- 页填充率；
- 兄弟页状态；
- latch 争用；
- 后台时机；
- 索引访问模式。
14.7 索引统计
B+Tree 统计会估计：
- 索引基数；
- 不同 key 数；
- 树高；
- 页数量；
- 记录数。
刷新：
ANALYZE TABLE orders;
统计不准时，连接顺序和索引选择可能异常。
14.8 观测
SHOW INDEX FROM orders;
EXPLAIN FORMAT=TREE SELECT * FROM orders WHERE user_id=100;
SELECT SPACE, NAME, N_ROWS, PAGE_SIZE
FROM information_schema.innodb_tables
WHERE NAME='test/orders';
14.9 常见问题
| 现象 | 原因 |
|---|---|
| 插入随机 key 导致页分裂 | 单调主键更友好 |
| 删除后空间不释放 | delete mark + purge |
| 二级索引查询慢 | 大量回表 |
| 索引失效 | 条件、类型、统计 |
| 二级索引变大 | 主键过长 |
| 索引维护慢 | 索引过多 |
本章小结
B+Tree 是 InnoDB 有序存储的核心。查找依赖页内二分和树内导航，插入可能触发分裂，删除先标记再由 purge 清理。二级索引回表和页分裂是理解索引性能的关键。
思考题
- 为什么二级索引叶子保存主键？
- 页分裂如何影响写入性能？
- DELETE 后空间为什么不会立即释放？
- 覆盖索引如何减少 IO？
- 主键过长对二级索引有什么影响？