红黑树的实现。

头文件：include/linux/rbtree.h（声明和宏）
实现文件：lib/rbtree.c（核心算法）

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 最低位存储颜色（0=红色，1=黑色），高位存储父指针。这种技巧节省了内存（一个指针同时存储父地址和颜色）。

rb_node 只包含树结构，实际数据通过 container_of() 或 rb_entry() 宏获取，实现了"侵入式"数据结构。

// 初始化
#define RB_ROOT (struct rb_root) { NULL, }
void rb_init_node(struct rb_node *rb);

// 插入（需要调用者实现比较逻辑）
void rb_insert_color(struct rb_node *rb, struct rb_root *root);

// 查找（需要调用者手写遍历逻辑）
#define rb_entry(ptr, type, member) container_of(ptr, type, member)

// 遍历
#define rb_first(root)  // 返回最左节点
#define rb_last(root)   // 返回最右节点
#define rb_next(rb)     // 返回后继节点
#define rb_prev(rb)     // 返回前驱节点

// 删除
void rb_erase(struct rb_node *rb, struct rb_root *root);

// 提取父指针（清除最低位）
#define rb_parent(rb) ((struct rb_node *)((rb)->__rb_parent_color & ~3))

// 获取颜色
#define rb_color(rb) ((rb)->__rb_parent_color & 1)

// 设置父节点
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
    rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
}

// 设置颜色
static inline void rb_set_black(struct rb_node *rb)
{
    rb->__rb_parent_color |= RB_BLACK;
}

实际性能：

插入 100 万个随机键值：约 2-3 秒（取决于硬件）
内存开销：每个节点额外 24 字节（64 位系统）

红黑树并发挑战：
    1.锁的粒度完全由调用者决定（通常保护整棵树）
    2.读操作也需要获取锁（除非额外实现 RCU 保护）
    3.插入操作可能触发重平衡（旋转），在锁保护下执行
    4.需要小心处理睡眠问题（如 kmalloc 在锁内可能睡眠）
           

尽管Xarray在许多新场景中表现优异，但这并不意味着红黑树（rbtree）会从内核中消失。它们是互补的数据结构，各有侧重：        

Xarray正在内核中逐步取代红黑树，尤其是在处理密集、连续ID（如索引、偏移量）的查找场景。但在键值随机、插入删除频繁且对内存分配失败零容忍的复杂场景下，红黑树依然是内核开发者首选的数据结构。