二叉树、B树、B+树的区别详解

二叉树

一、是什么？
二叉树是每个节点最多有两个子节点（左/右子节点）的树结构，节点存储数据。常见类型包括二叉搜索树（BST）、平衡二叉树（AVL树）等。

二、解决什么问题
解决快速查找和排序问题，在有序数据中实现高效检索（时间复杂度O(log n)）。

三、应用场景

1. 内存中的数据结构（如HashMap的冲突解决）
2. 表达式解析（编译器语法树）
3. 简单排序算法（如堆排序）

---

B树

一、是什么？
B树是多路平衡查找树，每个节点可存储多个键和指针（通常节点大小=磁盘页），保持所有叶子节点在同一层。

二、解决什么问题
解决磁盘I/O效率低的问题：减少磁盘访问次数（通过单次读取更多数据），适用于文件系统和数据库索引。

三、应用场景

1. 文件系统（如NTFS、ReiserFS）
2. 非关系型数据库（如MongoDB索引）
3. 需要大量磁盘读写的场景

---

B+树

一、是什么？
B+树是B树的变种：所有数据存储在叶子节点，非叶子节点仅存键值，叶子节点通过指针链接形成有序链表。

二、解决什么问题

1. 进一步减少磁盘I/O（非叶子节点可存更多键）
2. 支持高效范围查询（叶子节点链表直接遍历）
3. 保证查询稳定性（所有查询路径长度相同）

三、应用场景

1. 关系型数据库索引（MySQL InnoDB）
2. 大数据存储引擎（HBase）
3. 需要范围查询的场景

---

核心区别对比

特性	二叉树	B树	B+树
节点结构	2个子节点	多子节点（平衡）	多子节点（平衡）
数据存储	所有节点存数据	所有节点存数据	仅叶子节点存数据
查询效率	O(log n)	O(log n)	O(log n)更稳定
范围查询	需回溯遍历	效率较低	直接链表遍历
磁盘I/O	高（节点分散）	较低	最低
应用场景	内存操作	文件系统	数据库索引

---

总结

1. 二叉树：内存操作高效，适合小规模数据
2. B树：平衡磁盘I/O，适合文件系统
3. B+树：
   • 数据库首选（范围查询+低I/O）
   • 叶子节点链表提升遍历效率
   • 非叶子节点无冗余数据，存储更紧凑

注意：JDK中的TreeMap使用红黑树（平衡二叉树），而数据库如MySQL索引使用B+树，两者选择取决于数据存储位置（内存vs磁盘）。