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>