外观
11 - B+ Tree 索引为什么适合数据库,而不是普通二叉树
摘要与阅读定位
按订单 ID 查一笔订单,与按状态查出九千笔订单,即使都能使用索引,工作量也可能相差很大。B+ Tree 用多路、有序的页结构缩短查找路径,但找到起点之后,数据库仍需读取候选记录,必要时再取完整行。本文先解释这套模型,再用独立样本比较不同查询路径和写入成本。
- 前置:02 页与缓冲;建模关联:03 主键与字段。
- 后续:12 联合索引字典序 → 14 执行计划证据 → 13 成本选择。
- 对比:算法 14 二叉搜索树解释内存有序不变量与树高,不把二叉树算法直接当作 InnoDB 实现。
- 基线:MySQL 8.0.16+ / 8.4、InnoDB;EXPLAIN ANALYZE 需 8.0.18+。按 A留证,下面不预设计划或耗时。
初次先读下面的五行查询、第 2 节的树形直觉和第 3 节回表模型。扇出公式、一万行构造、强制候选与写入性能对照可以第二遍再读,不是理解索引的前提。
从五行数据开始:索引保存的是查找线索
表保存订单记录,索引按键组织查找线索:键就是用于排序和查找的列值,例如订单 ID 或客户编号。按客户建立有序索引后,同一客户的索引记录集中在一个键范围中,数据库可以先找到这个范围,再读取其中的候选记录,无需每次逐行检查整张表。索引本身也占空间,新增、删除或修改相关数据时都要维护。
下面先验证三种查询的结果。在隔离实例、旧事务已明确结束的连接中执行;表已存在时停止并确认归属,不删除公共实验库:
sql
CREATE DATABASE IF NOT EXISTS kb_database_lab;
USE kb_database_lab;
SET autocommit = 1;
CREATE TABLE btree_basic (
id BIGINT PRIMARY KEY,
customer_id BIGINT NOT NULL,
amount DECIMAL(10, 2) NOT NULL,
KEY idx_btree_basic_customer (customer_id)
) ENGINE = InnoDB;
INSERT INTO btree_basic VALUES
(1, 10, 100), (2, 20, 50), (3, 10, 40), (4, 30, 70), (5, 10, 0);
SELECT id, customer_id, amount FROM btree_basic WHERE id = 3;
SELECT id, customer_id FROM btree_basic WHERE customer_id = 10 ORDER BY id;
SELECT id, amount FROM btree_basic WHERE customer_id = 10 ORDER BY id;预期结果:第一条是 (3,10,40);第二条 ID 为 1、3、5;第三条对应金额 100、40、0。这些结果可由插入数据推导;客户端可能把金额显示为 40.00 等带小数位的形式。
在这张 InnoDB 表中,主键索引按 id 组织完整记录,客户索引则保存 customer_id 和用于定位订单的主键 id。主键之外的这类索引称为二级索引。第二条查询只需要客户编号和 ID,客户索引已经能提供;第三条还需要 amount,若选择客户索引,就通常要拿找到的 ID 再去主键索引取金额,这一步叫回表。
因此,查询需要哪些列,会影响找到候选之后还要做多少工作。不过,小表也可能直接扫描整表;结果正确不能证明实际发生了回表,五行数据也不能证明哪种查询更快。
先带着这个区别读树结构,再用第 5 节的执行计划核对实际路径。
1. 现象:定位起点很快,扫描九千行仍可能很慢
第 4 节的样本有一万笔订单,其中九千笔状态为 PAID(已支付)。按 status 建立索引,可以快速找到已支付订单的起点,却不能省掉后面九千笔候选的读取;如果还要获取索引中没有的列,就可能增加大量回表访问。
这解释了“已用索引仍然慢”:定位起点和读取结果是两部分成本。命中范围很大时,直接扫描整表可能更便宜。优化器如何选择路径见 13,这里先理解每条路径要做的工作。
2. 原理:高扇出降低页访问层数
数据库把数据和索引组织在页中,读写和缓存都围绕这些页进行。可以把 B+ Tree 的一个节点理解为一页:最上层的根页是查找入口,中间的非叶子页负责指路,最下层的叶子页保存索引记录。
非叶子页中的分隔键划分各个子页负责的键范围,子页引用则告诉数据库下一步访问哪一页。查一个 ID 时,每经过一层就缩小一次范围,最后在叶子页中定位记录。二叉树一个节点最多分成两路;B+ Tree 一页能容纳许多分隔键和子页引用,因此一层可以分成很多路,这个路数称为扇出。相同记录规模下,扇出越大,通常需要的层数越少。
B+ Tree 保持所有叶子处于同一深度,通过维护树结构避免插入顺序把查找路径变成长链。叶子记录按键有序,叶子页之间也有相邻关系,因此范围查询找到起点后,可以继续读取后面的记录和页,无需为每个结果重新从根开始查找。多路查找降低层数,有序叶子支持范围访问,这两点共同使它适合数据库;维护这种结构仍有成本。
2.1 可选估算:页宽如何影响树高
二叉搜索树(BST)按键的大小选择左、右分支。若记录数为 N、树高为 h,查找复杂度为 O(h);平衡时是 O(log N),普通 BST 则可能退化为长链,达到 O(N)。数据库还要考虑节点分布在哪些页:若每个节点只能分成两路,且节点散布在许多页中,查找可能需要访问更多页。这是页访问模型下的比较,不能据此断定所有内存红黑树都有相同的磁盘成本。
B+ Tree 的非叶子页存分隔键与子页引用,叶子存完整索引记录并有逻辑相邻关系。给定可用页空间 U,非叶项平均宽度 K、指针与记录开销 P,粗略扇出 F≈U/(K+P);叶子容量 L≈U/叶子记录平均宽度。
教学估算:U=14 KiB、非叶项 32 字节则 F≈448;叶项 128 字节则 L≈112。三层树(根、中间、叶子)容量量级为 F²×L≈2248 万行。这不是 InnoDB 固定容量公式:填充率、分隔键长度、记录头、目录、页外值和分裂会改变 F/L。它只说明键和行宽为什么影响页数与缓存工作集。
text
点查:根定位 → 中间层 → 叶子页内定位
范围:定位起点 → 扫描叶子项 → 沿逻辑相邻页继续InnoDB 的页内查找也有自己的结构,并非把所有记录当成简单数组做二分:页目录中的槽指向记录组,先借助目录缩小范围,再在组内查找。叶子页在键顺序上相邻,不保证它们在存储设备上物理连续。
Buffer Pool 是 InnoDB 缓存数据页和索引页的内存区域。根页和中间页常在其中,命中缓存就不必从存储设备读取,所以访问三层树不等于发生三次物理 I/O。缓存和预读的边界见 02。
3. 聚簇、二级与覆盖:包含列不等于永远不读聚簇树
聚簇索引的叶子保存行内数据,因此沿这棵树找到叶子记录,就能获取行内业务列;较大的值可能还需要读取页外存储。InnoDB 每张表有一个聚簇索引,通常使用 PRIMARY KEY。没有主键时,选择首个所有列都为 NOT NULL 的 UNIQUE 索引;再没有符合条件的索引,就生成隐藏聚簇键。
二级索引按另一组列排序,叶子记录携带二级键和用于定位聚簇行的键。因此,二级索引中的定位键不是直接指向磁盘位置的行地址,回表还需要在聚簇索引中查找。聚簇键列若已经出现在二级键中,不需要再简单重复存一份。以第 4 节的客户与时间索引为例:
text
聚簇叶子:id + 行内业务列 + 记录/事务元数据
二级叶子:(customer_id,created_at) + 缺少的聚簇键列 id如果查询的过滤条件和返回列都能由选中的索引提供,就称为覆盖查询;覆盖是索引与具体查询的关系,不是一种独立的索引结构。相反,若需要的业务列不在二级索引中,就通常要回表获取,属于非覆盖查询。传统表格格式的执行计划中,覆盖查询常显示 Using index。
覆盖也有版本可见性的边界。MVCC(多版本并发控制)让事务按规则读取可见的数据版本;二级索引记录未必足以完成可见性判断,删除标记和旧版本重建等情况仍可能需要访问聚簇记录。因此,覆盖不能解释为“绝不访问聚簇树”。一致性读的版本规则见 18 MVCC。
把更多列加入二级索引,可以让更多查询得到覆盖,但也会使索引记录变宽:同一页容纳的记录减少,整个索引需要更多页,写入维护和缓存压力也可能增加。主键会作为定位键进入二级记录,因此主键宽度同样影响二级索引大小。这些存储成本也是 03选择主键和字段类型时的考虑因素。
4. 实现:一万行可重建数据,不依赖其他文章表
下面扩大样本,用于比较执行计划。同一张数字表使用四个别名,分别表示个位、十位、百位和千位;四次组合得到 0000—9999,再加一得到 ID 1—10000。这只是生成固定规模样本的方法,不是索引内部算法。
结束所有实验事务后,在隔离库初始化本篇 btree_* 表。下面的 DROP TABLE 会删除已有同名表,执行前确认它们仅用于本篇实验。四位十进制组合不依赖递归深度配置。
sql
CREATE DATABASE IF NOT EXISTS kb_database_lab;
USE kb_database_lab;
SET autocommit=1;
DROP TABLE IF EXISTS btree_order;
DROP TABLE IF EXISTS btree_digit;
CREATE TABLE btree_digit (digit INT PRIMARY KEY) ENGINE=InnoDB;
INSERT INTO btree_digit VALUES (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
CREATE TABLE btree_order (
id BIGINT PRIMARY KEY,customer_id BIGINT NOT NULL,
status VARCHAR(16) NOT NULL,amount DECIMAL(10,2) NOT NULL,
created_at DATETIME NOT NULL,payload VARCHAR(200) NOT NULL,
KEY idx_btree_customer_time (customer_id,created_at),
KEY idx_btree_status (status)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
INSERT INTO btree_order
SELECT num,MOD(num-1,100)+1,
CASE WHEN MOD(num-1,10)<9 THEN 'PAID' ELSE 'CANCELLED' END,
MOD(num,100),TIMESTAMPADD(MINUTE,num-1,'2026-09-01 00:00:00'),REPEAT('x',200)
FROM (
SELECT 1+ones.digit+10*tens.digit+100*hundreds.digit+1000*thousands.digit AS num
FROM btree_digit AS ones CROSS JOIN btree_digit AS tens
CROSS JOIN btree_digit AS hundreds CROSS JOIN btree_digit AS thousands
) AS seq;
SELECT COUNT(*) AS rows_count,MIN(id) AS first_id,MAX(id) AS last_id FROM btree_order;
SELECT status,COUNT(*) AS rows_count FROM btree_order GROUP BY status ORDER BY status;
ANALYZE TABLE btree_order;预期一万行、ID 1—10000,CANCELLED=1000、PAID=9000,每客户 100 行。ANALYZE TABLE 更新优化器用于估算数据分布的统计信息,可能改变后续计划;它属于管理操作,不在业务事务内执行。
5. 验证:同数据分别观察四种工作
下面四个计划依次观察:主键点查、客户索引覆盖查询、客户索引非覆盖查询,以及命中九成订单的状态查询。先区分它们需要的列和候选范围,再看优化器实际选择哪条路径。
sql
EXPLAIN FORMAT=TREE SELECT payload FROM btree_order WHERE id=5000;
EXPLAIN FORMAT=TREE
SELECT id,created_at FROM btree_order WHERE customer_id=1
ORDER BY created_at,id LIMIT 5;
EXPLAIN FORMAT=TREE
SELECT id,amount FROM btree_order WHERE customer_id=1
ORDER BY created_at,id LIMIT 5;
EXPLAIN FORMAT=TREE SELECT id,payload FROM btree_order WHERE status='PAID';
SELECT id,created_at FROM btree_order WHERE customer_id=1
ORDER BY created_at,id LIMIT 5;最后一条普通 SELECT 的结果 ID 预期为 1、101、201、301、401。前四条 EXPLAIN FORMAT=TREE 输出估算计划,不实际返回业务结果。主键点查应重点观察单行访问路径;覆盖与非覆盖要结合所选索引和返回列判断。若查看传统表格格式的 EXPLAIN,主键等值点查可能显示 const。PAID 查询可能选择全表扫描,不保证选中状态索引。
为了单独观察二级非覆盖候选,而不是证明其最优,可在实验库使用:
sql
EXPLAIN ANALYZE
SELECT id,amount FROM btree_order FORCE INDEX (idx_btree_customer_time)
WHERE customer_id=1 ORDER BY created_at,id LIMIT 5;
EXPLAIN ANALYZE
SELECT id,created_at FROM btree_order FORCE INDEX (idx_btree_customer_time)
WHERE customer_id=1 ORDER BY created_at,id LIMIT 5;
SHOW INDEX FROM btree_order;EXPLAIN ANALYZE 会实际执行 SELECT,并输出执行过程中的统计;FORCE INDEX 在这里用于限制候选路径,便于对照,不证明该路径最优。SHOW INDEX 的 Cardinality 表示估算的不同键值数量,不是本次查询命中的行数;传统 EXPLAIN 的 key_len 也不是实际行宽或树高。
外层 LIMIT 返回五行,不必然表示只扫描五条候选:若还要过滤或排序,上游可能已经处理更多记录。应继续检查过滤和排序的输入,统计边界见 14。
这个样本中,customer_id 与 status 相关:客户 1 的订单全是 PAID,客户 10 的订单全是 CANCELLED。因此不能把两个条件视为独立分布,实验记录应包含参数选择和这种相关性。缓存中已有多少相关页、数据规模、统计信息及并发都会影响性能,两次耗时差不能证明所有覆盖查询都更快。
6. 写入成本:顺序和随机都有代价
插入时先按键找到目标叶子页。页空间不足时,InnoDB 可能先整理页内空间;必要时把记录分配到更多页,并更新上层指路信息,这就是页分裂或扩展带来的维护工作。
随机键让插入位置分散,可能扩大工作集,也就是这段负载经常访问和修改的页集合。顺序插入的位置更集中,有利于重复利用缓存页,但并发写入也可能集中竞争最右侧叶子页。二级索引按自己的键排序,仍需分别维护。一次业务写入引起额外索引、日志等工作,称为写放大;只优化主键并不能消除它。
比较随机与顺序键时,应固定行数、键宽、二级索引、数据分布、每次事务提交的行数与并发,仅改变键的生成顺序。随机序列使用固定种子以便复现;记录导入期间页分裂计数增量、逻辑空间、日志量,以及写入延迟的 P95/P99(95%/99% 的观测值不超过的分位值)。InnoDB 指标是否启用、共享实例的背景写入及版本都会影响归因,缺少这些控制就不能得出“随机键一定慢 X 倍”的结论。
在分布式数据库中,连续主键还可能让新写入集中到同一个分片,形成分片热点;这是请求路由集中,与单机最右叶子页的内部并发竞争属于不同层次的问题。路由和热点取舍见 29 分库分表,具体产品的随机化策略需要按 30中的版本条件核验。
7. 排障与选型边界
| 现象 | 第一个问题 | 证据/后续 |
|---|---|---|
| 已用索引仍慢 | 扫描范围大还是回表多? | actual rows、loops、非覆盖列与 14 |
| 稀有/热点参数计划不同 | 命中比例与相关性是什么? | 13统计及成本 |
| 索引越来越大 | 聚簇键、二级键宽还是分裂空闲? | 02、03 |
| 范围读排序仍昂贵 | 联合键实际排序是否匹配? | 12字典序 |
| 范围写锁住更多行 | 实际访问哪个索引范围? | 19 锁 |
哈希结构把键映射到查找位置,适合等值查找;B+ Tree 还保留键顺序,因而能从一个起点继续做范围访问。InnoDB 自适应哈希是内部加速机制,不等于用户定义的普通哈希索引。
位图索引用位集合表示键值与行的对应关系,LSM(日志结构合并树)采用另一套组织和合并数据的方式;这些结构的可用性取决于具体产品,不能仅凭“不同值少”就建议在 MySQL 中建立位图索引。内存哈希与二叉树的取舍可对照 算法 04、算法 14。
清理前结束事务,在隔离库删除 btree_order、btree_digit、btree_basic。下一步 12把单一路径模型扩展为“范围、过滤、排序和覆盖”的四项设计。
8. 名词解释
| 名词 | 含义 |
|---|---|
| B+ Tree / 扇出 | 以多路有序页组织查找的树结构 / 一个非叶节点可以分出的子路数 |
| 根页 / 叶子页 | 查找从这里开始 / 保存完整索引记录、范围读取最终到达的层 |
| 聚簇索引 / 二级索引 | 叶子组织行数据的索引 / 携带其他键及聚簇定位键的索引 |
| 回表 / 覆盖 | 通过二级键继续获取聚簇记录 / 所需列能由选中索引提供,仍有可见性例外 |
| 页分裂 | 页空间不足等情况下重新分配记录并维护树结构,不只发生于随机键 |
| 工作集 | 某段负载经常访问的数据与索引页,影响缓存压力 |
| 写放大 | 一次业务写入引起额外索引、日志等工作,需要按具体口径计量 |
| FORCE INDEX | 对照候选访问的提示,不是所有查询都应强制索引的建议 |
参考资料
- MySQL 8.4 Reference Manual:Clustered and Secondary Indexes、InnoDB File Space Management、InnoDB Row Formats、InnoDB Multi-Versioning、EXPLAIN Statement。
- 适用条件:真实回表次数、树高与页分裂指标需在目标版本留证,不能由样本行数推断物理计数。