白话Nginx中最常用的数据结构之红黑树篇

之前我们在 Nginx之进程间通信-共享内存篇 里提到在进程间通信的时候，经常在红黑树上管理一些对象，红黑树的使用场景：比如限速，流控，缓存等。 因为这些场景需要快速增加 删除节点。

我们先来明确一下红黑树的定义：它首先是一棵二叉查找树，也就是说任一节点的左侧数据都会小于当前节点，右侧数据大于当前节点。

而极端情况下一颗二叉查找树会退化成一根链表。如图：

所以红黑树还有以下特点：

1）从名字就能看出，红黑树的节点是有颜色的分为红色和黑色。

2）根节点是黑色。

3）所有的叶子节点都是黑色（叶子是NIL节点）。

4）每个红色节点必须有两个黑色的子节点（不存在两个连续的红色节点）。

5）从任一节点到它的每个叶子节点的所有路径都包含相同数目的黑色节点。

除了以上特性，红黑树还有以下优点：

1. 高度不会超过2倍log(n)
2. 增删改查算法复杂度O(log(n))
3. 遍历复杂度O(n)

Nginx中红黑树有相关结构体介绍:

// 红黑树节点结构体
typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

struct ngx_rbtree_node_s {
    ngx_rbtree_key_t       key;
    ngx_rbtree_node_t     *left;
    ngx_rbtree_node_t     *right;
    ngx_rbtree_node_t     *parent;
    u_char                 color;
    u_char                 data;
};

字段说明如下：

key：节点的键值，这是一个数字，在比较红黑树节点大小时使用。

left：指向当前节点的左节点。

right：指向当前节点的右节点。

parent：指向当前节点的父节点。

color：当前节点的颜色。

data：节点的数据。

typedef struct ngx_rbtree_s  ngx_rbtree_t;
// 红黑树结构体
struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};

字段说明如下：

root：红黑树的根节点。

sentinel：哨兵指针，始终指向红黑树的叶子节点。

insert：函数指针，添加数据时被调用，用来计算被添加节点的插入位置。

示意图如下：

红黑树的第4、第5条性质保证了红黑树的平衡性。

所以在红黑树插入、删除任一节点之后要通过旋转等操作来保证当前树仍符合基本的5条性质。

下面来一起学习一下红黑树的相关操作。

#define ngx_rbtree_init(tree, s, i)                                           \
    ngx_rbtree_sentinel_init(s);                                              \
    (tree)->root = s;                                                         \
    (tree)->sentinel = s;                                                     \
    (tree)->insert = i

从代码中 我们可以看到初始化的红黑树时，需要一个函数指针，用于插入时调用，赋值到insert字段。还需要一个哨兵节点，并且将根节点root也指向了这个节点。