3.1.5 平衡二叉树

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