LKD(Linux内核设计与实现) Chapter 6 Kernel Data Structures
继续谈数据结构,本篇来聊聊红黑树。红黑树是一种基本平衡的二叉树,在提供良好的搜索性能的同时,插入操作也不会引入过大的再平衡开销。
对红黑树的简单描述
红黑树是这样一种特殊的二叉树:
- 每个节点带颜色,非红即黑
- 叶子节点必须存在并且是黑色的
- 如果一个节点是红色的,那么它的两个子节点必须是黑色的
- 从一个节点到其下辖的叶子结点之间如果存在多条路径,那么每条路径上的黑色节点个数必须等同
以上所有的规则就是为了保证一条特性:
从根节点开始的最远路径的长度不会超过最短路径的两倍。
这条特性限制了红黑树最差情况,保证了搜索性能。
Linux的红黑树实现
Linux的数据结构实现基本有一个共同点,我把它叫做宿主内嵌,看下面的例子:
struct rb_node node
作为红黑树的数据结构,是内嵌到宿主数据结构struct mytype
中去的。这样做的明显好处是集约化,不必再专门为struct rb_node node
单独分配内存,然后数据的读取更具有本地性,会带来更好的cache性能。
第二个问题,因为C语言的限制,Linux的红黑树实现并没有提供一套很完整的操作,类似查找和插入的操作需要使用者自行实现。但是Linux提供了工具箱,可以帮你很容易实现各种操作。让我们来看看内核文档中的一个例子:
红黑树的实现在lib/rbtree.c
,使用前需要包含头文件#include <linux/rbtree.h>
。