结构体与红黑树：Linux内核中rbtree的实现、结构体嵌入

红黑树，这个名字听起来有点吓人。说实话，我当年第一次看到这玩意儿时，也觉得它是个高不可攀的数据结构。但后来我在Linux内核里跟它打了无数次交道，才明白——它其实就是一棵「自平衡的二叉搜索树」，只不过加了几条颜色规则。

今天我们就来聊聊，结构体是怎么跟红黑树结合在一起的。重点看Linux内核里rbtree的实现，以及那个非常关键的设计思路——结构体嵌入。

红黑树是什么？

红黑树是一种二叉搜索树，每个节点多了一个「颜色」属性：红色或黑色。它通过几条简单的规则，保证树的高度始终在O(log n)级别。你想想看，这意味着什么？意味着无论你怎么插入、删除，查找效率都不会退化。

它的核心规则就五条：

• 每个节点要么红，要么黑
• 根节点是黑色的
• 叶子节点（NIL）是黑色的
• 红色节点的子节点必须是黑色的
• 从任一节点到其每个叶子的所有路径，包含相同数量的黑色节点

嗯，规则看着多，但实际用起来，你根本不需要自己实现这些平衡逻辑。Linux内核已经帮你封装好了。

Linux内核rbtree的数据结构

先看核心结构体。Linux内核里，红黑树的节点定义在 include/linux/rbtree.h 中：

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root {
    struct rb_node *rb_node;
};

这里有个小细节：__rb_parent_color 这个字段，它同时存储了父节点指针和颜色信息。为什么能这么做？因为指针在Linux内核里是4字节或8字节对齐的，最低两位永远是0。内核就把颜色信息塞进了最低位。这种「位域复用」的技巧，我在做嵌入式内存优化时也经常用，能省不少空间。

结构体嵌入：核心设计思想

Linux内核的rbtree，跟教科书上最大的不同在于——它不存储具体数据。你想想看，内核要管理进程、文件、内存区域……这些数据类型各不相同，不可能为每种类型都写一套红黑树。

解决方案就是：把rb_node嵌入到你的结构体里。

举个例子，假设我们要管理一批缓存对象：

struct my_cache {
    u32 key;
    struct rb_node node;
    char data[256];
};

你看，rb_node 只是 my_cache 的一个成员。查找时，我们通过 rb_node 找到树节点，再通过 container_of 宏拿到整个结构体。

#define container_of(ptr, type, member) ({          \
    const typeof(((type *)0)->member) *__mptr = (ptr); \
    (type *)((char *)__mptr - offsetof(type, member)); })

说白了，就是拿成员的地址减去它在结构体中的偏移量。这个宏我几乎每天都在用，尤其是在写驱动的时候，从链表或树节点反查设备结构体，全靠它。

插入操作：从结构体到红黑树

插入一个节点，分两步走：先按二叉搜索树找到位置，再调用内核的插入函数做颜色调整。

int my_cache_insert(struct rb_root *root, struct my_cache *cache)
{
    struct rb_node **new = &(root->rb_node), *parent = NULL;

    while (*new) {
        struct my_cache *this = container_of(*new, struct my_cache, node);
        parent = *new;

        if (cache->key < this->key)
            new = &((*new)->rb_left);
        else if (cache->key > this->key)
            new = &((*new)->rb_right);
        else
            return -EEXIST;  // 键已存在
    }

    rb_link_node(&cache->node, parent, new);
    rb_insert_color(&cache->node, root);
    return 0;
}

这里有个坑，我曾经踩过：rb_link_node 只是把节点挂到树上，不会做平衡调整。平衡操作是 rb_insert_color 完成的。如果你只调了 rb_link_node 忘了调 rb_insert_color，那树就乱套了。

查找操作：从红黑树到结构体

查找就简单多了，沿着树往下走就行：

struct my_cache *my_cache_find(struct rb_root *root, u32 key)
{
    struct rb_node *node = root->rb_node;

    while (node) {
        struct my_cache *cache = container_of(node, struct my_cache, node);

        if (key < cache->key)
            node = node->rb_left;
        else if (key > cache->key)
            node = node->rb_right;
        else
            return cache;
    }
    return NULL;
}

你看，查找过程完全不涉及颜色信息。红黑树的平衡性只保证树的高度可控，查找逻辑跟普通二叉搜索树一模一样。

删除操作：稍微复杂一点

删除节点，内核提供了 rb_erase 函数。它会处理所有情况，包括节点有两个子节点时的替换逻辑。

void my_cache_erase(struct rb_root *root, struct my_cache *cache)
{
    rb_erase(&cache->node, root);
    // 注意：rb_erase 不会释放内存，你需要自己 free
}

遍历红黑树

内核提供了 rb_first、rb_next 等辅助函数，用于中序遍历：

void my_cache_print_all(struct rb_root *root)
{
    struct rb_node *node;

    for (node = rb_first(root); node; node = rb_next(node)) {
        struct my_cache *cache = container_of(node, struct my_cache, node);
        printk("key: %u\n", cache->key);
    }
}

中序遍历的结果，就是按键值从小到大排列。这个特性在很多场景下非常有用，比如需要按顺序输出日志或统计信息时。

知识结构图

下面这张图，帮你理清结构体与红黑树的关系：

实际项目中的经验

我在做嵌入式网络设备时，用红黑树管理大量会话连接。每个连接就是一个结构体，里面嵌了 rb_node。按连接ID做key，查找速度非常快。

有几个经验分享给你：

• key的选择要谨慎：红黑树是按key排序的，如果你用随机数做key，树会偏平衡。如果用递增ID，树会偏右，但红黑树会自动调整，问题不大。
• 不要频繁插入删除：虽然红黑树平衡效率是O(log n)，但每次插入删除都有颜色调整和旋转操作。如果数据量不大（比如几十个），用数组加二分查找反而更快。
• 注意并发访问：Linux内核的rbtree本身不是线程安全的。多核环境下，你需要加锁或使用RCU机制。我见过一个bug，两个核同时插入节点，结果树结构被破坏，查了半天才发现是没加锁。

总结

结构体嵌入是Linux内核里非常优雅的设计。它让红黑树这种通用数据结构，能够跟任意自定义类型结合，而不需要侵入式的继承或泛型。你只需要在自己的结构体里放一个 rb_node，然后用 container_of 来回转换就行。

我个人觉得，理解了这个设计思路，你再看内核里其他数据结构（链表、哈希表、基数树）都会豁然开朗。它们用的都是同一套模式——结构体嵌入 + container_of。

嗯，红黑树的内容就聊到这儿。代码我已经贴出来了，建议你找个Linux环境，自己动手写个demo跑一跑。光看是记不住的，亲手敲一遍，印象才深。