约 2122 字
B树与B+树 核心原理、完整区别、数据库选型原因
B树（多路平衡查找树）与 B+树（B树的优化变种）是磁盘数据库、索引结构的核心底层数据结构。MySQL、InnoDB、文件系统均采用 B+树而非 B树，核心原因是 B+树更适配磁盘IO特性。本文用通俗语言、对比维度、场景差异，彻底讲透二者区别。
一、前置核心认知
1. 二叉树、AVL、红黑树不适合磁盘存储：树层高、IO次数多，磁盘寻道开销极大；
2. B/B+树是多路平衡树，矮、胖、层数极少，最大限度减少磁盘IO；
3. 磁盘读写最小单位是 页（Page），InnoDB 默认一页 16KB，B+树节点与磁盘页对齐。
二、B树（多路平衡查找树）原理
核心特点：所有节点都存【索引key + 数据data + 子节点指针】
- 非叶子节点：存key、数据、子节点指针，可直接命中数据
- 叶子节点：同样存储完整key和数据，所有叶子节点无有序链表连接
- 平衡性：所有叶子节点高度一致，天然平衡
- 查找规则：从根节点逐层比对key，命中即返回，无需走到叶子
致命缺点：每个节点存储数据，单页存储key数量少 → 树层高变高 → 磁盘IO变多，范围查询极差。
三、B+树（增强多路平衡树）原理
核心特点：非叶子只存索引，叶子存全部数据 + 有序双向链表
- 非叶子节点（索引层）：只存key和子节点指针，不存data数据，仅用于路由检索
- 叶子节点（数据层）：存储全部key + 完整数据，整棵树所有数据都在叶子
- 有序链表：所有叶子节点按key从小到大串联成双向链表
- 平衡性：全程平衡，树高极低
核心优势：索引节点极小、存储key极多、树高极低、范围查询无敌。
四、B树与B+树 全方位核心区别（重点）
| 对比维度 | B 树 | B+ 树 |
|---|---|---|
| 数据存储位置 | 非叶子、叶子节点都存数据 | 仅叶子节点存数据，非叶子只存索引key |
| 单节点存储容量 | 小（存数据占用大量空间） | 极大（只存key，一页可存成千上万个索引） |
| 树的高度 | 较高 | 极低（千万级数据仅3~4层） |
| 单点查询IO | 可能更快（中途命中） | 略慢（必须走到叶子节点） |
| 范围查询能力 | 极差，需要多次遍历、回溯 | 极强，叶子链表直接遍历，无需回溯 |
| 叶子节点结构 | 无序、无链表连接 | 有序双向链表串联 |
| 重复key处理 | 分散存储 | 非叶子冗余存储，叶子唯一完整存储 |
| 磁盘IO效率 | 低，树层高、IO次数多 | 极高，树层极低、预读命中率高 |
| 适配场景 | 少量单次查询、内存索引 | 数据库索引、文件系统 |
五、关键细节深度解读（面试高频）
1. 为什么 B+树 树高极低？
B树每个节点要存【key+数据+指针】，数据占用空间大，一页能存的key数量少；
B+树非叶子节点只存key和指针，无数据冗余，单页可存储数千个索引key，分支度极大，树被压得极矮。
举例：16KB页，key为8字节主键，千万级数据 B+树仅需3层，最多3次磁盘IO即可查到数据。
2. 为什么数据库需要范围查询？
SQL 中 between、>、<、like、order by 全是范围查询：
- B树：范围查询需要中序遍历，频繁回溯上层节点，IO爆炸
- B+树：找到起始叶子节点，直接顺着链表向后遍历，一次IO批量读取
3. B树单点查询真的更快吗？
理论上是：B树非叶子可直接命中返回，不用走到叶子；
但工程上几乎无影响：
- B+树树高极低，多走一层开销可忽略
- 数据库90%场景是范围查询，单点查询优势完全被抵消
4. B+树磁盘预读性更好
磁盘局部性原理：读取一页数据时，系统会预读后续页。
B+树叶子节点有序连续，预读命中率极高；B树数据分散，预读基本失效。
六、总结：为什么 MySQL 选 B+树而不是 B树？
- 树高更低，磁盘IO更少：非叶子不存数据，索引密度极高；
- 完美支持范围查询、排序、分页：叶子链表结构天然适配SQL场景；
- 磁盘预读效率高：有序连续存储，贴合磁盘局部性原理；
- 查询性能稳定：所有查询最终都走叶子节点，时间复杂度统一；
- 增删更稳定：数据仅在叶子变动，非叶子索引调整开销小。
七、极简面试背诵版
B树：所有节点存数据，树层高、IO多、范围查询弱，适合纯单点查找。
B+树：非叶子只索引、叶子存数据且链表串联，树极矮、IO极少、范围查询无敌，是数据库索引最优解。