MySQLNotes

第 09 章：B+Tree 索引原理

zjc 于 2026-01-09 发布

这是《MySQL 零基础实战指南》的独立章节版。本章从概念、实操和生产排查三个视角展开，代码块保留了原书可直接运行的版本。 MySQL 的 InnoDB 索引是 B+Tree。理解 B+Tree，就能理解为什么主键要递增、为什么联合索引遵守最左前缀、为什么二级索引会回表、为什么范围查询可能影响排序。

9.1 为什么需要索引

没有索引时，查找一个订单只能全表扫描：

10 万行：最多比较 10 万次
1000 万行：最多比较 1000 万次

B+Tree 将有序数据按页组织，从根到叶逐层缩小范围。100 万行数据通常只需要几次页访问。

真实次数取决于行大小、页填充率、缓冲命中和数据分布，但数量级差异非常明显。

9.2 B+Tree 的结构

InnoDB 默认页大小为 16KB：

SHOW VARIABLES LIKE 'innodb_page_size';

B+Tree 结构：

Root Page
  |
  +-- Internal Page：只存键和子页指针
        |
        +-- Leaf Page：存索引键和行信息

同一层叶子节点之间用双向链表连接

特点：

  1. 非叶子节点只负责路由；
  2. 叶子节点保存全部键值；
  3. 叶子节点有序；
  4. 范围扫描可以沿链表继续读取；
  5. 树高通常为 2 到 4 层。

9.3 聚簇索引

InnoDB 表本身就是按主键组织的 B+Tree，称为聚簇索引。

PRIMARY KEY B+Tree
叶子节点：
  主键值 + 完整行数据

如果没有显式主键：

  1. 优先使用第一个非 NULL 唯一索引作为聚簇索引；
  2. 如果没有合适的唯一索引，InnoDB 生成隐藏的 ROW_ID。

隐藏 ROW_ID 不利于治理，业务表应显式定义主键。

主键查询

SELECT *
FROM orders
WHERE id = 1;

沿着主键 B+Tree 定位叶子页，直接拿到完整行，不需要回表。

9.4 二级索引

二级索引也称为辅助索引。它的叶子节点保存索引列和主键值：

INDEX(user_id, created_at)
叶子节点：
  user_id + created_at + id

查询：

SELECT *
FROM orders
WHERE user_id = 1001;

执行过程：

1. 在 idx_user_created 中定位 user_id=1001；
2. 从叶子节点拿到主键 id；
3. 回到主键索引查完整行；
4. 继续扫描直到 user_id 条件不满足。

第 3 步就是回表。若结果很多，回表成本会明显上升。

覆盖索引

SELECT id, user_id, created_at
FROM orders
WHERE user_id = 1001;

二级索引叶子已经包含 user_id、created_at 和主键 id，无需回表，执行计划通常显示 Using index。

覆盖索引不是一种独立语法，而是查询所需列恰好被索引包含的结果。

9.5 最左前缀原则

联合索引：

KEY idx_user_status_created (user_id, status, created_at)

可以支持：

user_id
user_id + status
user_id + status + created_at
user_id + status + created_at 范围

不能直接支持：

status
created_at
status + created_at

因为 B+Tree 先按 user_id 排序；只有 user_id 相同，才按 status 排序；只有前两列相同，才按 created_at 排序。

MySQL 8.0.13+ 有 Index Skip Scan，某些前导列取值很少的场景可以跳跃扫描，但不能把它当作通用设计依据。

9.6 索引列顺序与范围条件

联合索引 (a, b, c) 中：

WHERE a = 1 AND b = 2 AND c >= 10

通常 a、b 可以精确匹配，c 走范围。

WHERE a >= 1 AND b = 2

a 是范围后，b 在 B+Tree 全局有序性上无法继续精确定位。优化器仍可能使用 b 过滤，但效率取决于数据分布。

设计建议：

  1. 等值条件列放前面；
  2. 范围条件列尽量放后面；
  3. 排序列放在范围列之后要谨慎；
  4. 高选择性列优先，但要结合固定查询；
  5. 不要只看单列区分度，要看组合查询路径。

9.7 页分裂与页合并

页分裂

当一页写满后插入新行，InnoDB 会分配新页并移动部分记录：

原页 100% 满
  -> 分裂成两个约 50% 满的页
  -> 父节点增加路由项

随机主键会让新数据落在已有页之间，导致更多页分裂：

  1. 写入放大；
  2. 页空间利用率下降；
  3. 树高增长；
  4. Buffer Pool 命中率下降；
  5. 二级索引同样受影响。

趋势递增主键让新数据集中追加到最右侧页，分裂更少。

页合并

删除数据使页填充率低于阈值时，InnoDB 可能合并页：

低填充页 -> 与相邻页合并 -> 释放空页

删除大量数据后磁盘空间未必立刻返还给操作系统，通常以可复用页的形式留在表空间中。

9.8 索引基数与统计信息

查看索引基数：

SHOW INDEX FROM orders;

SELECT
  table_name,
  index_name,
  column_name,
  cardinality
FROM information_schema.STATISTICS
WHERE table_schema = 'shop'
  AND table_name = 'orders';

基数表示索引列不同值的估算数量。基数越高，通常选择性越好。

粗略选择性：

SELECT
  COUNT(DISTINCT status) / COUNT(*) AS status_selectivity,
  COUNT(DISTINCT user_id) / COUNT(*) AS user_selectivity
FROM orders;

注意：

  1. 基数是估算值；
  2. 低基数不等于索引一定没用；
  3. 状态列配合时间列可能有效；
  4. 高基数列也要匹配查询条件；
  5. 数据分布倾斜时平均值会误导判断。

更新统计信息：

ANALYZE TABLE orders;

MySQL 8.0 支持直方图，帮助优化器了解非索引列分布：

ANALYZE TABLE orders
  UPDATE HISTOGRAM ON status, merchant_id WITH 100 BUCKETS;

查看：

SELECT * FROM information_schema.COLUMN_STATISTICS
WHERE table_name = 'orders'\G

9.9 行格式与大字段

查看表行格式：

SELECT NAME, ROW_FORMAT
FROM information_schema.INNODB_TABLES
WHERE NAME LIKE '%/orders';

常见行格式：

格式 说明
COMPACT 传统紧凑格式
DYNAMIC MySQL 5.7+ 常用，长变长列可溢出
COMPRESSED 压缩行格式，需要评估 CPU 和页匹配

大字段可能存储在溢出页：

聚簇索引叶子保存前缀 + 指向溢出页的指针

影响：

  1. 单页可容纳行数减少；
  2. 索引树变高；
  3. 查询大字段增加随机 IO；
  4. 内存命中率下降。

大字段治理：

  1. 不查询不必要的 TEXT / BLOB；
  2. 高频字段和低频大字段分表；
  3. 图片和文件放对象存储；
  4. 历史详情归档；
  5. 使用覆盖索引避免读取大字段所在页。

9.10 Change Buffer

Change Buffer 用于二级索引写优化。当修改的二级索引页不在 Buffer Pool 中时，InnoDB 可以先把变更缓存起来，避免立即读入原索引页。

查看：

SHOW VARIABLES LIKE 'innodb_change_buffering';
SHOW ENGINE INNODB STATUS\G

适合：

  1. 二级索引多；
  2. 写多读少；
  3. 页不在内存概率高；
  4. 非唯一索引。

不适合：

  1. 唯一索引必须读取页判断唯一性；
  2. 写后马上读取；
  3. 索引页基本常驻内存；
  4. 高压场景需要简化不确定因素。

9.11 Adaptive Hash Index

InnoDB 会监控热点页访问模式，自动为热点索引页构建自适应哈希：

SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';
SHOW ENGINE INNODB STATUS\G

它不是用户可显式创建的哈希索引，也不是通用加速器。高并发读写下可能引入锁竞争，排障时可以谨慎关闭测试：

SET GLOBAL innodb_adaptive_hash_index = OFF;

生产修改全局参数必须评估影响范围并保留回滚方案。

9.12 主键为什么推荐 BIGINT AUTO_INCREMENT

常见理由：

  1. 趋势递增，减少随机插入和页分裂；
  2. 固定 8 字节，键比较简单；
  3. 二级索引叶子保存主键，主键越小越省空间；
  4. 便于范围划分、归档和游标分页；
  5. 便于监控自增水位。

随机 UUID 的问题：

  1. 插入位置随机；
  2. 空间占用更大；
  3. 缓存局部性差；
  4. 二级索引体积膨胀；
  5. 页分裂更多。

如果需要对外隐藏规律，可以保留内部递增主键，另建随机 public_id 唯一索引。

9.13 索引的代价

索引不是免费的：

操作 受影响
INSERT 每个索引都可能写入
UPDATE 修改索引列时更新索引
DELETE 标记删除并维护索引
磁盘 索引占用空间
内存 索引页竞争 Buffer Pool
优化器 候选索引越多选择越复杂
DDL 索引越多变更越慢
备份 数据文件更大

经验上，单表索引数量应控制在必要范围内，并为每个索引回答：

1. 支撑哪个查询；
2. 预计减少多少扫描；
3. 写入代价多少；
4. 是否能覆盖高频查询；
5. 未来是否可下线；
6. 由谁负责验证；
7. 由谁负责删除。

本章小结

InnoDB 的聚簇索引按主键组织完整行，二级索引叶子保存索引列和主键。B+Tree 的有序结构解释了最左前缀、范围扫描、回表、覆盖索引和页分裂。主键应尽量小且趋势递增，索引设计要同时考虑查询收益和写入、存储、DDL、内存成本。

思考题

  1. 为什么二级索引叶子节点保存主键而不是完整行地址？
  2. 覆盖索引为什么可以减少回表？
  3. 联合索引 (a,b,c) 为什么不能直接支持只按 c 查询？
  4. 随机 UUID 主键为什么会增加页分裂？
  5. 为什么索引数量不是越多越好？