内核数据结构:红黑树(设计)

    技术2022-05-12  38

    何为红黑树? 红黑树是一种具备较好平衡性二叉搜索树,用于存储键值对类型的数据。 1. 所谓较好平衡性,是指该二叉树的任何一个子节点,其左右子树的高度都相近。从而在搜索/插入/删除节点的时候都有较高的效率。为保证这一特性,约定红黑树具有以下性质:       性质1. 节点是红色或黑色。            性质2. 根是黑色。            性质3 每个叶节点是黑色的。            性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)            性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 2. 另外,还需要注意,红黑树存储的是key-value类型的数据。每一个节点必然具有key。在阅读内核代码碰到红黑树时,就要去考虑,该树中各个节点的key是什么。 3. 红黑树是二叉搜索树,所以一个节点不能有两个以上的子节点。但在QoS调度算法sch_htb中,一个节点可能有多个子节点,该怎么处理?

    为什么要使用红黑树? hash表也可以用来存储key-value类型的数据,那么和hash表相比,红黑树有哪些优缺点?      1)hash表可以以O(1)的效率去查找一个节点,但是红黑树不行,它的效率是O(n)(虽然很接近O(lgN)),效率方面没有优势。      2)hash表需要占用一定内存去存储key数组,且该数组的大小在初始化hash表时就设定好了的,不太方便扩容。但红黑树不用分配内存存储key,可以很优雅地伸缩。      3)hash表的效率在一定程度上取决于hash函数能否将所有的key-value很分散地映射到数组中,最差劲的hash函数会导致hash表的效率为O(n)。红黑树没有这方面的顾虑。      4)相对于线性的hash表,以树形方式组织所有节点,使得代码更加晦涩难读。所以要用得好也就需要一定技巧了。

      

      

    Linux内核中的红黑树       内核中的数据结构大都具有一个特点:实现无关性。       比如list_head。在内核中,由于大量使用链表,如果按照传统方式定义链表,那么需要在数据结构中实现大量的a_next, a_prev, b_next, b_prev这样的指针。也就是说,链表本身和它的应用是紧密结合在一起的。可否将这二者分离?在C++中,可以使用诸如vector_list将链表与应用分离,C语言也可以实现这样的效果。linux内核实现list_head数据结构,可以嵌入在任意数据结构中,之后该数据结构的所有节点即可以向链表一样串起来。       我们期待内核中的红黑树也有这种效果。它实现的是一个容器,可以将各个节点往这个容器中装,完全不用根据节点的类型去考虑该怎么设计这个树。有两种数据结构:       1)容器,或者叫树的根。名为rb_root。       2)节点,代表树中的每一个分叉,或者每一个叶子。名为rb_node。节点需要维护颜色信息,以及指向左右子树和父节点的指针。

      

          或者从面向对象的角度来看这个需求,可能更容易理解一些。       定义一个基础类base_rb_node,它记录红黑树本身的关键信息,包括颜色信息,以及指向左右子树和父节点的指针。在该类中定义一个纯虚函数match_fun用于比较两个节点。业务类aa_node继承自基础类,并添加key、value,match_fun等信息,派生类还需要实现match_fun函数。定义一个vector_rbtree的容器,用来保存所有的base_rb_node。       int base_rb_node::match_fun(class base_rb_node *bnode1, class base_rb_node *bnode2) ;       int vector_rbtree::add_node(class base_rb_node *bnode) ;       刚查了下,STL中的set和map都是使用红黑树来实现的,有时间可以研究下STL中的红黑树是怎么实现的。又或者将内核中的红黑树以C++的方式移植一下?

        


    最新回复(0)