Nginx源代码学习：490行代码的教科书级实现：Nginx红黑树源码中我发现的6个精妙设计

一、为什么要读这490行代码

红黑树大概是每个程序员都"学过但没真正理解"的数据结构。

算法课上讲过五条性质、左旋与右旋两种旋转、若干种插入删除情况，考试也考过，但说实话，真正能手写一棵完整红黑树的人并不多。大部分人的红黑树知识停留在"平衡二叉搜索树，增删查都是O(log n)"这个层面——知道它好用，但不清楚它到底怎么实现的，更不清楚工业级代码里的红黑树和教科书上的有什么区别。

Nginx的红黑树实现是一个绝佳的学习样本。整个实现只有两个文件：ngx_rbtree.h（87行）和ngx_rbtree.c（405行），加起来不到500行，但功能完整——插入、删除、旋转、中序遍历、查找最小值，一个不少。源码注释开门见山地写着：

The red-black tree code is based on the algorithm described in the “Introduction to Algorithms” by Cormen, Leiserson and Rivest.

直接标明了算法来源是Cormen等人的《算法导论》（注意这里只列了三位作者，没有后来加入的Stein，说明Nginx参考的是1990年的第一版，那时候这本书还叫CLR而不是CLRS）。教科书的算法，工业级的实现——这个组合让它既有理论上的严谨性，又有工程上的实用价值。

在Nginx内部，红黑树承担着几个关键角色：定时器管理（所有超时事件按到期时间排序，快速找到最近的超时事件）、事件查找