MySQL 为何采用 B+ 树？B+ 树与 B 树的区别是什么？

面试回答

MySQL InnoDB 的普通索引采用通常所说的 B+ 树结构，核心原因是数据库索引需要同时兼顾磁盘或页访问次数、等值查询、范围查询和顺序遍历。

B+ 树与 B 树的主要区别是：

• B 树的非叶子节点和叶子节点都可以保存数据记录；
• B+ 树的非叶子节点主要保存索引键和子页面指针，完整索引记录集中在叶子节点；
• B+ 树的叶子节点按照键值顺序连接，适合范围扫描；
• 由于非叶子节点不保存完整数据，同样大小的页面能够容纳更多目录项，树的扇出更大、高度更低。

InnoDB 默认索引页大小为 16KB。一次读取通常以页为单位，而不是只读取一个键。B+ 树通过较大的扇出，把大量数据组织在较少的层级中，查询通常只需要访问少量页面；定位到范围起点后，还可以沿叶子页顺序扫描，不必反复从根节点查找。

InnoDB 的聚簇索引叶子节点保存完整行数据，二级索引叶子节点保存二级索引键和主键值。通过二级索引查询非覆盖列时，需要先取得主键，再回到聚簇索引查找完整行，这就是常说的回表。

一句话总结

B+ 树让非叶子节点专注于导航，以更大的扇出降低树高，并把有序数据集中在相连的叶子节点中，因此既能减少页面访问，又适合范围查询和顺序扫描。

详细讲解

一、先明确：MySQL 文档中的 B-tree 与 B+ 树

MySQL 官方文档通常把 InnoDB 的普通索引统称为 B-tree 索引。在数据库实现和面试语境中，InnoDB 的这种索引组织通常被称为 B+ 树：

• 索引记录存放在叶子页；
• 非叶子页负责索引导航；
• 聚簇索引的叶子页保存行数据；
• 二级索引的叶子记录保存索引列和主键；
• InnoDB 同一层的索引页通过前后页指针双向连接；
• 叶子页中的索引记录有序，能够进行范围扫描。

因此，“MySQL 使用 B+ 树”通常是在描述 InnoDB 普通索引的具体组织特征；它不代表 MySQL 中所有索引都使用 B+ 树。

例如：

• InnoDB 普通索引使用 B-tree 类结构；
• 空间索引使用 R-tree；
• 全文索引有独立的倒排索引设计；
• InnoDB 还可能使用自适应哈希索引加速部分热点等值访问。

二、B 树是什么

B 树是一种多路平衡查找树。

“多路”表示一个节点可以拥有多个子节点，而不是像二叉查找树那样最多只有两个子节点。

一个简化的 B 树可以表示为：

                 [20 | 50]
                /    |    \
       [5 | 10]   [30 | 40]   [60 | 80]

B 树具有以下特点：

• 节点中的键有序；
• 一个节点可以保存多个键和数据记录；
• 非叶子节点也可以直接保存数据；
• 所有叶子节点通常处于同一层；
• 插入和删除后通过分裂、合并或旋转维持平衡。

查询 20 时，可能在根节点直接找到数据，不一定需要访问叶子节点。

三、B+ 树是什么

B+ 树也是多路平衡查找树，但它把导航结构和数据记录进一步分离。

一个简化的 B+ 树可以表示为：

                         [20 | 50]
                        /    |    \
                       /     |     \
        [5 | 10 | 20] [30 | 40 | 50] [60 | 80]
                ↔              ↔
          叶子页通过前后页指针双向连接

B+ 树具有以下典型特点：

• 非叶子节点主要保存键和子节点指针；
• 完整的数据记录集中在叶子节点；
• 所有查询最终都会到达叶子节点；
• InnoDB 同一层的索引页通过前后页指针双向连接；
• 适合从某个键开始连续读取一段数据。

需要注意，示意图中的分隔键可能同时出现在非叶子节点和叶子节点中。非叶子节点中的键用于导航，叶子节点中的索引记录才承载最终数据定位信息。

这里的双向链表连接的是索引页，并不是说整棵 B+ 树本身就是双向链表。整体结构仍然是一棵多路平衡树：树结构负责快速定位目标页；同层页面之间的 FIL_PAGE_PREV、FIL_PAGE_NEXT 指针负责前后遍历。单个索引页内部的记录则主要按键值顺序组成单向链表，并由页目录辅助查找。

四、B 树与 B+ 树的核心区别

不能简单得出“B+ 树在所有场景都比 B 树快”的结论。

如果整个数据结构都在内存中，而且只做等值查询，B 树可能在非叶子节点提前命中。但数据库索引更关心页面访问、范围扫描和批量读取，B+ 树的整体特性更适合这类负载。

五、为什么数据库关心页面访问次数

InnoDB 管理数据的基本单位是页，默认页面大小为 16KB。

查询一个索引键时，底层不是只从磁盘读取这个键对应的几个字节，而是把相关页面读入 Buffer Pool，再在页内查找。

因此，索引设计要尽量做到：

更少的树层级
        ↓
更少的页面访问
        ↓
更低的 I/O 和缓存查找成本

即使数据已经在 Buffer Pool 中，较低的树高仍然意味着更少的页面定位、Latch 竞争和 CPU 缓存访问。

所以分析 B+ 树时，不应只背诵时间复杂度 O(log N)，还要关注：

这个对数以多大的扇出为底，以及一次查询需要访问多少个页面。

六、扇出是什么

**扇出（Fan-out）是一个非叶子节点能够直接指向的子节点数量。**在 InnoDB 中，可以把它理解为：

一个非叶子索引页能够直接导航到多少个下层索引页。

例如，某个非叶子页保存了大量“索引值 + 子页面指针”目录项，并能够据此导航到约 1,000 个子页面，那么可以近似地说这个节点的扇出约为 1,000。

扇出不是整棵树的记录总数，也不是一个叶子页能够保存的行数。它描述的是单个非叶子节点向下一层分出的分支数量。

对于相同数量的数据，树高可以粗略理解为：

树高 ≈ log(扇出)(需要管理的页面数)

扇出越大，每增加一层能够覆盖的页面数增长得越快，因此管理相同数据量所需的层级通常越少：

扇出为 2：       2 → 4 → 8 → 16
扇出为 1,000：   1,000 → 1,000,000 → 1,000,000,000

这里的数字只用于说明增长速度。真实扇出会受到索引键长度、页面格式、记录头、页面填充率等因素影响。

七、B+ 树如何通过更大的扇出降低树高

假设一个非叶子页既保存键，又保存完整行数据，那么每个目录项会比较大，一个页面能够容纳的目录项就比较少。

如果非叶子页只保存：

索引键 + 子页面指针

每个目录项更小，同一个 16KB 页面就能容纳更多目录项，一个节点可以指向更多子页面。

由于单个目录项更紧凑，同一个页面可以保存更多目录项、指向更多子页面，这就是 B+ 树扇出更大的原因。

例如，仅用于理解数量级，假设一个非叶子目录项平均占用 16 字节，忽略页头、槽目录、填充率和其他开销：

16KB ÷ 16B ≈ 1024

一个非叶子页理论上可以导航约一千个子页面：

根节点：约 1,000 个分支
第二层：约 1,000 × 1,000 个分支
第三层：继续扩大

真实容量会受到键长度、页格式、记录头、填充率等因素影响，不能直接按这个示例计算生产容量。但它能说明：

多路树的扇出很大，少量层级就可以管理大量记录。

八、为什么 B+ 树适合范围查询

假设执行：

SELECT *
FROM orders
WHERE id BETWEEN 1000 AND 2000;

B+ 树可以先从根节点定位到 id=1000 附近的叶子页：

根页
  ↓
非叶子页
  ↓
包含 1000 的叶子页

定位范围起点以后，可以沿叶子页顺序扫描：

[1000 ... 1200] ↔ [1201 ... 1500] ↔ [1501 ... 1800] ↔ [1801 ... 2000]

不需要为范围中的每一条记录重新从根节点查找。

因此，B+ 树天然适合：

• >、>=、<、<=；
• BETWEEN；
• 有效前缀的 LIKE 'abc%'；
• 按索引顺序执行的 ORDER BY；
• 部分 MIN、MAX；
• 范围扫描和顺序分页。

能否真正使用索引顺序，还取决于联合索引结构、最左前缀、排序方向和执行计划，不能因为底层是 B+ 树就认为所有范围条件都会高效。

九、为什么不用二叉查找树或红黑树

二叉查找树和红黑树的扇出通常是 2。

即使红黑树能够保持近似平衡，管理大量数据时树高仍然明显高于多路树：

二叉树：
每个节点最多 2 个分支

B+ 树：
每个页面可以拥有数百甚至更多分支

如果每层节点可能位于不同页面，树越高，查询可能需要访问的页面越多。

红黑树很适合内存中的集合和映射，例如 Java 的 TreeMap；数据库索引需要尽量减少页面 I/O，并支持大范围顺序扫描，因此多路 B+ 树更加合适。

十、为什么不直接使用哈希索引

哈希结构擅长等值查询：

WHERE id = 100

理想情况下可以根据哈希值直接定位桶。

但哈希值不保留原始键的顺序，因此不适合：

WHERE id > 100;
WHERE id BETWEEN 100 AND 200;
ORDER BY id;
LIKE 'abc%';

哈希索引还需要处理哈希冲突，也无法自然支持联合索引的有序最左前缀扫描。

B+ 树虽然等值查找通常需要沿树下降，但同时支持：

• 等值查询；
• 范围查询；
• 顺序扫描；
• 排序；
• 联合索引前缀匹配。

因此它的通用性更强。

InnoDB 的自适应哈希索引可以为部分热点 B-tree 页面建立哈希访问路径，但它属于内部优化，不会替代原有 B+ 树索引。

十一、InnoDB 聚簇索引如何组织数据

每张 InnoDB 表都有一个聚簇索引。

聚簇索引的选择顺序通常是：

1. 显式定义的主键；
2. 第一个所有列均为 NOT NULL 的唯一索引；
3. InnoDB 自动生成的隐藏行 ID。

聚簇索引可以简化为：

非叶子节点：
主键 + 子页面指针

叶子节点：
主键 + 完整行数据

因此，通过主键查询：

SELECT * FROM users WHERE id = 100;

沿聚簇索引找到叶子记录时，通常已经取得了完整行数据。

这也是为什么官方文档把 InnoDB 表称为按聚簇索引组织的数据结构。

十二、InnoDB 二级索引如何组织数据

二级索引的叶子记录不直接保存完整行，而是保存：

二级索引列 + 主键值

假设存在：

CREATE INDEX idx_users_name ON users(name);

执行：

SELECT age
FROM users
WHERE name = 'Tom';

如果 age 不在二级索引中，查询过程通常是：

idx_users_name B+ 树
        ↓
找到 name='Tom' 对应的主键
        ↓
回到聚簇索引 B+ 树
        ↓
根据主键取得完整行和 age

这就是回表。

如果查询所需列都能从二级索引叶子记录中取得：

SELECT id
FROM users
WHERE name = 'Tom';

那么可能直接通过二级索引完成查询，不需要回到聚簇索引，这就是覆盖索引。

十三、为什么主键不宜过长

InnoDB 的每条二级索引记录都包含主键值。

如果主键很长：

每条二级索引记录更大
        ↓
一个索引页容纳的记录更少
        ↓
索引占用空间增加
        ↓
缓存命中率和扇出可能下降

因此，在满足业务要求的前提下，较短且稳定的主键通常更有利于 InnoDB 索引组织。

这并不意味着所有表都必须使用自增整数主键。是否采用自增 ID、分布式 ID 或业务主键，还要考虑写入热点、分库分表、数据合并和业务语义。

十四、叶子节点有序带来的其他收益

除了范围查询，叶子节点按键值有序还可以帮助：

• 按索引顺序输出数据，减少额外排序；
• 快速定位最小值和最大值；
• 连续读取相邻索引记录；
• 对联合索引执行最左前缀扫描；
• 利用页预读和 Buffer Pool 提高连续访问效率。

但“逻辑有序”不等于“所有叶子页在磁盘上永远物理连续”。页面分裂、删除、合并和长期更新都会产生碎片，页之间主要通过页号和链路维持逻辑顺序。

十五、B+ 树的写入代价

B+ 树并不是只有优点。

插入新记录时，需要先找到目标叶子页。如果页面空间不足，可能发生页分裂：

一个满页
   ↓
分裂为两个页
   ↓
更新父节点目录项

删除大量记录后，也可能触发页面合并或树结构收缩。

随机主键写入容易把数据分散到不同叶子页，可能带来：

• 更多随机页面访问；
• 页分裂；
• 页面利用率下降；
• Buffer Pool 压力增加。

顺序递增键通常更容易写入索引右侧页面，但高并发场景下也可能形成右侧热点。主键选择需要结合实际写入模式评估。

十六、常见误区

误区 1：MySQL 所有索引都是 B+ 树

不准确。这里主要讨论 InnoDB 的普通索引。空间索引、全文索引和内部自适应哈希索引采用不同结构或机制。

误区 2：B+ 树的所有数据都只存在叶子节点

需要区分“完整索引记录”和“分隔键”。非叶子节点也会保存用于导航的键，但完整索引记录集中在叶子节点。

误区 3：B+ 树一定比 B 树快

不一定。纯内存、单次等值查询中，B 树可能提前在非叶子节点命中。B+ 树的优势主要体现在页面扇出、稳定查询路径和范围扫描。

误区 4：使用 B+ 树后查询一定只需要三次 I/O

树高不是固定值，取决于页面大小、键长度、记录大小、填充率和数据量。页面还可能已经位于 Buffer Pool 中，因此树层访问次数也不能直接等同于磁盘 I/O 次数。

误区 5：建立索引就一定能提高性能

索引会占用空间并增加 INSERT、UPDATE、DELETE 的维护成本。低选择性索引、无法满足最左前缀的查询或返回大量数据的查询，也可能不使用索引。

十七、回答时可以怎样组织

面试时可以按照以下顺序回答：

先说结构差异
    ↓
再说数据库按页读取
    ↓
解释扇出更大、树高更低
    ↓
解释叶子节点有序，适合范围扫描
    ↓
结合 InnoDB 聚簇索引和二级索引

重点不是只说“B+ 树查询复杂度是 O(log N)”，而是说明：

InnoDB 通过页组织索引，B+ 树让一个非叶子页保存更多导航项，从而用较少层级管理大量数据；定位到叶子页后，又能沿有序叶子页完成范围扫描。

参考资料

• MySQL 8.4 Reference Manual：Clustered and Secondary Indexes
• MySQL 8.4 Reference Manual：The Physical Structure of an InnoDB Index
• MySQL 8.4 Reference Manual：Column Indexes
• MySQL 8.4 Reference Manual：Comparison of B-Tree and Hash Indexes
• MySQL 8.4 Reference Manual：File Space Management