Linux 核心專題: 紅黑樹實作改進

contributed by < Wufangni >
解說影片連結：Linux 核心專題: 紅黑樹實作改進

Reviewed by `fennecJ`

針對 linux kernel 中紅黑樹的相關函式 API 進行廣泛的探討，閱讀文章過程中我學到了許多，也複習了不熟悉的紅黑樹操作流程。

問題

問題一
「紅黑樹在重新平衡的標準下容忍度相較高，減少需重新平衡的時間成本。」可否進一步說明，或透過分析其演算法呈現為何其容忍度較高。

紅黑樹遵守五大原則(在 TODO: rbtree & XTree 中提及)，因此做插入或刪除操作時只會因為黑色節點數量不一致或顏色規則而需重新平衡，而 AVL Tree 在平衡結構方面規劃的較為嚴謹，若左右子樹差超過 1 時就須重新平衡，因此整體所需的重平衡成本相較高於紅黑樹。
問題二
針對運用場景的歸納，為何 AVL tree 相較 rb tree 更適合用於搜尋較多的場合

因上訴回答說明，AVL Tree 在平衡方面有較嚴謹的規範，因此整體平衡性會高於紅黑樹，因此在搜尋操作下相較於紅黑樹能更有效率的找出目標節點。
問題三
rb_augmented_tree 中使用了 propagate function 進行資料的維護，該 function 的時間複雜度為何？是否會影響到原本 insert/del 的時間複雜度。

根據紅黑樹性質其樹高最多被限制在
$O (l o g n)$ ，而 propagate 用於向上更新節點附加資訊(從更新節點位置到至多根節點位置)，因此時間複雜度為
$O (l o g n)$ ，且由於額外維護操作與樹高成正比，因此在插入及刪除操作下時間複雜度仍為
$O (l o g n)$ 。
問題四
可否進一步解釋 xtree 中使用的超立方體資料結構是如何實做的

Xtree 中每個節點皆擁有自己的一份超立方體，用來含括資料範圍提高範圍搜尋效率，因此超立方體結構須包含最大值、最小值以及維度等資訊，範例如下:
```
typedef struct Hypercube {
    float *min;
    float *max;
    int dimensions;
} Hypercube;
```

Reviewed by `marsh-fish`

rbtree_augmented.h 的 __rb_erase_augmented 並不是在進行刪除節點的操作，而是在判斷是否進行再平衡(rebalance)

TODO: rbtree & XTree

閱讀課程教材 Linux 核心的紅黑樹了解紅黑樹(rbTree)的基本定義及優勢

紅黑樹做為一種自平衡樹在新增、刪除或搜尋等操作下時間複雜度均為

O (l o g n)

，特別的地方在於樹高採用 black height(不含自身節點到樹葉節點的總黑色節點數量)，相較於 AVL Tree 嚴格要求每個節點左右子樹高度差不超過1，紅黑樹在重新平衡的標準下容忍度相較高，減少需重新平衡的時間成本。
因此以不同角度對AVL Tree與紅黑樹做觀察和比較，前者雖然整體結構較平衡，但需要比多的平衡時間，而在搜尋資料方面 AVL Tree 因較好的平衡規範表現優於紅黑樹，所需空間方面紅黑樹只需 1 位元的變數來區分紅色或黑色資訊，因此可將兩種資料結構的運用場景歸納如下:

插入或移除較多的情況: 使用紅黑樹結構
以搜尋為主的場景: 使用 AVL Tree 結構

從 linux 提供的紅黑樹相關程式碼逐一理解紅黑樹基本操作:

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

紅黑樹從 2-3-4 樹變化而來，因此可以自由地在兩結構之間做變換，主要遵守五大原則:

紅黑樹內所有節點不是紅色就是黑色
樹根( root )必為黑色節點
紅色節點的子節點皆為黑色節點
所有樹葉節點( null )皆為黑色
從根節點到每個樹葉節點的路徑內黑色節點數量必一致

節點定義

rb_node 結構體存放三種資訊，*rb_left、*rb_right 分別指向左右子節點位址，__rb_parent_color 存放了父節點位址，且由於 __attribute__((aligned(sizeof(long))) 會讓編譯器對 sizeof(long) 做對齊，因此最低兩位元不會被使用到(永遠都是零)，可用來儲存該節點顏色資訊，而 rb_root 用來儲存根節點的位址資訊。

struct rb_node {
	unsigned long  __rb_parent_color; #包括父節點位址和顏色，顏色存在最後兩bit
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root {
	struct rb_node *rb_node;
};

較常使用的 rb_parent 過濾掉 __rb_parent_color 最低兩位元資訊，用於獲取父節點的位址。

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

rb_link_node 透過指定 __rb_parent_color 到 *parent 的方式將 *node 的父節點位址指定到 *parent。

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

rb_root_cached 除了儲存根節點位址外也存了最左節點(樹的最小節點)資訊，因此使用 #define rb_first_cached(root) (root)->rb_leftmost 可直接存取cache儲存的最左節點，搜尋結果的時間複雜度只需

O (1)

。

struct rb_root_cached {
	struct rb_root rb_root; //原始紅黑樹的根
	struct rb_node *rb_leftmost; //樹的最左節點
};

對 rb_root_cached 做插入、刪除、替換節點的操作時需要一同更新 cache 內最左節點的資訊。

static inline void rb_insert_color_cached(struct rb_node *node,
					  struct rb_root_cached *root,
					  bool leftmost)
{
	if (leftmost)
		root->rb_leftmost = node; //如果插入的節點是最左節點，則更新cache
	rb_insert_color(node, &root->rb_root); //使用插入修復函數rb_insert_color
}

static inline void rb_erase_cached(struct rb_node *node,
				   struct rb_root_cached *root)
{
	if (root->rb_leftmost == node)
		root->rb_leftmost = rb_next(node); //如果刪除的節點是最左節點，則更新cache
	rb_erase(node, &root->rb_root); //使用刪除修復函數rb_erase
}

static inline void rb_replace_node_cached(struct rb_node *victim,
					  struct rb_node *new,
					  struct rb_root_cached *root)
{
	if (root->rb_leftmost == victim) //如果被替代的節點是最左節點
		root->rb_leftmost = new; //更新cache為新節點
	rb_replace_node(victim, new, &root->rb_root); //使用替換函數rb_replace_node
}

Augmented Red-Black Tree

從 rbtree_augmented.h 可看到對於 Augmented Red-Black Tree 的相關定義與實作方式，Augmented Red-Black Tree 可在一般傳統紅黑樹上附加額外的資訊及維護功能，可將額外資訊藏在節點中(比如子樹的最大值、最小值…等)，使用 rb_augment_callbacks 做各種維護操作，主要結構如下:

struct rb_augment_callbacks {
    void (*propagate)(struct rb_node *node, struct rb_node *stop);
    void (*copy)(struct rb_node *old, struct rb_node *new);
    void (*rotate)(struct rb_node *old, struct rb_node *new);
};

*propagate 代表在插入、刪除節點和調整顏色時用來向上更新子樹的附加資訊
*copy 代表節點被替換時複製附加資訊
*rotate 代表在旋轉時更新附加資訊

rbtree_augmented.h 內的常用定義:

#define	RB_RED		0 //紅節點為0
#define	RB_BLACK	1 //黑節點為1

#define __rb_parent(pc)    ((struct rb_node *)(pc & ~3)) //取得父節點位址

#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) //判斷是否為黑色

rb_set_parent 將 *rb 節點的顏色與 *p 的位址合起來指定給 rb->__rb_parent_color，等同於設定 *p 作為 *rb 的父節點。

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

__rb_change_child 為替換節點操作，如果父節點存在則判斷要被替換的節點是否為左子節點，一致就將左子節點位址指定到新節點，否則指定右子節點位址到新節點，若父節點不存在代表此被替代節點為根節點，則指定根節點為址到新節點。

static inline void
__rb_change_child(struct rb_node *old, struct rb_node *new,
		  struct rb_node *parent, struct rb_root *root)
{
	if (parent) {
		if (parent->rb_left == old)
			WRITE_ONCE(parent->rb_left, new); 
		else
			WRITE_ONCE(parent->rb_right, new);
	} else
		WRITE_ONCE(root->rb_node, new);
}

__rb_erase_augmented 刪除節點情況:

Case1 如果刪除節點沒有子節點或只有一個子節點:
- 將刪除節點以子節點作替代
- 若只有右(左)子節點則將pc(刪除節點的父節點位址及刪除節點的顏色)給替代的節點
- 若皆無子節點則判斷刪除節點是否為黑色，若刪除黑色節點則需重新平衡紅黑樹(保持第五點原則)
Case2 如果刪除節點有兩個子節點，且刪除節點的右子節點就是後繼節點:
```
if (child2) {
    rb_set_parent_color(child2, parent, RB_BLACK);
    rebalance = NULL;
}
```
若child2為紅色，後繼節點必為黑色，則刪除節點有兩種情況:
- 刪除節點為黑色時，因紅黑樹原則第五點每條路徑黑色節點數必須一致，child2必須轉為黑色節點確保數量正確。
- 刪除節點為紅色時，原在刪除節點的左子節點必為黑色，跑到後繼節點下則黑色節點數目需加一，child2需轉為黑色確保後面的路徑黑色節點數一致。

Case3 如果刪除節點有兩個子節點，且刪除節點的右子節點不是後繼節點:

持續直到找到後繼節點( succesor )為止:

do {
    parent = successor;
    successor = tmp;
    tmp = tmp->rb_left;
} while (tmp);

將後繼節點往上拉到刪除節點的右子節點:

child2 = successor->rb_right;
WRITE_ONCE(parent->rb_left, child2);
WRITE_ONCE(successor->rb_right, child);
rb_set_parent(child, successor);

augment->copy(node, successor);
augment->propagate(parent, successor);

此時欲替代刪除節點的後繼節點已變成刪除節點的右子節點，與 Case2 情況相同，因此後續交換節點與平衡方式等同於 Case2 作法。

在 lib/rbtree.c 中的基本輔助函數 rb_set_black 與 *rb_red_parent，前者用於設置輸入節點的顏色為黑色，後者則是獲取紅色節點 *red 的父節點指針。

static inline void rb_set_black(struct rb_node *rb)
{
    rb->__rb_parent_color |= RB_BLACK;
}

static inline struct rb_node *rb_red_parent(struct rb_node *red)
{
    return (struct rb_node *)red->__rb_parent_color;
}

__rb_rotate_set_parents 在旋轉操作中設置父節點和顏色，old 節點被替換成 new 節點，且更新父節點指針和顏色。

static inline void __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new, struct rb_root *root, int color)
{
    struct rb_node *parent = rb_parent(old);
    new->__rb_parent_color = old->__rb_parent_color;
    rb_set_parent_color(old, new, color); //設定 new 為 old 節點的父節點，且 old 上色為指定的顏色 color
    __rb_change_child(old, new, parent, root); //將 old 節點位置替換成 new 節點
}

了解 XTree 基本定義和操作方式

XTree 用於多維度數據空間索引的資料結構，可高效率的對高維度數據做搜尋，適用於需高維度資料查詢的場景下，例如需要建立地圖、座標等高維資訊的地理資訊系統(Geographic Information System, 簡稱 GIS)，含有圖像、聲音、影片等高維特徵向量的多媒體數據庫…等，可在空間利用率和資料查詢性能之間取得較好的平衡。
節點類型分為兩種:

樹葉節點( leaf ):直接存取多維向量資料，並賦予每筆資料一個索引 ID
分支節點( branch ):不儲存資料，而是存放其子節點的位址指針

每個節點會有一個自己的 Split Dimension 和 Split Threshold，當節點的資料數量達到 Split Threshold 設立的上限，則需依靠 Split Dimension 提供的分割維度分裂節點， XTree使用超立方體來覆蓋每個節點的資料，一個節點代表一個超立方體，邊長為該節點包含的資料最大範圍在各維度上的跨度，使用超立方體可簡化節點的管理和搜尋過程。
XTree 的工作原理主要劃分為以下三項:
1. 插入節點操作
新資料根據多維座標找到適合插入的樹葉節點，為了確保邊長能覆蓋到此節點包含的所有資料需要對此節點的超立方體進行更新。
2. 分裂節點操作
若插入的資料超過此節點的容量限制( Split Threshold )，則需分裂節點，且分裂後的新節點會各自擁有自己的超立方體。
3. 搜尋節點操作
XTree 會透過查詢條件判斷是否與節點的超立方體重疊來快速過濾不相關的節點，提高搜尋效率。

XTree基於上述特性可整理出它帶有的優缺點，如下統整:

優點
1. 高效率的多維查詢:透過超立方體特性可有效處理和查詢多維度資訊
2. 較低的樹高結構:透過分裂策略 X-Tree 可維持較低的樹高提升搜尋效率
3. 減少節點重疊:在分裂過程盡量減少節點重疊區域，提高搜尋效率
缺點
1. 實現困難:因複雜的結構和分裂策略，實際實現難度較大。
2. 空間成本大:為了減少樹高和重疊區塊，節點容量需求較大。
3. 通用性低:相較於紅黑樹被廣泛的應用， X-Tree 主要針對多維度資料處理，應用範圍較低。

因此與先前教材中的紅黑樹特性去做一個比較整合，下表顯示 rbtree vs XTree 的特性比較:

-	rbtree	XTree
應用場景	需要快速搜尋、插入和刪除的場合，例如記憶體管理等系統操作。	需要對多維資料作處理的場景，例如 GIS 和多媒體資料庫。
實現難易度	難度高，但效能穩定，可廣泛適用於多種場景下使用。	難度高，主要針對多維度資料處理的應用。
效能	一維資料上效能穩定，操作複雜度維 $O (l o g n)$ 。	在高維資料上效能上有優勢，能高效率查詢多維資訊。
重平衡時間	rbtree 因高效的平衡操作，所需時間成本較短。	XTree 在多維資料處理上效率較高。
空間成本	每個節點需要儲存顏色資訊。	由於節點容量需求較大，空間成本開銷較高。
資料範圍	主要針對一維資料操作。	主要針對多維資料操作。

TODO: 閱讀 CPU Scheduler book 第 3 章關於 AVL tree vs. rbtree

在 linux 核心中紅黑樹資料結構應用在任務的排程器當中，系統將可執行的任務儲存在紅黑樹，再以執行時間的線性順序插入到 process 中，且因紅黑樹的自平衡搜尋樹特性，樹高會與基本操作(插入、刪除和搜尋)的時間成本成正比，因此在平衡過程中會盡可能減低樹的高度以降低時間成本。

CPU 排程器在選取下一個要執行的任務時會依據 vruntime 最小來做選擇，因此需找出紅黑樹最左邊節點，一般紅黑樹在 n 個節點下樹高 ≤ 2 log2(n + 1)，搜尋的時間複雜度為

O (l o g n)

，然而在 lib/rbtree.c 中可看到紅黑樹存在有快取和非快取兩種結構的版本，有快取版本中用來儲存根節點位址的結構體 rb_root_cached 會多儲存最左邊節點的資訊，且以多個更新操作去維護他，此時對最小節點的搜尋成本降為

O (1)

，可顯著加速搜尋過程，CFS 中採用快取版本來維護最小執行時間的任務。

若任務是被阻止的不會再次進入 runqueue，但若是遇到 timeslice 結束或是被其他任務搶先則會插入到更新執行時間後的紅黑樹中，且可能不會在原先的位置(經過

O （ l o g n ）

時間的重新平衡)。

以上圖範例來看，左邊以一個黑色子節點代表最淺的樹葉節點，右邊則利用紅黑穿插來增加樹高(不能有連續紅節點情況)，且要符合每條路徑內的黑節點數量一致，因此最深可達樹高 3 的樹葉節點，確保了最深樹葉節點的樹高不會超過最淺樹葉節點的兩倍。
根據上述內容及前置作業對紅黑樹的基本認知，紅黑樹的優點可以分為下面兩點:

插入和刪除操作的實時性:
在紅黑樹的插入和刪除操作中通常只需要最多兩次和三次旋轉，可使得樹迅速達到平衡保持實時性能，且這些操作的最壞情況皆有一個上限
$O (l o g n)$ 。
搜尋時間雖相較於 AVL tree 略慢，但最糟情況下還是可達到
$O (l o g n)$

將紅黑樹與常使用的 AVL tree 做比較，列出了兩結構在時間、空間及使用場景下的差異性，且由於 CFS 需要頻繁的插入和刪除，因此紅黑樹更適合 CFS。

	rbtree	AVL tree
平衡性	較低，但相較於AVL tree 減少了每次操作需要重新平衡的次數	較高，AVL tree 有嚴格規定左右子樹之間的高度不能大於2
空間需求	較低，只需一位元儲存顏色資訊	較高，需要一整個整數變量來儲存平衡因子
搜尋效率	較低，平衡狀態不如 AVL tree，時間複雜度為 $𝑂 (2 \times l o g (𝑛 + 1))$	較高，屬於高度平衡結構因此時間複雜度為 $𝑂 (1.44 \times l o g (𝑛 + 2))$
應用場景	適用於頻繁添加/刪除節點的場景	適用在需密集查詢資料的場景

TODO: 設計實驗 + extra

設計紅黑樹測試內容，引入 rbtree.c 及 rbtree.h 並撰寫測試檔 rbtree-tst.c，首先建立欲操作的紅黑樹節點結構 my_node，包含一個節點值 key 及紅黑樹存放指針結構 rb_node 。

struct my_node {
    int key;
    struct rb_node rb;
};

加入搜尋、插入 my_insert 、刪除等操作，且在插入及刪除節點時使用紅黑樹平衡函式 rb_insert_color 及 rb_erase ，避免紅黑樹規則被破壞。

新增紅黑樹根節點 tree，使用 clock_t 紀錄操作開始與結束的時間，且定義要紀錄的最大節點數 max_node_count 、每次操作的節點數量 step_size ，以及迭代次數 iterations ，實驗會以多次迭代的平均作為該次操作的計算結果。

struct rb_root tree = RB_ROOT;
clock_t start, end;
int max_node_count = 250;
int step_size = 10; //須持續往上遞增直到達到最大節點數上限
int iterations = 10; //設計迭代次數取 10 次操作結果的平均值

測試執行時間差異

新增用來計算操作時長的函數 get_time_in_seconds。

double get_time_in_seconds(clock_t start, clock_t end) {
    return (double)(end - start) / CLOCKS_PER_SEC;
}

n 等同於 step_size，每次操作會採用 rand() 對該次操作的全部節點賦予隨機值。

int* keys = (int*)malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
    keys[i] = rand() % 1000000;
}

計算插入節點操作
建立新的插入節點 *new_node 並賦予 key 值，start = clock() 和 end = clock() 分別紀錄操作開始與結束的時間，且使用 get_time_in_seconds 計算總操作時長。

for (int i = 0; i < n; i++) {
    struct my_node *new_node = (struct my_node *)malloc(sizeof(struct my_node));
    new_node->key = keys[i];

    start = clock();
    my_insert(&tree, new_node);
    end = clock();

    total_insert_time += get_time_in_seconds(start, end);
}

計算搜尋節點操作
與插入操作相同計算方式，分別紀錄開始與結束時間並使用 get_time_in_seconds 取得總操作時長。

for (int i = 0; i < n; i++) {
    start = clock();
    my_search(&tree, keys[i]);
    end = clock();

    total_search_time += get_time_in_seconds(start, end);
}

計算刪除節點操作
先利用 my_search 搜尋欲刪除的節點，後續計算方式與插入操作相同，分別紀錄開始與結束時間並使用 get_time_in_seconds 取得總操作時長。

for (int i = 0; i < n; i++) {
    struct rb_node *node = my_search(&tree, keys[i]);
    if (node) {
        struct my_node *data = rb_entry(node, struct my_node, rb);

        start = clock();
        my_delete(&tree, data);
        end = clock();

        total_delete_time += get_time_in_seconds(start, end);
    }
}

最後在每次操作結束後釋放儲存節點值的記憶體 free(keys) 。

完整程式碼在 Wufangni/rbtree

此為最大節點數達到 250 時，分別對插入搜尋刪除三種操作時長的紀錄
此為最大節點數達到 1000 時，分別對插入搜尋刪除三種操作時長的紀錄

最大節點數增加到1000時可明顯分別出三個操作下時間長度的差異，插入和刪除操作因多次重平衡（旋轉和上色）所需時間會高於搜尋操作。

圖表中最後呈現結果反而在刪除操作時效能會優於搜尋操作，但搜尋時不需要做重新平衡，理應低於刪除操作的執行時長，但只有在初期實驗（最大節點數 50 以內）有呈現這個趨勢，目前還沒找出能解釋的原因。

此外也分別對不同迭代次數做實驗，以下皆為 max_node_count = 250 時不同 iterations 的實驗結果：

iterations = 1
iterations = 5
iterations = 10
iterations = 50

可看到若沒有設置迭代次數（iterations = 1）只單靠一次操作時長做紀錄，會因每次操作的細微差異造成不穩定的曲線狀態，在三種不同操作下的辨識程度會非常低，難以區分各操作的效能優劣，隨著迭代次數的增加取平均後可看到不同操作分佈逐漸分開，曲線也不會像單一次數那樣呈現震盪，若是迭代次數設置太大（iterations = 50）則容易造成分佈相似的操作更緊密，差異較大的分的更明顯的現象，對於原本比較接近的刪除和搜尋兩操作會更不易於分辨。

測試旋轉次數差異

在 rbtree.h 檔案中新增外部宣告 rb_rotation_count，用於紀錄旋轉次數。

extern unsigned long rb_rotation_count;
void reset_rb_rotation_count(void);

在 rbtree.c 中加入 reset_rb_rotation_count 函式

unsigned long rb_rotation_count = 0;

void reset_rb_rotation_count(void) {
    rb_rotation_count = 0;
}

更改 __rb_rotate_left 和 __rb_rotate_right，增加 rb_rotation_count++ 以計算每次左旋和右旋的次數。

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) {
    rb_rotation_count++; // Increment rotation count
    struct rb_node *right = node->rb_right;
    struct rb_node *parent = rb_parent(node);

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

    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_set_parent(node, right);
}

修改 Makefile

CC = gcc
CFLAGS = -Wall -g
OBJ = rbtree.o rbtree-tst.o

all: rbtree-tst

rbtree-tst: $(OBJ)
	$(CC) $(CFLAGS) -o $@ $^

rbtree.o: rbtree.c rbtree.h
	$(CC) $(CFLAGS) -c rbtree.c

rbtree-tst.o: rbtree-tst.c rbtree.h
	$(CC) $(CFLAGS) -c rbtree-tst.c

clean:
	rm -f *.o rbtree-tst rbtree_performance_time.dat rbtree_performance_rotation.dat rbtree_performance_time.gnuplot rbtree_performance_rotation.gnuplot rbtree_performance_time.png rbtree_performance_rotation.png

測試在最大節點數為 250 時三個操作的旋轉次數

根據圖表呈現插入操作的旋轉次數使用最多，其次為刪除操作，驗證了兩操作在時間總長實驗下的差異性（插入所花時間明顯高於刪除），而搜尋操作因沒有直接對樹的本身結構做改變則不須重新平衡，故旋轉次數為零。

測試 cache 未命中次數

cache miss 作為一個新的判斷效能的依據，若在執行過程中產生 miss 則須從記憶體再做一次存取的操作，造成效能降低，因此使用 perf 來統計 Data Cache Misses 總次數，並對不同操作進行了分析及比較。
新增 measure_cache_misses 函數，建立一個 command 命令用來統計插入、刪除和搜尋操作的 cache 未命中次數。

char command[256];
sprintf(command, "perf stat -e cache-misses ./rbtree-tst-perf-helper %s %d 2>&1 | grep 'cache-misses' | awk '{print $1}'", operation, n);

打開進程來執行剛剛建立的 command，並連接到 perf_output

FILE* perf_output = popen(command, "r");
if (!perf_output) {
    perror("Error running perf command");
    exit(1);
}

建立一個儲存 cache 輸出結果的緩衝區，並從 perf_output 讀取一行輸出到 buffer，轉換型態存進 *cache_misses 中，最後關閉剛剛被打開的 perf_output。

char buffer[128];
if (fgets(buffer, sizeof(buffer), perf_output) != NULL) {
    *cache_misses = atol(buffer);
} else {
    *cache_misses = 0;
}
pclose(perf_output);

在插入刪除，及搜尋操作下呼叫 measure_cache_misses 函數並以不同變數累加該次的 cache miss，最後除以迭代次數取的平均值。

//插入操作
long insert_cache_misses;
measure_cache_misses("insert", n, &insert_cache_misses);
total_insert_cache_misses += insert_cache_misses;

//搜尋操作
long search_cache_misses;
measure_cache_misses("search", n, &search_cache_misses);
total_search_cache_misses += search_cache_misses;

//刪除操作
long delete_cache_misses;
measure_cache_misses("delete", n, &delete_cache_misses);
total_delete_cache_misses += delete_cache_misses;

測試在最大節點數為 5000 時三個操作的 cache miss 次數

可看到在插入操作時的 miss 情況會比較多，與執行所花時長呈現正相關，表示插入操作執行過程中會比另兩個操作多花費了大量重新存取資料的時間。

rbtree vs AVL tree

實做 AVL tree 的兩個檔案 avltree.c 及 avltree.h，並新增 avlVSrb-tst.c 測試檔，引入兩種資料結構和分別紀錄在插入刪除和搜尋三個操作下的執行時間。

插入操作下的 rbtree vs AVL tree
刪除操作下的 rbtree vs AVL tree
搜尋操作下的 rbtree vs AVL tree

根據兩資料結構的性質，rbtree 較適合進行大量插入刪除的操作，而在實驗結果中可看到在插入操作過程中 rbtree 的執行時間明顯低於 AVL tree，而在刪除與搜尋兩操作執行時間差異不大，較難對此做區分。

XTree 的改進 (Xa-Tree)

參考〈Xa-tree：在 OLAP 上有效支援範圍查詢的多維度索引架構〉論文的作法，Xa-Tree 做為 X-Tree 的一種變化型態，結合了 X-Tree 和 Ra-tree 的優點，可以有效提升範圍查詢的效能，提昇查詢效率。

改進 X-Tree 方式

Xa-Tree 在內部節點另外存放了該節點的特徵值，例如節點包含的葉子節點總數或所有值總和…等，若遇到範圍查詢時只須對其根目錄做搜尋，節省逐一拜訪每個節點的搜尋時間。

typedef struct DirEntry {
    struct Node *child;
    float *min;
    float *max;
    float sum; // 增加子樹總和特徵值
} DirEntry;

建立範圍判斷函數 contains，利用每個維度的最小值與最大值檢查該範圍是否完全包含於另一種範圍。

int contains(float *min1, float *max1, float *min2, float *max2, int dimensions) {
    for (int i = 0; i < dimensions; i++) {
        if (min1[i] < min2[i] || max1[i] > max2[i]) {
            return 0;
        }
    }
    return 1;
}

且在範圍搜尋函數內使用 contains 判斷此節點內容是否包含於搜尋範圍內，若是則直接採用節點內的特徵值。

if (contains(query_min, query_max, node->dir_entries[i].min, node->dir_entries[i].max, dimensions)) {
    sum += node->dir_entries[i].sum;
}

Xa-Tree 保留了 X-Tree 分裂節點的 supernode 機制，透過減少與目錄節點的重疊提高搜尋效能。

實驗結果

下面是〈Xa-tree：在 OLAP 上有效支援範圍查詢的多維度索引架構〉論文提供的在不同範圍大小的資料搜尋下各資料結構的效能。

查詢範圍 90%各維度 CPU 計算時間
查詢範圍 10%各維度 CPU 計算時間
查詢範圍 90%各維度節點存取次數
查詢範圍 10%各維度節點存取次數

Jim Huang

2024/06/26 23:15:32

如何改進 XTree 呢？

2024/07/02 03:21:46

XTree 用於多維度數據空間索引的資料結構

沒這回事！XTree 只是隨意的命名，不要穿鑿附會

2024/07/02 03:22:06

測驗題已經說，XTree 只是隨意的命名，務必認真看說明

2024/07/02 03:24:17

可否進一步解釋 xtree 中使用的超立方體資料結構是如何實做的

這問題不需要討論，純粹是張冠李戴。原本題目的 XTree 根本跟下面報告的描述不同

Linux 核心專題: 紅黑樹實作改進

Reviewed by fennecJ

問題

Reviewed by marsh-fish