06. 平衡二叉树与 B+ 树数据库索引机制
💡 交互图解
本章理论对应的动态微观仿真位于：👉 CS 10 图全屏走查 · FIG 09 平衡树旋转变色 与 FIG 10 B+ 树分裂与范围扫描
1. 从二叉查找树的退化说起
普通的二叉查找树（BST）在输入有序或近似有序的数据时（如依次插入
为了解决这一问题，诞生了以旋转与重平衡为核心的两大经典二叉平衡树体系：
- AVL 树（Adelson-Velsky and Landis）：以严格高度差保持完全平衡；
- 红黑树（Red-Black Tree）：以颜色与黑高约束保持统计意义上的弱平衡。
2. AVL 树与四种旋转平衡动作
每个节点维护一个平衡因子（Balance Factor,
AVL 树要求任何节点的
3. 红黑树的五大公理与变色决策树
红黑树放弃了 AVL 的严格高度平衡，引入节点着色规则：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色的；
- 每个叶子节点（NIL 哨兵空节点）是黑色的；
- 如果一个节点是红色的，则它的子节点必须全为黑色（不能出现连续红节点）；
- 从任一节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点（黑高平衡，Black Height）。
红黑树核心性质：从根到叶子的最长可能路径（红黑交替）不会超过最短路径（全黑）的 2 倍。树高至多为
。
插入修复核心决策表
新插入节点默认着为红色。若其父节点为黑色，直接插入完毕无需修复；若父节点为红色（违反性质 4）：
| 情况 (Case) | 判定条件 | 修复动作 |
|---|---|---|
| Case 1 | 叔叔节点也是红色 | 纯变色：父节点与叔叔节点变黑，祖父节点变红；将当前节点指针移到祖父，继续向上回溯检查 |
| Case 2 | 叔叔是黑色，当前是右孩子（内侧） | 先局部单旋：将当前节点左旋，转变为 Case 3 |
| Case 3 | 叔叔是黑色，当前是左孩子（外侧） | 旋转 + 变色：父节点变黑，祖父变红，对祖父右旋！彻底恢复平衡，终止修复！ |
4. 为什么数据库（MySQL InnoDB）必须选择 B+ 树？
如果把红黑树或 AVL 树直接搬到磁盘上做数据库索引，一个拥有 2000 万行的表，二叉树的高度约为
B+ 树打败 B 树的决定性优势
- 极其巨大的扇出（High Fanout）与极矮的树高：
- 非叶子节点不存储真实数据行，只存主键索引和 6 字节指针。
- 设主键为
BIGINT(8B)，指针 6B，一个 16KB 的数据页能容纳个分支指针！ - 高度为 3 的 B+ 树就能索引
条记录！千万级数据仅需 2~3 次磁盘 I/O。
- 底层双向有序链表，让范围查询（BETWEEN / > / < / ORDER BY）彻底起飞：
- 在 B 树中做范围查询必须在整棵树的各个高度间来回回溯（中序遍历）；
- 而在 B+ 树中，仅需树上走访一次定位到下界叶子页，接下来沿着底部双向链表顺藤摸瓜顺序读，天然利用磁盘顺序预读能力（Read-Ahead），极大减少随机 I/O！
5. 生产级选型：B+ 树 vs LSM-Tree
| 维度 | B+ 树 (InnoDB / PostgreSQL) | LSM-Tree (RocksDB / ClickHouse / HBase) |
|---|---|---|
| 读性能 | ⭐⭐⭐⭐⭐ | ⭐⭐⭐ 读放大（需并发查 MemTable + 多层 SSTable + 布隆过滤器） |
| 写性能 | ⭐⭐⭐ 随机写导致页分裂与磁盘随机写入 | ⭐⭐⭐⭐⭐ 顺序追加写极快（全写内存 MemTable + 顺序 WAL 日志） |
| 写放大 | 相对较高（修改 1 个字节也需刷回 16KB 脏页） | 异步 Compaction 会带来写放大，但被平摊在后台 |
| 适用场景 | 传统事务 OLTP、关系型核心数据库、强一致点查 | 海量日志写入、时序监控、大数据指标追加采集 |