Red-black Trees (rbtree) in Linux
January 18, 2007
Rob Landley <rob@landley.net>
=============================
red-black树是什么样的树，为什么需要red-black树？
------------------------------------------------
red-black tree（RB树）是一种平衡二叉树，它主要用于存储或者说索引可排序的键
值对数据。RB树（红黑树）与radix树和hash表都不同。radix树是一种比较适合用于
存储稀疏的数据集而且将用一个大整数进行插入，删除，查找的操作基础。而hash表
并不是以某种排序顺序进行存储，而且必须指定大小和hash函数。
RB树与AVL树很相似，但是比AVL树有更好的插入和删除最坏情况的时间复杂度，以及
O(log n)的最坏查找时间复杂度。
引用:
在Linux中有很多地方用到了RD树。anticipatory, deadline, 和CFQ I/O调度都使用
的是RB树进行请求跟踪，还有CD/DVD驱动的包管理也是如此。
高精度计时器（high-resolution timer）使用RB树组织定时请求。
EXT3文件系统也使用RB树来管理目录。
虚拟存储管理系统也是有RB树进行VMAs（Virtual Memory Areas）的管理。
当然还有文件描述符，密码钥匙，“等级令牌桶”调度的网络数据包都是用RB数据进
行组织和管理的。
相关资料：
Linux Weekly News article on red-black trees
http://lwn.net/Articles/184495/
Wikipedia entry on red-black trees
http://en.wikipedia.org/wiki/Red-black_tree
可见RB树（红黑树）在Linux内核中的重要性。
Linux内核的RB树实现
---------------------------------------
在Linux内核源代码中rb树的实现在lib/rbtree.c文件中，可以通过
#include "linux/rbtree.h"进行使用。
在Linux内核中的RB树实现与传统的实现方
1. 学会写简单的makefile
2. 编一些应用
程序
，可以用makefile跑起来
3. 学会写驱动
的makefile
4. 写一简单char驱动，makefile编译通过，可以insmod， lsmod， rmmod. 在驱动的init函数里打印hello world，insmod后应该能够通过dmesg看到输出
。
5. 写一完整驱动， 加上read， write， ioctl， polling等� ......
Linux 虚拟文件系统概观
作者 Richard Gooch <rgooch@atnf.cs.iro.au>
翻译 albcamus <albcamus@gmail.com>
最后更新:2007 年 6 月 24 日
版权:1999, Richard Gooch
版权:2005, Pekka Enberg
本文件以 GPLv2 许可发放
[翻译说明:Richard Gooch 的这份 Overview of ......
