Linux内核中的红黑树

china_long

[color="#05006c"]Linux内核中的红黑树[color="#05006c"][精彩] Linux内核中的红黑树
       
         http://www.chinaunix.net 作者:
Godbach
  发表于：2009-01-11 21:46:46
       
【
发表评论
】
【
查看原文
】
【
Linux讨论区
】【
关闭
】
       
       
       
引用链接：http://www.kerneltravel.net/jiaoliu/kern-rbtree.html
红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。
先到include/linux/rbtree.h中看一下红黑树的一些定义，如下：
struct rb_node
{
        unsigned long  rb_parent_color;
#define        RB_RED                0
#define        RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
struct rb_root只是struct rb_node*的一个包装，这样做的好处是看起来不用传递二级指针了。不错，很简单。再看一下
下面几个重要的宏，细心的你一定会发现，rb_parent_color其实没那么简单，Andrea Arcangeli在这里使用了一个小的技巧，不
过非常棒。正如名字所暗示，这个成员其实包含指向parent的指针和此结点的颜色！它是怎么做到的呢？很简单，对齐起了作用。既然是sizeof
(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两
种，其实一位就已经够了。
这样，提取parent指针只要把rb_parent_color成员的低两位清零即可：
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
取颜色只要看最后一位即可：
#define rb_color(r) ((r)->rb_parent_color & 1)
测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数：
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);
它把parent设为node的父结点，并且让rb_link指向node。
我们把重点集中在lib/rbtree.c上，看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则：
1. 每个结点要么是红色要么是黑色；
2. 根结点必须是黑色；
3. 红结点如果有孩子，其孩子必须都是黑色；
4. 从根结点到叶子的每条路径必须包含相同数目的黑结点。
这四条规则可以限制一棵排序树是平衡的。
__rb_rotate_left是把以root为根的树中的node结点进行左旋，__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务，而不是为外部提供接口。
新插入的结点都设为叶子，染成红色，插入后如果破坏了上述规则，通过调整颜色和旋转可以恢复，二叉树又重新平衡。插入操作的接口函数是
void rb_insert_color(struct rb_node *node, struct rb_root *root);
它把已确定父结点的node结点融入到以root为根的红黑树中，具体算法的分析可以参考[1]中第14.3节，这里的实现和书中的讲解几乎完全
一样。怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是，虽然插入操作需要一个循环迭代，但是
总的旋转次数不会超过两次！所以效率还是很乐观的。
删除操作多多少少都有点麻烦，它要先执行像普通二叉查找树的“删除”，然后根据删除结点的颜色来判断是否执行进一步的操作。删除的接口是：
void rb_erase(struct rb_node *node, struct rb_root *root);
其实它并没有真正删除node，而只是让它和以root为根的树脱离关系，最后它还要判断是否调用__rb_erase_color来调整。具体
算法的讲解看参考[1]中第13.3和14.4节，__rb_erase_color对应书中的RB-DELETE-FIXUP，此处的实现和书上也基本
上一致。
其余的几个接口就比较简单了。
struct rb_node *rb_first(struct rb_root *root);
在以root为根的树中找出并返回最小的那个结点，只要从根结点一直向左走就是了。
struct rb_node *rb_last(struct rb_root *root);
是找出并返回最大的那个，一直向右走。
struct rb_node *rb_next(struct rb_node *node);
返回node在树中的后继，这个稍微复杂一点。如果node的右孩子不为空，它只要返回node的右子树中最小的结点即可；如果为空，它要向上查找，找到迭带结点是其父亲的左孩子的结点，返回父结点。如果一直上述到了根结点，返回NULL。
struct rb_node *rb_prev(struct rb_node *node);
返回node的前驱，和rb_next中的操作对称。
void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);
用new替换以root为根的树中的victim结点。
红黑树接口使用的一个典型例子如下：
static inline struct page * rb_search_page_cache(struct inode * inode,
                                                 unsigned long 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 offset)
                        n = n->rb_left;
                else if (offset > page->offset)
                        n = n->rb_right;
                else
                        return page;
        }
        return NULL;
}
static inline struct page * __rb_insert_page_cache(struct inode * inode,
                                                   unsigned long offset,
                                                   struct rb_node * node)
{
        struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
        struct rb_node * parent = NULL;
        struct page * page;
        while (*p)
        {
                parent = *p;
                page = rb_entry(parent, struct page, rb_page_cache);
                if (offset offset)
                        p = &(*p)->rb_left;
                else if (offset > page->offset)
                        p = &(*p)->rb_right;
                else
                        return page;
        }
        rb_link_node(node, parent, p);
        return NULL;
}
static inline struct page * rb_insert_page_cache(struct inode * inode,
                                                 unsigned long offset,
                                                 struct rb_node * node)
{
        struct page * ret;
        if ((ret = __rb_insert_page_cache(inode, offset, node)))
                goto out;
        rb_insert_color(node, &inode->i_rb_page_cache);
out:
        return ret;
}
因为红黑树的这些良好性质和实现中接口的简易性，它被广泛应用到内核编程中，大大提高了内核的效率。
参考资料：
1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press.
2. Understanding the Linux Kernel, 3rd Edition, Daniel P. Bovet, Marco Cesati, O'Reilly.
3. Linux Kernel 2.6.19 source code.
[ 本帖最后由 Godbach 于 2008-12-31 10:52 编辑 ]

Godbach
回复于：2008-12-31 10:38:07
转过来一篇介绍内核中红黑树接口的文章。

scutan
回复于：2008-12-31 11:01:24
学习了，谢谢版主。 :em02:

Godbach
回复于：2008-12-31 11:09:46
呵呵，这两天因为要使用，所以得研究一下。大家一起交流。

Godbach
回复于：2008-12-31 11:30:39
如果哪位朋友使用内核的红黑树接口写了一些程序，方便的话拿上来大家一起学习一下

Godbach
回复于：2008-12-31 11:53:34
2.4.20内核中使用红黑树的好像就mmap等。2.6中使用的更广泛一些

emmoblin
回复于：2008-12-31 19:23:34
红黑树在内核中有很多应用。
数据库中也应用的很多

Godbach
回复于：2008-12-31 19:48:16
是啊。emmoblin兄对这方面有研究吧，什么时候分享一下。

platinum
回复于：2008-12-31 20:10:31
内核 QoS 的 HTB 分层令牌桶用了 RBTREE，Godbach 可以参考一下

dreamice
回复于：2008-12-31 20:25:36
rbtree现在用得越来越广了，连进程调度都使用了红黑树，前面学了一下，看来还需要深入掌握这个东西。

Godbach
回复于：2008-12-31 20:39:25
多谢白金兄指点啊。内核中确实不少地方在使用。正在研究如何使用这样的接口。

Godbach
回复于：2008-12-31 20:40:34
引用：原帖由 dreamice 于 2008-12-31 20:25 发表

rbtree现在用得越来越广了，连进程调度都使用了红黑树，前面学了一下，看来还需要深入掌握这个东西。
是啊。就算不完全理解红黑树，至少要熟悉一下内核接口如何使用。
偶的数据结构学的不好。现在又得一点一点翻书，哈哈。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=631385]changzi100
回复于：2008-12-31 21:48:15
版主发的东西都很高深啊！

Godbach
回复于：2008-12-31 22:58:54
呵呵，这个只是数据结构的东西

Godbach
回复于：2008-12-31 23:04:17
内核中常用的一些数据结构还是需要了解并学习使用方法的

prolj
回复于：2009-01-01 01:19:03
引用：原帖由 emmoblin 于 2008-12-31 19:23 发表

红黑树在内核中有很多应用。
数据库中也应用的很多
SQLite3的开放域开源软件，也就是完全放弃版权的那种。可以看看，我以前看过。hash

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=24163]seawolf1979
回复于：2009-01-01 16:44:02
最近刚好在重看Understanding the Linux Kernel 3rd的第九章，
9.3. Memory Regions也讲到了RB tree，其实说明的也算清楚。
内存区域（vm_area_struct表示）同时用了链表和红黑树。

Godbach
回复于：2009-01-01 17:45:19
引用：原帖由 seawolf1979 于 2009-1-1 16:44 发表

最近刚好在重看Understanding the Linux Kernel 3rd的第九章，
9.3. Memory Regions也讲到了RB tree，其实说明的也算清楚。
内存区域（vm_area_struct表示）同时用了链表和红黑树。
还没看到这个地方，就先翻一下9.3节

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=254716]蚊见蚊爱
回复于：2009-01-01 22:17:55
有空还是自己尝试写个红黑树吧。

Godbach
回复于：2009-01-01 22:31:52
C版converse版主已经实现一个了。正在学习

Godbach
回复于：2009-01-01 23:00:23
引用：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;
}
它把parent设为node的父结点，并且让rb_link指向node。
一个疑问：
这个地方只能设置parent为node的父节点。那么node是作为parent的左子节点还是右子节点，应该是我们在程序里自己实现了吧？

prolj
回复于：2009-01-02 00:35:31
sqlite除了hash还有B tree，管理大量数据RB Tree显然不如B Tree和hash有优势

Godbach
回复于：2009-01-02 12:50:37
请教prolj兄一个问题：
如果我想统计一段时间内和我本地主机通信的IP总数，你觉得用哪种方式实现更好？

dreamice
回复于：2009-01-02 15:39:24
引用：原帖由 Godbach 于 2009-1-1 23:00 发表

一个疑问：
这个地方只能设置parent为node的父节点。那么node是作为parent的左子节点还是右子节点，应该是我们在程序里自己实现了吧？
通过父结点来确认自身是左是右。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=534931]Godbach
回复于：2009-01-02 16:06:19
引用：原帖由 dreamice 于 2009-1-2 15:39 发表

通过父结点来确认自身是左是右。
dreamice兄什么意思，该函数并没有包含任何parent指向该节点的动作啊。
[ 本帖最后由 Godbach 于 2009-1-2 16:55 编辑 ]

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=562632]dreamice
回复于：2009-01-02 17:11:53
引用：原帖由 Godbach 于 2009-1-2 16:06 发表

dreamice兄什么意思，该函数并没有包含任何parent只想该节点的动作啊。
如果是你自己写程序调用这个函数的话，那就是在查找阶段设置左还是右了

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=534931]Godbach
回复于：2009-01-02 17:45:00
引用：原帖由 dreamice 于 2009-1-2 17:11 发表

如果是你自己写程序调用这个函数的话，那就是在查找阶段设置左还是右了
多谢dreamice兄的指点。明白了这个函数的实际用法：
static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
node为当前要插入的节点；
parent为node的父节点；
rb_link为node节点要插入的位置，即parent->left 或parent->right。这个可有前面在查找过程中确定。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=254716]蚊见蚊爱
回复于：2009-01-03 16:45:37
这种数据结构的东西，还是看教材，代码参考产品代码 (STL 中也有 这个数据结构， )，最好不要使用未经严格测试的代码，

Godbach
回复于：2009-01-03 16:53:14
引用：原帖由 蚊见蚊爱 于 2009-1-3 16:45 发表

这种数据结构的东西，还是看教材，代码参考产品代码 (STL 中也有 这个数据结构， )，最好不要使用未经严格测试的代码，
这是内核中的代码，内存管理、进程管理都使用红黑树的接口。怎么能说未经严格测试的代码呢？:em14:

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=540548]creating2008
回复于：2009-01-03 22:09:38
红黑树在STL容器里面基本上都用着了,数据库里面有B+树,hash多一点.

dreamice
回复于：2009-01-03 22:29:22
引用：原帖由 蚊见蚊爱 于 2009-1-3 16:45 发表

这种数据结构的东西，还是看教材，代码参考产品代码 (STL 中也有 这个数据结构， )，最好不要使用未经严格测试的代码，
STL确实比较强大:lol:
Linux内核中的这部分代码，应该是比较稳定可靠的了:wink:

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=75275]lbaby
回复于：2009-01-03 22:33:44
引用：原帖由 Godbach 于 2009-1-2 12:50 发表

请教prolj兄一个问题：
如果我想统计一段时间内和我本地主机通信的IP总数，你觉得用哪种方式实现更好？
这个rb_tree 和hash 都好，  hash 的难点就在于估算总数，在数量级可以预见的情况下，hash的性能可以令人非常满意

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=534931]Godbach
回复于：2009-01-03 22:36:56
引用：原帖由 lbaby 于 2009-1-3 22:33 发表

这个rb_tree 和hash 都好，  hash 的难点就在于估算总数，在数量级可以预见的情况下，hash的性能可以令人非常满意
可以预见的情况下？
那如果我设定了hash表项最多为500,000个，应该也算可预见吧。这个时侯lbaby兄会在hash和rb_tree之间选择那个？

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=562632]dreamice
回复于：2009-01-03 22:42:50
引用：原帖由 lbaby 于 2009-1-3 22:33 发表

这个rb_tree 和hash 都好，  hash 的难点就在于估算总数，在数量级可以预见的情况下，hash的性能可以令人非常满意
如果树建好了后，不存在插入和删除的话，其实AVL树的性能比rbtree还占优势:wink:

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=534931]Godbach
回复于：2009-01-03 22:44:49
是吗。不过很多情况下建树主要就是用来动态的插入和删除吧。

dreamice
回复于：2009-01-03 22:49:25
引用：原帖由 Godbach 于 2009-1-3 22:44 发表

是吗。不过很多情况下建树主要就是用来动态的插入和删除吧。
也有用静态树的情况，这样的话用avl树性能上稍微好一些，但没有数量级的提升，都是log（N）级的。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=534931]Godbach
回复于：2009-01-03 22:51:20
引用：原帖由 dreamice 于 2009-1-3 22:49 发表

也有用静态树的情况，这样的话用avl树性能上稍微好一些，但没有数量级的提升，都是log（N）级的。
OK，以后有对应的应用可以尝试一下。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=75275]lbaby
回复于：2009-01-04 09:43:35
引用：原帖由 Godbach 于 2009-1-3 22:36 发表

可以预见的情况下？
那如果我设定了hash表项最多为500,000个，应该也算可预见吧。这个时侯lbaby兄会在hash和rb_tree之间选择那个？
可预见的意思是，  你可以根据历史或经验估算出你要处理的数据的数量级，和你想出来的设定的那个数无关
比如：你的站点每日访问量100万，那我们就在大于 150万 小于200万之间选一个素数作为hash表项大小
如果我上边没说清，我这里补充一下
hash 表的实现简单，用起来也好用，现在的内存都是白菜价，不用白不用。
省下的时间都是自己的，泡泡妞，灌灌水， 何乐而不为捏？

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=75275]lbaby
回复于：2009-01-04 10:05:38
http://lxr.linux.no/linux+v2.6.28/include/linux/hash.h
另外内核里也有不错的 hash 实现，Godbach 兄可以去看看

Godbach
回复于：2009-01-04 10:05:41
譬如说我的设备最多就防50万个链接，再多的我都直接放过。不用添加表项。
也就是我知道我的设备就可以处理的上限。我以这个上限建表，也算固定的了
[ 本帖最后由 Godbach 于 2009-1-4 10:07 编辑 ]

Godbach
回复于：2009-01-04 10:06:23
引用：原帖由 lbaby 于 2009-1-4 10:05 发表

http://lxr.linux.no/linux+v2.6.28/include/linux/hash.h
另外内核里也有不错的 hash 实现，Godbach 兄可以去看看
多谢lbaby兄指点啊。。

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=719352]wifi
回复于：2009-01-04 10:21:57
好文章，收藏。

Godbach
回复于：2009-01-05 22:28:56
引用：static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
                                struct rb_node ** rb_link)
node为当前要插入的节点；
parent为node的父节点；
rb_link为node节点要插入的位置，即parent->left 或parent->right。这个可有前面在查找过程中确定。
如果rb_link_node如我解释的一样，那么也就是调用该函数的时候应该保证tree至少有一个节点，也就是根节点存在。不然的话，parent本身就为空，无法执行link

maxxfire
回复于：2009-01-11 00:35:18
看了，但是“知其然而不知其所以然”，版主大哥，。。

Godbach
回复于：2009-01-11 12:31:43
引用：原帖由 maxxfire 于 2009-1-11 00:35 发表

看了，但是“知其然而不知其所以然”，版主大哥，。。
其实这里讲的基本上就是《算法导论》中讲的红黑树的实现啊。如果不明白这个，是不是本身对红黑树不太了解啊？

[url=http://linux.chinaunix.net/bbs/viewpro.php?uid=562632]dreamice
回复于：2009-01-11 20:31:42
算法导论的中文版，红黑树那一章讲得有点云里雾里的，呵呵。可能英文版讲得好一点吧

Godbach
回复于：2009-01-11 21:46:46
引用：原帖由 dreamice 于 2009-1-11 20:31 发表

算法导论的中文版，红黑树那一章讲得有点云里雾里的，呵呵。可能英文版讲得好一点吧
呵呵，insert部分大致明白了。erase比较复杂。
[color="#05006c"]

               
               
               

本文来自ChinaUnix博客，如果查看原文请点：[url]http://blog.chinaunix.net/u2/83200/showart_1799718.html