P23 B 树和 B+ 树的区别

面试题：B 树和 B+ 树的区别是什么？为什么 MySQL InnoDB 索引选 B+ 树？

一、结构区别

对比项	B 树	B+ 树
数据存放位置	每个节点都存数据（含叶子和非叶子）	只有叶子节点存数据，非叶子只存索引键
叶子节点	各自独立	叶子节点用链表串联（单向/双向），有序
查询方式	可能在中间节点就命中返回	必须走到叶子节点才能拿到数据
范围查询	需要中序遍历多次回溯	叶子链表直接顺序扫描
树高	数据分布在各层，树通常更高	非叶子只存键，一页能存更多键，树更矮
磁盘 IO	中间层也读数据，IO 次数更多	固定读叶子，IO 次数稳定

二、为什么数据库/MySQL 选 B+ 树

1. 树更矮，磁盘 IO 更少

数据库数据在磁盘上，一次 IO 读一个页（16KB）。B+ 树非叶子节点只存索引键（如主键 8 字节），一页能存上千个键，3 层就能覆盖千万级数据：

千万行数据 ≈ 3 次磁盘 IO（根 + 中间层 + 叶子）

2. 范围查询/排序高效

叶子节点用链表串起来且有序，范围查询（WHERE id BETWEEN ...、ORDER BY）只要找到起点，顺着链表顺序读即可；B 树则要反复回溯树节点，慢得多。

3. 查询性能稳定

B+ 树所有数据都在叶子层，每次查询都走到叶子，IO 次数固定（等于树高）；B 树有的查询在中层命中，有的要到叶子，波动大。

4. 缓存友好

非叶子节点小，可以全部/大部分常驻内存（Buffer Pool），实际查询时往往只读叶子页。

三、B 树也有适用场景

• MongoDB 等用 B 树（文档数据库更常做单键精确查找）；
• 内存数据库（数据全在内存，IO 不再是瓶颈）也可能用 B 树/跳表。

加分点

• 追问"为什么不用红黑树/哈希索引"：
  • 红黑树：内存结构，树高随数据量增长，磁盘 IO 多；B+ 树矮胖更适合磁盘；
  • 哈希索引：等值查询 O(1) 但不支持范围查询和排序，所以 InnoDB 默认 B+ 树（自适应哈希索引只是优化）。
• 追问"非叶子节点为什么不存数据"：正是为了一页多存键、降低树高。

一句话总结

B+ 树"非叶子只存键、叶子存数据并链表串联"：树更矮 IO 更少、范围查询直接走叶子链表、查询性能稳定，所以成为 MySQL 等磁盘数据库索引的首选。