第13章红黑树与B树

课程目录第13章红黑树与B树

第13章红黑树与B树：平衡之美与磁盘之友

说实话，红黑树和B树这两个东西，我当年学的时候也觉得挺头疼的。一个是在内存里玩得转，一个是在磁盘上吃得开。但等你真正理解了它们的本质，你会发现——嗯，其实没那么玄乎。

今天我们就来聊聊这两个“平衡”家族的重要成员。我会结合我这些年踩过的坑，给你讲明白。

红黑树的定义与性质

先说说红黑树。它本质上是一棵二叉搜索树，但每个节点多了一个颜色属性——红色或黑色。为什么要加颜色？说白了，就是为了保证树的平衡。

红黑树有5条性质，我建议你死记硬背下来：

每个节点要么是红色，要么是黑色
根节点是黑色
叶子节点（NIL）是黑色
红色节点的子节点必须是黑色（不能有两个连续的红色节点）
从任意节点到其每个叶子节点的路径上，黑色节点数量相同

核心理解：红黑树不是绝对平衡，而是“黑平衡”。它允许红色节点存在，但通过限制红色节点的出现方式，保证了最长路径不超过最短路径的2倍。

我在项目中遇到过一个问题：有人觉得红黑树太复杂，直接用AVL树替代。结果数据量大了以后，频繁的插入删除导致AVL树旋转太多，性能反而不如红黑树。你想想看，AVL树是严格平衡，红黑树是近似平衡，但红黑树的调整代价更低。这就是工程上的取舍。

红黑树的插入与调整

插入操作其实不复杂。先按二叉搜索树的规则插入，新节点默认涂成红色。然后根据情况调整。

调整分三种情况：

情况1：叔叔节点是红色。把父节点和叔叔节点变黑，祖父节点变红，然后继续向上调整。
情况2：叔叔节点是黑色，且当前节点是内侧插入。先旋转父节点，变成情况3。
情况3：叔叔节点是黑色，且当前节点是外侧插入。旋转祖父节点，变色。

我刚开始学的时候，总觉得这三种情况记不住。后来我总结了一个口诀：“红叔变色，黑叔旋转”。简单吧？

我的小技巧：写红黑树代码时，先把插入逻辑写好，再单独写一个fixUp函数处理调整。这样代码结构清晰，不容易出错。

来看一段插入的核心代码：

// 红黑树插入后的调整
void rb_insert_fixup(RBTree *T, RBNode *z) {
    while (z->parent->color == RED) {
        if (z->parent == z->parent->parent->left) {
            RBNode *y = z->parent->parent->right;  // 叔叔节点
            if (y->color == RED) {
                // 情况1：叔叔是红色
                z->parent->color = BLACK;
                y->color = BLACK;
                z->parent->parent->color = RED;
                z = z->parent->parent;
            } else {
                if (z == z->parent->right) {
                    // 情况2：内侧插入
                    z = z->parent;
                    left_rotate(T, z);
                }
                // 情况3：外侧插入
                z->parent->color = BLACK;
                z->parent->parent->color = RED;
                right_rotate(T, z->parent->parent);
            }
        } else {
            // 对称情况，左右互换
            // ... 类似逻辑
        }
    }
    T->root->color = BLACK;
}

我曾经踩过的坑：写红黑树删除的时候，忘记处理根节点变红的情况。结果调试了一整天，最后发现是fixUp循环结束后忘了把根节点涂黑。记住：不管怎么调整，根节点永远是黑色。

B树的定义与性质

好，聊完红黑树，我们来说说B树。B树不是二叉树，它是多路搜索树。为什么需要B树？因为磁盘IO太慢了。

你想想看，内存访问是纳秒级的，磁盘访问是毫秒级的。差了100万倍。红黑树虽然平衡，但每个节点只存一个键值，树的高度太高，每次查找都要多次磁盘IO。B树一个节点可以存几百个键值，树的高度大大降低。

B树的定义：

每个节点最多有m个子节点（m称为阶数）
除根节点外，每个节点至少有⌈m/2⌉个子节点
根节点至少有两个子节点（除非是叶子节点）
所有叶子节点在同一层
节点内的键值有序排列

我记得有一次做数据库索引优化，发现某个表的查询特别慢。一看B树的阶数设置得太小，导致树的高度达到了5层。调整阶数后，树高降到3层，查询速度提升了3倍。这就是B树的魅力。

B树的查找与插入

B树的查找很简单：从根节点开始，在节点内二分查找，找到就返回，找不到就进入对应的子树继续查找。

插入稍微复杂一点。核心思想是：先查找，再插入，满了就分裂。

具体步骤：

从根节点开始，找到要插入的叶子节点
如果叶子节点没满，直接插入
如果叶子节点满了，先分裂，把中间键值提升到父节点，然后插入
如果父节点也满了，继续向上分裂，直到根节点

关键点：B树的插入总是从叶子节点开始，然后向上分裂。这和红黑树的插入后向上调整有异曲同工之妙。

来看一个B树插入的示意图：

B树的插入代码实现：

// B树插入（简化版）
void btree_insert(BTree *T, int key) {
    if (T->root == NULL) {
        // 空树，创建根节点
        T->root = create_node();
        T->root->keys[0] = key;
        T->root->num = 1;
        return;
    }
    
    if (T->root->num == MAX_KEYS) {
        // 根节点满了，先分裂
        BNode *s = create_node();
        s->is_leaf = 0;
        s->children[0] = T->root;
        T->root = s;
        split_child(s, 0);
    }
    
    // 从根节点开始插入
    insert_nonfull(T->root, key);
}

我的建议：学习B树时，先用手工模拟几次插入过程。拿张纸，画个阶数为3的B树，一步步插入数据。你会发现，B树的分裂其实很有规律——中间键值上提，左右两边各成一子节点。

红黑树 vs B树：怎么选？

特性	红黑树	B树
适用场景	内存中的数据结构	磁盘/数据库索引
树的高度	O(log n)	O(log_m n)，m为阶数
节点存储	1个键值	多个键值
平衡方式	颜色+旋转	分裂+合并
典型应用	C++ STL map, Linux内核	MySQL InnoDB, 文件系统

说白了，如果你在写内存中的数据结构，比如实现一个关联容器，红黑树是首选。如果你在做数据库或者文件系统，需要处理大量磁盘IO，B树才是正确的选择。

我记得有一次面试，面试官问我：“为什么MySQL用B+树而不是红黑树？”我回答说：“因为磁盘IO太贵了，红黑树树高太高，每次查找都要多次IO。B+树一个节点可以存几百个键值，树高只有3-4层，IO次数大大减少。”面试官点了点头，说：“嗯，回答得不错。”

注意：B树和B+树是有区别的。B+树的所有数据都存储在叶子节点，内部节点只存索引。MySQL的InnoDB引擎用的是B+树，不是B树。这个区别很重要，面试经常考。

好了，红黑树和B树的核心内容就这些。这两种树都是平衡树的经典实现，一个面向内存，一个面向磁盘。理解了它们的设计思想，你就能在合适的场景下做出正确的选择。

记住：没有最好的数据结构，只有最合适的。红黑树和B树，各有各的用武之地。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录