B+ 树与 B 树的区别，以及为什么数据库选 B+ 树

一、一个反直觉的结论

如果只看"查一个具体的值要几次 IO"，B+ 树没有优势，甚至可能更差：B 树的非叶子节点上就挂着数据，运气好走到第二层就命中了；B+ 树必须一路走到叶子节点才能拿到数据。

那为什么 MySQL 的 InnoDB 还是选了 B+ 树？

因为这个比较的前提就错了。数据库面对的不是"内存里比较两个数"，而是"从磁盘上读一个页"。理解了这一点，B+ 树的每一个设计选择都会变得顺理成章。

二、先搞清磁盘 IO 和页

数据库的存储介质是磁盘（或 SSD），它的读写单位不是字节，而是块。操作系统层面通常是 4KB，而 InnoDB 把逻辑上的读写单位定为 16KB，称为一个页（page）。

关键点在于：

读 1 个字节和读 16KB，在磁盘上的代价几乎一样。 因为寻道 + 旋转延迟占了大头。

于是设计目标就很明确了：尽量让每一次 IO 都"装满"有用的信息，同时尽可能减少 IO 次数。

树的高度 = 最坏情况下的 IO 次数。所以真正要优化的目标是：在存下同样多数据的前提下，让树尽可能矮。

为什么不用红黑树

红黑树是二叉的，高度约为 log2(N)：

数据量	红黑树高度	最坏 IO 次数
1 万	约 14 层	14
100 万	约 20 层	20
1 亿	约 27 层	27

每一层都是一次随机 IO。机械盘上一次随机 IO 大约 10ms，27 次就是几百毫秒，这个延迟对在线查询来说是不可接受的。二叉树的问题在于每个节点只能分出两个叉，扇出太小，数据量一大树就必然变高。

B 树和 B+ 树都是多叉树，一个节点就是一个页，能塞下几百上千个键，扇出从 2 变成上千，高度立刻塌下来。

为什么不用哈希表

哈希索引的等值查询是 O(1)，听起来很美，但它有三个致命缺陷：

不支持范围查询。WHERE id > 100 AND id < 200 在哈希表里等于全表扫描，因为哈希值之间没有顺序关系。
不支持排序。ORDER BY 需要额外一次排序。
不支持最左前缀。联合索引 (a, b) 上查 WHERE b = 1 完全用不了。

哈希表只在"只有等值查询"的场景有用，比如 Memory 引擎，或者 InnoDB 的自适应哈希索引（它只在 Buffer Pool 内部为热数据建哈希，且只加速等值查询，范围查询仍然走 B+ 树）。

三、B 树和 B+ 树的四个核心区别

对比维度	B 树	B+ 树
数据存储位置	数据既可以存在叶子节点，也可以存在非叶子节点	所有数据都存在叶子节点，非叶子节点只存键值做索引
叶子节点结构	叶子节点之间没有连接	叶子节点之间用指针连成链表
查询效率	数据分散在多层，需要在多个层级中查找，路径不稳定	数据只在叶子层，每次查询路径长度一致，且叶子有序链表支持高效范围查询
插入与删除	可能涉及叶子节点与非叶子节点之间的结构调整	调整通常只发生在叶子层，结构更稳定

下面逐条展开。

区别一：数据存在哪

B 树的每个节点都同时承担"存数据"和"当索引"两个职责。B+ 树做了分工：非叶子节点只负责导航，叶子节点负责存全部数据。

这个分工带来一个直接的后果——扇出（fan-out）的差距。

假设一行数据 1KB，主键 8 字节：

B 树：非叶子节点也要存数据行，16KB 的页大约只能放 16 条记录，扇出 ≈ 16。存 2000 万行需要 log16(2000万) ≈ 6 层。
B+ 树：非叶子节点只存"主键 + 页号"，大约 14 字节一条，16KB 的页能放约 1170 个键，扇出 ≈ 1170。

三层 B+ 树能存多少？假设每个叶子页放 16 行：

1170 × 1170 × 16 ≈ 2100 万行

同样是存 2000 万行，B 树要 6 层（6 次 IO），B+ 树只要 3 层（3 次 IO）。

这就是"扇出优势"：非叶子节点不存数据，同样的页能装更多键，树更矮，IO 更少。 而且 B+ 树最上面的 1~2 层通常长期驻留在内存（Buffer Pool）里，实际磁盘 IO 往往只有 1 次。

区别二：叶子节点的链表

B+ 树的所有叶子节点用双向指针串成一个有序链表：

[10, 20, 30] ⇄ [40, 50, 60] ⇄ [70, 80, 90]
     叶子页          叶子页          叶子页

B 树没有这个结构，叶子节点是彼此独立的。

区别三：范围查询

这是 B+ 树最实用的优势。看一条典型的 SQL：

SELECT * FROM orders WHERE id BETWEEN 1000 AND 2000;

B+ 树：先用树查找定位到 id = 1000 所在的叶子页，然后沿叶子链表顺序向右扫。整个过程只有第一次是随机 IO，后续都是顺序 IO。
B 树：数据分散在各个层级，范围查询需要中序遍历——在节点内扫描、下探子节点、回退、再下探，节点之间反复上下跳跃，随机 IO 数量成倍增加。

排序同理：

SELECT * FROM orders ORDER BY create_time LIMIT 20;

B+ 树在 create_time 索引上天然有序，走到最左叶子节点向后取 20 条即可；B 树则很难避免额外排序。

区别四：插入与删除

B+ 树的键值会冗余存在于非叶子节点和叶子节点中（非叶子节点的键只是路由用的路标）。这带来一个好处：

插入：新数据只进叶子层，非叶子节点只有在页分裂时才需要改路由键，不搬运数据。
删除：同理，删除只影响叶子层。

B 树因为非叶子节点也存真实数据，插入删除可能触发跨层级的节点合并与旋转，调整范围更大、更不稳定。

把四个区别串起来，其实是一句话：B+ 树牺牲了"非叶子节点也能命中"的小概率捷径，换来了更大的扇出、更矮的树、更稳定的路径和更好的范围查询能力。

四、B+ 树带来的一个"副作用"：回表

上面说的都是好处，现在说代价。

InnoDB 的 B+ 树索引分两种：

类型	叶子节点存什么	一个表有几个
聚簇索引（主键索引）	完整的行数据	1 个
二级索引（辅助索引）	索引列的值 + 主键值	0~N 个

在二级索引上查数据时，如果是 SELECT *，流程是：

在二级索引的 B+ 树里找到目标记录，拿到主键值
再拿主键值回到聚簇索引里查一次，取出行数据

第 2 步就是回表，本质是多走一次 B+ 树。

-- 假设 idx_name 是 name 上的二级索引

-- 需要回表：二级索引只能给出主键，其他列要回聚簇索引取
SELECT * FROM users WHERE name = 'lan';

-- 不需要回表（覆盖索引）：查询涉及的列都在索引里
SELECT id, name FROM users WHERE name = 'lan';

覆盖索引就是让查询需要的所有列都出现在索引中，从而跳过回表这一步：

-- 建一个包含三列的联合索引
ALTER TABLE users ADD INDEX idx_name_age_city (name, age, city);

-- 这三列都在索引上，直接从二级索引返回，无需回表
SELECT name, age, city FROM users WHERE name = 'lan';

五、三种结构的一次横向对比

结构	树高（1 亿数据）	等值查询	范围查询	排序	典型用途
红黑树	约 27 层	慢（27 次 IO）	支持但慢	支持	内存索引、`TreeMap`
哈希表	1 层	最快	不支持	不支持	等值缓存、`HashMap`
B 树	约 6 层	较快，路径不定	一般	一般	文件系统、部分 NoSQL
B+ 树	约 3 层	稳定	最优	天然有序	MySQL InnoDB

六、小结

数据库的性能瓶颈在磁盘 IO，而 IO 的单位是页（InnoDB 为 16KB），所以优化目标是让树变矮
红黑树扇出只有 2，1 亿数据要 27 层；哈希表虽然 O(1)，但不支持范围查询和排序
B 树与 B+ 树的四个区别：数据存储位置、叶子节点链表、查询效率、插入删除调整范围
B+ 树的非叶子节点不存数据只存键，扇出可达上千，3 层就能装下两千万行
叶子节点的有序双向链表让范围查询和排序只需一次随机 IO + 顺序扫描
代价是回表：二级索引只存主键，取其他列要多走一次聚簇索引，用覆盖索引可以规避

一句话记住：B+ 树不是"更快的查找结构"，而是"更省 IO 的存储结构"。 前者比的是比较次数，后者比的是磁盘寻道次数——而数据库只关心后者。