B 树和 B+ 树的区别

一、B 树

多路平衡搜索树： - 每个节点存 key + data。 - 子节点数 = key 数 + 1。 - 所有节点都存数据。

[10|20|30]
 /   |   \
[1-9][11-19][21-29][31-39]

二、B+ 树（MySQL 用）

• 非叶子节点只存 key，不存 data。
• 数据都在叶子节点。
• 叶子节点用链表连接。

[10|20|30]
 /   |   \
[1-9][11-19][21-29][31-39]
 ↓    ↓      ↓      ↓
链表连接

三、对比

	B 树	B+ 树
数据位置	所有节点	仅叶子
非叶子	key + data	只 key
叶子链表	无	有
范围查询	中序遍历	沿链表扫
单节点扇出	小	大（非叶子不存 data）
树高	高	低

四、为什么 MySQL 用 B+ 树

1. 矮胖：非叶子不存 data，一个页能存更多 key，树更矮，IO 更少。
2. 范围查询快：叶子链表，不用回溯。
3. 查询稳定：数据都在叶子，每次查询路径长度相同。

五、为什么不用红黑树

• 树太高，IO 次数多。
• 磁盘 IO 是瓶颈，要减少访问次数。

面试要点

B+ 树就是为磁盘设计的：矮、范围快、稳定。