Linux 核心的紅黑樹

本頁由 steven1lung, linD026, jserv 貢獻

red-black tree (以下簡稱 rbtree 或紅黑樹) 是一種特別的自平衡樹，不僅其新增、移除、搜尋的時間複雜度均維持在 $O(\log n)$，而樹高 (tree height) 的定義與尋常平衡樹不同 (紅黑樹用的是 black height)，後者使其重新平衡所需的時間成本較其他平衡樹小。

black height 的定義是，對於 bh(x)，從 x 到任何一個它後代到末端 (即 leaf) 節點的路徑上，遇到的標註為「黑」的節點個數 (不含自身)。

Linux 核心原始程式碼中，許多地方出現紅黑樹的蹤影，例如：hr_timer 使用紅黑樹來記錄計時器 (timer) 端發出的要求、ext3 檔案系統使用紅黑樹來追蹤目錄內容變更，以及於 Linux 預設 CPU 排程器 (CFS 和 EEVDF) ，由於需要頻繁地插入跟移除節點 (任務)，因此開發者選擇用紅黑樹 (搭配一些效能調整)。VMA（Virtual Memory Area）也用紅黑樹來紀錄追蹤頁面 (page) 變更，因為後者不免存在頻繁的讀取 VMA 結構，如 page fault 和 mmap 等操作，且當大量的已映射 (mapped) 區域時存在時，若要尋找某個特定的虛擬記憶體地址，鏈結串列 (linked list) 的走訪成本過高，因此需要一種資料結構以提供更有效率的尋找，於是紅黑樹就可勝任。

延伸閱讀: Red-black Trees (rbtree) in Linux

為何不選擁有同樣時間複雜度性質、同為 $O(\log n)$ 的 AVL tree 呢？

在樹高性質上，AVL tree 和 rbtree 雖然都是 $O(\log n)$ ，但 AVL 在樹高上較緊致，約 $1.44\times \log (n+2)$，而 rbtree 則為 $2\times \log (n+1)$。因此在搜尋等以樹高作為上限的操作下， AVL tree 會比 rbtree 略快，但這是建立在新增和移除需要更多旋轉 (rotate) 以維持樹高的情形（其中 AVL tree 為 3 次，rbtree 為 2 次）。也因此，對於一般實作，Linux 核心偏好採用 rbtree (但近年轉向本文後續探討的 "maple tree")，資料庫的實作會傾向採用 AVL tree。

相關討論: red-black tree over avl tree

儘管 rbtree 和 AVL tree 平均時間複雜度都是 $O(\log n)$，但因行為和特性的落差，有著不同的應用場景，簡述如下:

• 平衡
  • AVL tree 比紅黑樹要平衡（左右子樹的高度不能差超過 2），但會在平衡自身時花費比紅黑樹多的時間。
  • 如果考慮到要更快速地去 search 一個節點，那 AVL tree 會比較適合。
  • 紅黑樹的優點在於雖沒有到完全平衡 (最長路徑 $\le$ 2 倍最短路徑)，但是紅黑樹會在平衡自己時達到 $O(1)$ (最多 3 次旋轉) 的複雜度。
• 空間
  • AVL tree 的節點需要宣告 factor (height) 的變數給每個節點來作為平衡的參考，而紅黑樹只需要 1 位元的變數來區分顏色（紅、黑）。

簡化的判斷因素，讓我們依序場景來選擇自平衡樹:

1. 插入跟移除較多：紅黑樹
2. 查詢節點較多：AVL Tree

此外尚有一項考量:AVL tree 無法提供 amortized update cost，而 rbtree 則有。

對照 SortedSequences - section 7.4

關於效能表現的研究，可見〈Performance Analysis of BSTs in System Software〉，以下摘錄:

The results indicate that when input is expected to be randomly ordered with occasional runs of sorted order, red-black trees are preferred; when insertions often occur in sorted order, AVL trees excel for later random access, whereas splay trees perform best for later sequential or clustered access.

Linux 核心文件 Red-black Trees (rbtree) in Linux 提到:

Red-black trees are a type of self-balancing binary search tree, used for storing sortable key/value data pairs. This differs from radix trees (which are used to efficiently store sparse arrays and thus use long integer indexes to insert/access/delete nodes) and hash tables (which are not kept sorted to be easily traversed in order, and must be tuned for a specific size and hash function where rbtrees scale gracefully storing arbitrary keys).

說明不同資料結構適用場景：當輸入的 indexes 特性為之間的變化極大又偏向一邊，亦即每個 index 之間的差距都頗大的情況，應採用 radix tree，後者本質上是稀疏陣列，有用到的 indexes 才會建立其空間陣列，這也是為何核心文件強調 "must be tuned for a specific size"。在此情況中，若使用 rbtree 將遭遇大量旋轉，因為當資料都偏向一方時，rbtree 本身又是一個自平衡樹，為維護平衡就只能頻繁的旋轉，如此一來，時間開銷就相當可觀。然而，當採用的資料 indexes 浮動不大，rbtree 會是很好的選擇，因為無需事先配置陣列或記憶體。

用語

避免父權主義的遺毒，本文將 parent node 翻譯為「親代節點」，而非「父節點」或「母節點」，不僅更中性，也符合英文原意。若寫作「父」，則隱含「母」的存在，但以二元樹來說，沒有這樣成對關連性。若用「上代」會造成更多的混淆，在漢語中，「上一代」沒有明確的血緣關係 (例如「炎黃子孫」與其說是血緣關係，不如說是傾向文化認同)，但「親」的本意就是指名血緣和姻親關係。

延伸閱讀: 「新中國」和「中華民族」—— 梁啟超悔之莫及的發明

至於 sibling node，本文翻譯為「平輩節點」，而非「兄弟節點」。至於 parent's sibling node 則翻譯為「親代的平輩節點」，不用「叔伯節點」。前述用語儘量依循中性且明確的原則。

簡述紅黑樹

紅黑樹是 2-3-4 樹的變形，1978 年 Leonidas J. Guibas 和 Robert Sedgewick 發明最初的紅黑樹。2008 年 Sedgewick 做了改進，並將此命名為 LLRBT (Left-leaning red–black tree，即 左傾紅黑樹)，後者相比 1978 年的紅黑樹要簡單，程式碼量更精簡，可參見 Left-leaning Red-Black Trees。

簡報: Left-Leaning Red-Black Trees
以下內容改寫自〈理解紅黑樹〉

2-3-4 樹藉由著色轉化成二元樹。它把 3 樹轉化成一條紅邊的左樹或右樹（本文討論的是左傾紅黑樹，右傾的情況忽略)，4 樹轉化成兩條紅邊的二元樹，兩條黑邊的就是 2 樹。如圖所示：

以下是一顆 2-3-4 樹轉換成紅黑樹的表示。

紅黑樹的插入

紅黑樹的插入主要分兩步，首先找到插入節點的合適的排序位置進行插入，然後通過旋轉平衡樹的深度。第一步很容易，使用二元樹遞迴搜尋演算法即可。第二步方式按照 2-3-4 樹插入節點的方式來進行的。2-3-4 樹每插入一個節點會對樹自底向上進行調整(合併或分裂)，紅黑樹也是對應於 2-3-4 樹進行同樣的操作，通過將 3 樹合併為 4 樹，4 樹分裂為二個 2 樹。紅黑樹藉由旋轉和顏色反轉來做這些操作。

在 3 樹中插入一個節點，第一種狀況:

在 3 樹中間插入一個節點第二種情況:

在 3 樹中間插入一個節點第三種情況:

從上面幾種 3 樹的插入情況可看出，LLRBT 之所以使用左傾 (left-leaning) 是為了將 3 樹限制為一種，以便更容易的將 3 樹轉為 4 樹，從而降低實作難度。下圖是 4 節點的分裂。

如果插入的一個節點已是 4 樹，這時候的做法就是不斷向上分裂節點把 4 樹分裂成二個 2 樹的子樹。由於 4 樹的兩條邊都是紅的，轉化成 2 樹後需要把兩條邊變成黑的，並把紅邊提上去。兩條黑邊的是 2 樹，這裡顏色翻轉後就是二個 2 樹。

下圖就是 4 樹分裂顏色翻轉的例子。

下面是兩種當親代節點是 2 樹，4 樹分裂的兩種情況。（親代節點的左子樹）

情況二（親代節點的右子樹）

當親代節點是 3 樹時，4 樹分裂較複雜，一共有 3 種情況。

情況一：

情況二：

情況三：

對照 RBTree Animation 的展現。

紅黑樹的移除

直接移除一個 3 樹或 4 樹不會影響樹的平衡，移除一個 2 樹節點會讓整個樹失去平衡。為了保證不刪到 2 樹，紅黑樹在節點搜尋階段就開始旋轉調整樹，以避免最後碰到 2 樹節點。另外由於 LLRBT 樹是沒有親代節點，在移除一個節點是並不能像 AVL 樹那樣在移除後再旋轉。事先旋轉為的就是將要移除節點的那個方向的樹通過旋轉將高度升高一層。 像二分尋找樹一樣，移除操作會從右樹的最左邊找到一個節點進行替換並移除，所以關鍵點就要借助於 DeleteMin 方法。

為了最終找到的節點是 3 樹或 4 樹，在搜尋階段就開始對樹進行調整，讓搜尋那個方向的樹最終升高一層。

以下搜尋路徑往左走，調整左方向樹的方式。

以下搜尋路徑往右走，調整右向樹的方式。

以上兩種操作方式最終會讓樹搜尋的那個方向升高一層，我們可以看到最底層哪個節點的變始終會是紅的（也就是始終會是 3 樹）。DeleteMin 的做法就是不斷的往左邊進行遞迴，把左子樹升高一層。在節點移除完後，最底層遞迴會重新往上走，這時候會再次調整樹的平衡，把右樹紅色節點旋轉到左邊，兩邊都是左樹的紅色節點進行右旋。

以下是向上調整節點的過程。

以上的的移除方式看起來非常慢，向上和向下遞迴都需要不斷的調整外。經過顏色翻轉向下遞迴的這個過程實際上是碰不到 4 樹，在紅樹向下傳遞的過程中最末端會是顆 3 樹，而不會是 4 樹。

以下圖為例，探討程式碼實作:

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *rebalance;
	rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
	if (rebalance)
		____rb_erase_color(rebalance, root, dummy_rotate);
}
EXPORT_SYMBOL(rb_erase);

1. 假如 __rb_erase_augmented 的節點是 2 的話會進到 Case 1，移除掉的節點是紅色，因此 rebalance 會是 NULL 不會進行 __rb_erase_color ; 反之 __rb_erase_augmented 移除的節點是 31 的話 , 因為移除的節點是黑色，因此 rebalance 會是節點 34 , __rb_erase_color 會進到 Case 4 並脫離

• __rb_erase_augmented: Case1

    if (!tmp) {
        /* Case 1: node to erase has no more than 1 child (easy!)
         *
         * Note that if there is one child it must be red due to 5)
         * and node must be black due to 4). We adjust colors locally
         * so as to bypass __rb_erase_color() later on.
         */
        pc = node->__rb_parent_color;
        parent = __rb_parent(pc);
        __rb_change_child(node, child, parent, root);
        if (child) {
            child->__rb_parent_color = pc;
            rebalance = NULL;
        } else // pc 裡紀錄的是 node 的顏色
            rebalance = __rb_is_black(pc) ? parent : NULL;
        tmp = parent;
    }

2. 若 __rb_erase_augmented 的節點為 7，則會進到上述程式碼的 Case 1 , 會將 7 移除並將 2 變為 19 的左子節點 (leftchild) 且顏色改變為 7 的顏色，rebalance 一樣是 NULL 所以不會進行 __rb_erase_color

• __rb_erase_augmented: Still Case 1

    else if (!child) {
        /* Still case 1, but this time the child is node->rb_left */
        // 將 2 顏色改變為 7 的顏色
        tmp->__rb_parent_color = pc = node->__rb_parent_color;
        parent = __rb_parent(pc);
        // 將從 19 移出的 7 變成 2
        __rb_change_child(node, tmp, parent, root);
        rebalance = NULL;
        tmp = parent;
   }

3. 若 __rb_erase_augmented 的節點是 19，則會進到 Case 2，rebalance 會是節點 25 , __rb_erase_color 會進到 Case 4 並離開
4. 若 __rb_erase_augmented 的節點是 34，則會進到 Case 3，successor 為 49 且不是黑色所以 rebalance 為 NULL
5. __rb_erase_augmented
   • Case 1 : 要移除節點最多只有一個子節點，若只有一個子節點就不用 rebalance，若沒有子節點，則由移除的節點是否為黑色，決定是否 rebalance。rebalance node 為要移除的節點的親代節點
   • Case 2 : 要移除節點有二個子節點，且 rightchild->left == NULL，要移除節點會被右子節點取代 , 看 successor->right 是否存在或 successor 是否為黑色來決定要不要 rebalance , rebalance node 為 sucessor (即替換掉要移除節點)
   • Case 3 : 要移除節點有二個子節點且 rightchild->left != NULL，二個要移除節點會被右子節點的最左節點取代，看 successor->right 是否存在或 successor 是否為黑色來決定要不要 rebalance , rebalance node 為 sucessor (即替換掉要移除節點) 的親代節點
6. __rb_erase_color
   • 會進到 if 的情況：
     • 迴圈第一次 parent->rb_right != null
     • 經過 Case 2 後且需要在 rebalance，節點是親代節點的左子節點
     • 此時親代的平輩節點 (sibling) 為 parent->rightchild
     • case 1: 親代的平輩節點為紅色
     • case 2: 親代的平輩節點為黑色，且親代的平輩節點二個子節點皆為黑色
     • case 3: 親代的平輩節點為黑色，且親代的平輩節點的右子節點為黑色，左子節點為紅色
     • case 4: 親代的平輩節點為黑色，且親代的平輩節點的右子節點為紅色
   • 會進到 else 的情況：
     • 迴圈第一次 parent->rb_right == null , 也就是 rebalance node 沒有右子節點 (e.g 上面舉例的 19)
     • 經過 Case 2 後且需要在 rebalance，節點為親代節點的右子節點
     • 此時親代的平輩節點為 parent->leftchild
     • case 1: 親代的平輩節點為紅色
     • case 2: 親代的平輩節點為黑色，且親代的平輩節點二個子節點皆為黑色
     • case 3: 親代的平輩節點為黑色，且親代的平輩節點的左子節點為黑色，右子節點為紅色
     • case 4: 親代的平輩節點為黑色，且親代的平輩節點的左子節點為紅色
7. 假如 __rb_erase_augmented 的節點是 27 , 因為二個子節點都存在且 rightchild->left != NULL , 所以進到 Case 3 , successor 為右子節點的最左端節點 (31) 並取代要移除的節點 (27), 因 successor->right 不存在且 successor 為黑色要進行 rebalance , rebalance node 為 successor 的親代節點 (34) , 並傳入 __rb_erase_color , 因右子節點存在會進入 if 敘述，親代的平輩節點為黑色 65 又親代的平輩節點的二個子節點皆為紅色，所以只會進到 Case 4，並完成修正。

Linux 核心的紅黑樹實作

Linux 核心的紅黑樹跟一般紅黑樹實作不同之處在於，對節點存取進行若干改進，少了一層的間接操作，並有更好的 cache locality。類似 List API，Linux 的 rbtree 使用的方法是將 rb_node 嵌入要使用的結構中，藉由 container_of 存取資料，而非在 rb_node 裡宣告終端資料指標。

延伸閱讀: Linux 核心原始程式碼巨集: container_of

Linux 核心的紅黑樹需要使用者自行定義 tree search 跟 insert 函式。

延伸閱讀:

• Trees II: red-black trees

紅黑樹節點

摘自 include/linux/rbtree_types.h:

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

對照 rb_node 跟 list_head 後，可發現 Linux 核心風格的資料結構都不會包含 data，而是會將 rb_node 或是 list_head 這些資料結構包在一個更大的結構體裡面。

一個紅黑樹節點包含：親代節點、左子節點、右子節點、顏色。而在 Linux 核心宣告的程式碼中，巧妙地將親代節點跟顏色一起宣告，使用 unsigned long __rb_parent_color 將指向親代節點的指標跟自身的顏色合併。

透過 __attribute__((aligned(sizeof(long)))) 讓編譯器知道 struct rb_node 會對齊 sizeof(long)，這樣就會讓指標最低 2 個位元是沒有使用到的，就可以把顏色的資料放進去其中一個位元中。

舉例來說，一個節點指標如果指向 0xF724315C ，這個位址轉成二進位會變成 ...1100，最低 2 個位元會是 0，Linux 核心開發者利用這特性，將其中一個沒用到的位元拿來標注紅和黑這二種顏色。

container_of or rb_entry

關於什麼時候要使用 container_of 還是 rb_entry（或是其他的 XXXX_entry，依照你正在使用的資料結構），作者的說法是當你是要存取節點的 container structure 時，會使用 container_of。如果要存取節點 container structure 裡的 member，就會使用 XXXX_entry。雖然 XXXX_entry 是一個巨集，且定義跟 container_of 一樣，透過這樣來區分是要存取大的 container 抑或是裡頭的 member，取決於使用情境。

rb_link_node

我們先看一個最常被使用到的函式：

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;
}

這個函式就是把 node 的親代節點設為 parent，並且將 rb_link 指向 node。放入 parent 的左或是右子樹則是依照 rb_link。

rb_insert_color

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
    __rb_insert(node, root, dummy_rotate);
}

__rb_insert 可以到 lib/rbtree.c 看。__rb_insert 做的事情就是插入節點並且進行平衡（rotate）。

親代節點

當要存取親代節點時，可以透過巨集來存取：

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

這個巨集會捨棄最低位的 2 個位元，並且將結果轉成節點指標，就可得到親代節點的位址。

顏色

#define	RB_RED		0
#define	RB_BLACK	1

#define __rb_color(pc)     ((pc) & 1)
#define __rb_is_black(pc)  __rb_color(pc)
#define __rb_is_red(pc)    (!__rb_color(pc))
#define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
#define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
#define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)

在 rbtree_augmented 中定義了紅色為 0，黑色為 1。由此可知，如果一個節點是紅色的，那就可直接存取 __rb_parent_color，但還是透過巨集方式統一較好。

第 7 行的 rb_color(rb) 會存取這個節點的親代節點 __rb_parent_color 的顏色，因為知道黑色是 1，所以透過 (pc) & 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;
}

這個函式所做的事情就是將 p 設定為 rb 的親代節點，rb_color(rb) 是 p 的顏色跟 p 的位址去做 | 就一起設定好親代節點的位址跟顏色了。

也有針對親代節點去設定顏色的函式：

static inline void rb_set_parent_color(struct rb_node *rb,
				       struct rb_node *p, int color)
{
    rb->__rb_parent_color = (unsigned long)p | color;
}

commit b0687c 以 + 取代 | (bitwise-OR)，這樣可在 x86 善用 LEA 指令。

The benefit to x86 is it change the codegen for setting a node to block from mov %r0, %r1; or $RB_BLACK, %r1 to lea RB_BLACK(%r0), %r1 which
saves an instructions.

In all other cases it just replace ALU with ALU (or -> and) which perform the same on all machines I am aware of.

Total instructions in rbtree.o:
Before - 802
After - 782
so it saves about 20 mov instructions.

簡單的紅黑樹例子

決定架構

首先要定義好紅黑樹節點外的 container 結構：

struct mytype {
    struct rb_node node;
    char *keystring;
};

我們就可以透過 container_of(ptr, type, member) 從 rb_node 存取 struct mytype。

Search 實作

接著就需要定義 search 的函式，想法也很直覺：比對現在節點的 keystring 如果小於就往左子節點找，大於就往右子節點找。範例如下：

struct mytype *my_search(struct rb_root *root, char *string)
{
    struct rb_node *node = root->rb_node;

    while (node) {
        struct mytype *data = container_of(node, struct mytype, node);
        int result = strcmp(string, data->keystring);

        if (result < 0)
            node = node->rb_left;
        else if (result > 0)
            node = node->rb_right;
        else
            return data;
    }
    return NULL;
}

Insert 實作

插入的做法就需要先使用 search 找到要插入的位置，新增節點，再進行平衡跟重新著色。

 int my_insert(struct rb_root *root, struct mytype *data)
{
    struct rb_node **new = &(root->rb_node), *parent = NULL;

    /* Figure out where to put new node */
    while (*new) {
        struct mytype *this = container_of(*new, struct mytype, node);
        int result = strcmp(data->keystring, this->keystring);

        parent = *new;
        if (result < 0)
            new = &((*new)->rb_left);
        else if (result > 0)
            new = &((*new)->rb_right);
        else
            return FALSE;
    }

    /* Add new node and rebalance tree. */
    rb_link_node(&data->node, parent, new);
    rb_insert_color(&data->node, root);

    return TRUE;
}

第 6 到 17 行是找出要插入的位置，作法是用一個指向節點位址的指標（指標的指標）來儲存新增的節點要在的位址。

第 20 行就是將找到的 *new 位址插入一個新的節點，將 *new 位址放入節點並連接 parent。

從 11 或是 14 可以知道 new 是左、右子節點指標的指標，可以透過 *new 存取左、右子節點

迭代紅黑樹里的節點

struct rb_node *rb_first(struct rb_root *tree);
struct rb_node *rb_last(struct rb_root *tree);
struct rb_node *rb_next(struct rb_node *node);
struct rb_node *rb_prev(struct rb_node *node);

要迭代過每個節點的方式是藉由先呼叫 rb_first 或是 rb_last，就會回傳一個紅黑樹節點的指標。之後再用這個指標去呼叫 rb_next 或是 rb_prev 就可以存取下一個或是上一個節點了。

回傳 NULL 就代表沒有下一個

將所有節點的 keystring 輸出的範例（由小到大）：

struct rb_node *node;
for (node = rb_first(&mytree); node; node = rb_next(node))
    printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

相關原始程式碼

linux/rbtree.h
linux/rbtree_augmented.h
lib/rbtree.c

Maple tree

Oracle 公司主導、取代 rbtree 的 RCU-safe 嶄新資料結構實作: Maple Tree

[PATCH v4 00/66] Introducing the Maple Tree

Linux is a virtual-memory system. The address space for each process contains multiple virtual memory areas represented by vm_area_struct structures. Each VMA represents a contiguous block of address space and represents a range of memory of the same type, which may be anonymous memory (not backed by a file), a memory-mapped file, or even device memory. A virtual memory area, as seen from the process, is contiguous, while the supporting physical memory may not be. In addition, the address space contains holes between the VMAs; the kernel fills those empty blocks (leaving space for unmapped "guard" pages to catch buffer overflows) when it needs to add a new mapped area, for example when loading a library or in a response to an mmap() call.

VMAs are currently stored in a modified red-black tree (rbtree) with an additional, doubly-linked list that allows the kernel to traverse all of the VMAs in a process's address space. Kernel developers have been unhappy with this data structure for some time, for a number of reasons: rbtrees do not support ranges well, they are difficult to handle in a lockless manner (the balancing operation of the rbtree affects multiple items at the same time), and rbtree traversal is inefficient, which is why the additional linked list exists.

The Maple Tree, A Modern Data Structure for a Complex Problem (2021 年)

The Maple Tree (2019 年)
Different aspects matter for different reasons

	rbtree	Radix Tree	Maple Tree
RCU Safe	No	Yes	Yes
Range support	Yes	Limited	Non-overlapping
Tree height	Tall	Short*	Medium
API	Hard	Easy	Easy
Node	Embedded	External	External
Node size	24 bytes	576 bytes	128 bytes

* with dense indices