3.1.5 平衡二叉树
在上一讲中，我们讨论了二叉查找树为何无法胜任数据库索引。今天我们来深入平衡二叉树（Balanced Binary Tree）。它是对二叉查找树的高度控制版本，但即便如此，MySQL 依然没有把它作为磁盘索引结构，而是借鉴其“平衡”思想，发展出了 B+ 树。同时，平衡二叉树（尤其是红黑树）的变体很可能在 MySQL 内存管理、优化器等模块中发挥内作用。
⚖️ 一、平衡二叉树的本质
平衡二叉树是一类特殊的二叉查找树，它通过动态调整（旋转）保证左右子树高度差不超过某个阈值，从而将树高严格维持在 O(log₂N) 水平，避免退化成链表。
常见类型：
| 类型 | 平衡条件 | 调整方式 | 特点 |
|---|---|---|---|
| AVL 树 | 任何节点左右子树高度差 ≤ 1 | 旋转（LL、RR、LR、RL） | 严格平衡，查找极快，但插入删除旋转频繁 |
| 红黑树 | 节点分红黑色，满足色规（根黑、无连续红、黑高相同） | 变色+旋转 | 近似平衡（高度 ≤ 2log₂N），插入删除开销较小 |
关键性质：
- 高度为 O(log N)，百万数据树高约