09 - 平衡树与 B 树：数据库为什么用它

上一章留了个尾巴：二叉搜索树会「长歪」，退化成链表，查找变慢。这一章讲两个「防止长歪」的进阶结构——平衡树和 B 树。它们是数据库索引背后的真正主角。这章只讲思想，不讲怎么旋转、怎么分裂那些细节。

平衡树：会自我「掰正」的搜索树

问题的根源是树左右不平衡（一边高一边矮）。平衡树的思路很直接：

在每次插入、删除后，检查树有没有变歪；一旦发现某边太高，就自动调整节点，把树重新「掰正」，始终保持左右两边高度差不多。

这样一来，树永远不会退化成长长的链子，查找就能稳定保持 O(log n)，不会掉到 O(n)。

你可能听过一些名字：AVL 树、红黑树。它们是平衡树的不同实现流派，区别只是「掰正」的规则和严格程度不同：

AVL 树：管得很严，时刻保持高度非常平衡，查得极快，但维护成本高（调整更频繁）。
红黑树：管得松一点，允许一定程度的不平衡，换来插入/删除时调整更少、更省心。实际工程中用得最广——很多语言的「有序 Map / Set」（如 Java 的 TreeMap）底层就是红黑树。

你不用记住旋转规则。记住这句就够：平衡树 = 会自动掰正、防止长歪的二叉搜索树，从而稳定保证 O(log n)。

B 树：为「硬盘」量身定做的树

平衡树很好，但它是为内存设计的。当数据量大到得存在硬盘上时（比如数据库有上亿条记录），又冒出一个新问题。

回忆组成原理/操作系统篇：硬盘比内存慢成千上万倍，而且硬盘每次读取都是「一大块一大块」地读（读一次的固定开销很大）。

在这种情况下，二叉树有个致命缺点：每个节点只有两个分叉，树会很高。而查找时每往下走一层，就可能要读一次硬盘。树太高 = 读硬盘次数太多 = 慢得要命。

B 树 / B+ 树的解决思路很聪明：

既然读一次硬盘就能拿一大块数据，那就让每个节点「胖」一点——一个节点里存很多个值、有很多个分叉（不止两个）。节点变胖，树就变得又矮又宽，查一个数据只需要读很少几次硬盘。

二叉树（瘦高，层数多，读硬盘多次）：
         [50]
        /    \
     [25]    [75]
     ...很多层...

B 树（矮胖，一个节点存很多值、多路分叉，读硬盘几次就到底）：
     [ 20 | 40 | 60 | 80 ]        ← 一个节点存好多值
    /    |    |    |     \
 [..] [..]  [..]  [..]  [..]       ← 分很多叉，树很矮

树越矮，从根到叶子经过的节点越少，读硬盘的次数越少，这在硬盘场景下是决定性的。
这就是几乎所有数据库（MySQL 等）和文件系统的索引都用 B+ 树 的原因。你在数据库里「加索引让查询变快」，底层就是建了一棵 B+ 树。

一条清晰的进化线

把这两章串起来，你能看到一条为「查得又快又稳」而不断进化的路线：

二叉搜索树  → 查找 O(log n)，但会长歪退化
     │  加「自动掰正」
     ▼
平衡树(红黑树) → 稳定 O(log n)，适合内存
     │  为了适配「慢速、按块读」的硬盘
     ▼
B / B+ 树  → 矮胖多叉，减少读硬盘次数，数据库索引的标配

每一步进化，都是为了解决上一个的短板。理解了这条线，你就理解了「为什么数据库要用 B+ 树而不是普通二叉树」——这是面试高频题。

小结

平衡树：在插入/删除后自动「掰正」，防止二叉搜索树长歪，稳定保证 O(log n)。
常见实现：AVL 树（管得严、查得快、维护贵）、红黑树（管得松、更省心、工程中最常用）。
B 树 / B+ 树：为硬盘设计。让每个节点存很多值、多路分叉，把树变得又矮又宽，从而大幅减少读硬盘次数。
数据库和文件系统的索引普遍用 B+ 树——这就是「加索引变快」的底层原理。
进化线：二叉搜索树 →（防长歪）平衡树 →（适配硬盘）B+ 树。

下一章 → 10 - 堆：怎么快速找到最大/最小｜回到 README 目录