Linux 內核紅黑樹實現詳解：核心數據結構與關鍵算法

為什麼選擇紅黑樹？

Linux 內核大量場景需要**有序、動態、查找/插入/刪除均為 O(log n)** 的數據結構：虛擬記憶體區域 (vm_area_struct)、文件描述符表、進程調度實體、定時器輪、epoll 就緒隊列等。紅黑樹作為自平衡二叉搜索樹，成為內核標準選擇。

核心數據結構 (include/linux/rbtree.h)

節點結構：巧妙的位域壓縮

struct rb_node {
    unsigned long  __rb_parent_color;  // 父指針 + 顏色 (低 2 位)
    #define RB_RED  0
    #define RB_BLACK 1
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

設計精妙處：利用結構體對齊 (sizeof(long))，指針低 2 位必為 0 → 低 1 位存顏色，低 2 位清零得父指針。

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3UL))
#define rb_color(r)    ((r)->__rb_parent_color & 1)
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)   do { (r)->__rb_parent_color &= ~1UL; } while (0)
#define rb_set_black(r) do { (r)->__rb_parent_color |= 1UL; } while (0)

樹根結構：避免二級指針

struct rb_root {
    struct rb_node *rb_node;
};
#define RB_ROOT (struct rb_root){ NULL, }

輔助宏與內聯函數

// 將 node 掛載到 parent 的 rb_link 位置 (rb_link 為 &parent->rb_left 或 &parent->rb_right)
static inline void rb_link_node(struct rb_node *node, struct rb_node *parent,
                                struct rb_node **rb_link)
{
    node->__rb_parent_color = (unsigned long)parent;
    node->rb_left = node->rb_right = NULL;
    *rb_link = node;
}

紅黑樹五大性質 (不變量)

1. 節點非紅即黑
2. 根節點為黑
3. 紅節點的子節點必為黑 (無雙紅)
4. 從任一節點到其子孫葉子 (NIL) 的所有路徑，包含相同數目的黑節點 (黑高一致)
5. 葉子 (NIL) 視為黑節點

→ 保證最長路徑 ≤ 2 × 最短路徑 → 高度 ≤ 2 log₂(n+1) → 操作 O(log n)

關鍵操作源碼剖析 (lib/rbtree.c)

旋轉操作 (內部使用)

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *right = node->rb_right;
    struct rb_node *parent = rb_parent(node);

    node->rb_right = right->rb_left;
    if (right->rb_left)
        rb_set_parent(right->rb_left, node);
    right->rb_left = node;

    rb_set_parent(node, right);
    rb_set_parent(right, parent);

    if (parent) {
        if (node == parent->rb_left)
            parent->rb_left = right;
        else
            parent->rb_right = right;
    } else {
        root->rb_node = right;
    }
}
// __rb_rotate_right 對稱

插入：rb_insert_color()

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *parent, *gparent;

    while ((parent = rb_parent(node)) && rb_is_red(parent)) {
        gparent = rb_parent(parent);

        if (parent == gparent->rb_left) {
            // 父節點是左孩子
            struct rb_node *uncle = gparent->rb_right;
            if (uncle && rb_is_red(uncle)) {
                // Case 1: 叔叔紅 → 重新著色
                rb_set_black(uncle);
                rb_set_black(parent);
                rb_set_red(gparent);
                node = gparent;
                continue;
            }
            if (node == parent->rb_right) {
                // Case 2: 內側插入 → 左旋轉父節點
                __rb_rotate_left(parent, root);
                node = parent;
                parent = rb_parent(node);
            }
            // Case 3: 外側插入 → 右旋轉祖父節點 + 重新著色
            rb_set_black(parent);
            rb_set_red(gparent);
            __rb_rotate_right(gparent, root);
        } else {
            // 父節點是右孩子 (對稱)
            ...
        }
    }
    rb_set_black(root->rb_node); // 根節點永遠為黑
}

關鍵點：新節點插入時著紅，僅通過 **著色調整 + 最多 2 次旋轉** 恢復平衡。調用前需手動遍歷找到父節點位置 (rb_link_node)。

刪除：rb_erase()

void rb_erase(struct rb_node *node, struct rb_root *root)
{
    struct rb_node *child, *parent;
    int color;

    // 1. 標準 BST 刪除：找到替代節點 (child)
    if (!node->rb_left)
        child = node->rb_right;
    else if (!node->rb_right)
        child = node->rb_left;
    else {
        // 兩個孩子都在：找後繼節點 (右子樹最小)
        struct rb_node *old = node, *left;
        node = node->rb_right;
        while ((left = node->rb_left) != NULL)
            node = left;
        // 將後繼節點內容複製到被刪節點 (僅指針操作)
        child = node->rb_right;
        parent = rb_parent(node);
        color = rb_color(node);

        if (child)
            rb_set_parent(child, parent);
        if (parent == old) {
            parent->rb_right = child;
            parent = node;
        } else {
            parent->rb_left = child;
        }
        // 複製節點指針 (不複製顏色/父指針)
        node->__rb_parent_color = old->__rb_parent_color;
        node->rb_left = old->rb_left;
        node->rb_right = old->rb_right;
        rb_set_parent(old->rb_left, node);
        rb_set_parent(old->rb_right, node);
        if (rb_parent(old)) {
            if (rb_parent(old)->rb_left == old)
                rb_parent(old)->rb_left = node;
            else
                rb_parent(old)->rb_right = node;
        } else {
            root->rb_node = node;
        }
        goto color_fixup;
    }

    // 2. 簡單情況：最多一個孩子
    parent = rb_parent(node);
    color = rb_color(node);
    if (child)
        rb_set_parent(child, parent);
    if (parent) {
        if (parent->rb_left == node)
            parent->rb_left = child;
        else
            parent->rb_right = child;
    } else {
        root->rb_node = child;
    }

color_fixup:
    // 3. 若刪除的是黑節點 → 破壞黑高 → 需修復
    if (color == RB_BLACK)
        __rb_erase_color(child, parent, root);
}

刪除修復：__rb_erase_color()

對應教科書 RB-DELETE-FIXUP，處理「雙重黑」問題，通過旋轉與著色將額外的黑高向上傳遞，直到根或遇到紅兄弟節點。核心案例：

• 兄弟為紅 → 旋轉父節點，轉化為兄弟為黑
• 兄弟為黑，且兩個侄子皆黑 → 兄弟染紅，父節點承擔雙重黑，向上遞歸
• 兄弟為黑，遠側侄子為紅 → 旋轉父節點 + 重新著色，修復完成
• 兄弟為黑，近側侄子為紅 → 旋轉兄弟節點，轉化為遠側侄子紅

遍歷與查找接口

rb_next 實現邏輯

struct rb_node *rb_next(struct rb_node *node)
{
    struct rb_node *parent;

    if (node->rb_right) {
        // 有右子樹 → 右子樹最左節點
        node = node->rb_right;
        while (node->rb_left)
            node = node->rb_left;
        return node;
    }
    // 無右子樹 → 向上找第一個「是父親左孩子」的祖先
    while ((parent = rb_parent(node)) && node == parent->rb_right)
        node = parent;
    return parent;
}

實戰範例：頁面緩存搜尋 (mm/filemap.c)

struct page *rb_search_page_cache(struct inode *inode, pgoff_t offset)
{
    struct rb_node *n = inode->i_rb_page_cache.rb_node;
    struct page *page;

    while (n) {
        page = rb_entry(n, struct page, rb_page_cache);
        if (offset < page->index)
            n = n->rb_left;
        else if (offset > page->index)
            n = n->rb_right;
        else
            return page; // 找到
    }
    return NULL; // 未找到
}

rb_entry 宏 (容器模式) 由 container_of 實現，從成員指針反推結構體地址。

內核中其他紅黑樹應用

• mm/mmap.c：mm_struct.mm_rb 管理 vm_area_struct (進程虛擬地址空間)
• kernel/sched/：CFS 調度器 cfs_rq.tasks_timeline (按 vruntime 排序)
• kernel/time/：高精度定時器 timerqueue (按過期時間)
• fs/epoll.c：eventpoll.rbr 管理就緒文件描述符
• net/socket.c：inode.i_rb 管理 socket inode

調試與可視化

# 內核配置開啟
CONFIG_DEBUG_RB_TREE=y  # 運行時檢查紅黑樹性質

# 用戶空間工具
gdb> p/x rb_root
gdb> call rb_validate(&rb_root)  # 若內核導出

# 靜態分析
scripts/check_rbtree.py  # 內核源碼自帶腳本