目录
- AVL树、红黑树、b+树
- 比较：
- 简单比较：
- 一句话选型建议
- 核心差异总结
AVL树、红黑树、b+树
比较：
AVL树：要求任何节点的左右子树高度差不超过1。这非常严格，稍有倾斜就要立刻调整。avl树太严格了，插入或删除旋转调整太多，会慢，但是查询会快，因为高度底点。
红黑树：要求没那么苛刻，允许一侧比另一侧最多长2层（通过黑色节点数量来近似平衡）。红黑树层高，所以查慢一点，但是插入或删除旋转调整少，所以插入删除会快。红黑树层高，但是节约内存，维护简单点。内存里层高没事，主要是要快，要占用内存少，所以hashmap这种内存里的用红黑树
b+树：层少，就可以减少查找磁盘次数，所以MySQL的索引用b+树。但是维护麻烦，一个节点的大小固定，填不满就浪费内存了
简单比较：
AVL树：层少，高度差严格，插入或删除旋转调整太多，但是查询会快。
红黑：层高，节约空间，维护简单
b+树：层少，占空间，维护麻烦
一句话选型建议
- 内存、读多写少、对查询延迟要求极致 → AVL
- 内存、读写均衡、追求综合性能 → 红黑树（Linux内核、C++ STL map、Java HashMap）
- 磁盘、大量数据、需要范围查询 → B+树（MySQL InnoDB）
- 磁盘、点查为主、写少 → LSM树（RocksDB，但那是另一回事了）
核心差异总结
| 特性 | AVL树 | 红黑树 | B+树 |
|---|---|---|---|
| 平衡标准 | 高度差 ≤1（严格） | 黑色节点数平衡（宽松） | 多路搜索树 |
| 高度 | 最低 | 较高 | 最低（多叉） |
| 查询速度 | 最快 | 较快 | 快（但常数大） |
| 插入/删除 | 慢（旋转多） | 快（旋转少） | 中等（分裂/合并） |
| 适用场景 | 内存中读多写少 | 内存中读写均衡 | 磁盘存储（数据库） |
| 内存占用 | 较高（存平衡因子） | 较低（只需1位颜色） | 较高（节点大，有浪费） |