7.6　ngx_radix_tree_t基数树

基数树也是一种二叉查找树，然而它却不像红黑树一样应用广泛（目前官方模块中仅geo模块使用了基数树）。这是因为ngx_radix_tree_t基数树要求存储的每个节点都必须以32位整型作为区别任意两个节点的唯一标识，而红黑树则没有此要求。ngx_radix_tree_t基数树与红黑树不同的另一个地方：ngx_radix_tree_t基数树会负责分配每个节点占用的内存。因此，每个基数树节点也不再像红黑树中那么灵活——可以是任意包含ngx_rbtree_node_t成员的结构体。基数树的每个节点中可以存储的值只是1个指针，它指向实际的数据。

本节将以一棵完整的ngx_radix_tree_t基数树来说明基数树的原理和用法，这棵树的深度为3，它包括以下4个节点：0X20000000、0X40000000、0X80000000、0Xa0000000。这里书写成十六进制是为了便于理解，因为基数树实际是按二进制位来建立树的，上面4个节点如果转换为十进制无符号整型（也就是7.6.3节例子中的ngx_uint_t），它们的值分别是536870912、1073741824、2147483648、2684354560；如果转换为二进制，它们的值分别为：00100000000000000000000000000000、01000000000000000000000000000000、1000000000 0000000000000000000000、11000000000000000000000000000000。在图7-9中，可以看到这4个节点如何存储到深度为3的基数树中。

7.6.1　ngx_radix_tree_t基数树的原理

基数树具备二叉查找树的所有优点：基本操作速度快（如检索、插入、删除节点）、支持范围查询、支持遍历操作等。但基数树不像红黑树那样会通过自身的旋转来达到平衡，基数树是不管树的形态是否平衡的，因此，它插入节点、删除节点的速度要比红黑树快得多！那么，基数树为什么可以不管树的形态是否平衡呢？

红黑树是通过不同节点间key关键字的比较来决定树的形态，而基数树则不然，它每一个节点的key关键字已经决定了这个节点处于树中的位置。决定节点位置的方法很简单，先将这个节点的整型关键字转化为二进制，从左向右数这32个位，遇到0时进入左子树，遇到1时进入右子树。因此，ngx_radix_tree_t树的最大深度是32。有时，数据可能仅在全部整型数范围的某一小段中，为了减少树的高度，ngx_radix_tree_t又加入了掩码的概念，掩码中为1的位节点关键字中有效的位数同时也决定了树的有效高度。例如，掩码为11100000000000000000000000000000（也就是0Xe0000000）时，表示树的高度为3。如果1个节点的关键字为0X0fffffff，那么实际上对于这棵基数树而言，它的节点关键字相当于0X00000000，因为掩码决定了仅前3位有效，并且它也只会放在树的第三层节点中。

如图7-9所示，0X20000000这个节点插到基数树后，由于掩码是0Xe0000000，因此它决定了所有的节点都将放在树的第三层。下面结合掩码看看节点是如何根据关键字来决定其在树中的位置的。掩码中有3个1，将节点的关键字0X20000000转化为二进制再取前3位为010，然后分3步决定节点的位置。

❑首先找到根节点，取010的第1位0，表示选择左子树。

❑第2位为1，表示再选择右子树。

❑第3位为0，表示再选择左子树，此时的节点就是第三层的节点，这时会用它来存储0X20000000这个节点。

图　7-9　3层基数树示意图

ngx_radix_tree_t基数树的每个节点由ngx_radix_node_t结构体表示，代码如下所示。

typedef struct ngx_radix_node_s ngx_radix_node_t；

struct ngx_radix_node_s{

//指向右子树，如果没有右子树，则值为null空指针

ngx_radix_node_t*right；

//指向左子树，如果没有左子树，则值为null空指针

ngx_radix_node_t*left；

//指向父节点，如果没有父节点，则（如根节点）值为null空指针

ngx_radix_node_t*parent；

/value存储的是指针的值，它指向用户定义的数据结构。如果这个节点还未使用，value的值将是NGX_RADIX_NO_VALUE/

uintptr_t

value；

}；

如图7-9所示，value字段指向用户自定义的、有意义的数据结构。另外，基数树也不像红黑树一样还有哨兵节点。基数树节点的left和right都是有可能为null空指针的。

与红黑树不同的是，红黑树容器不负责分配每个树节点的内存，而ngx_radix_tree_t基数树则会分配ngx_radix_node_t结构体，这样使用ngx_radix_node_t基数树时就会更简单一些。但ngx_radix_node_t基数树是如何管理这些ngx_radix_node_t结构体的内存呢？下面来看一下ngx_radix_node_t容器的结构，代码如下。

typedef struct{

//指向根节点

ngx_radix_node_t*root；

//内存池，它负责给基数树的节点分配内存

ngx_pool_t

*pool；

/管理已经分配但暂时未使用（不在树中）的节点，free实际上是所有不在树中节点的单链表/

ngx_radix_node_t*free；

//已分配内存中还未使用内存的首地址

char

*start；

//已分配内存中还未使用的内存大小

size_t

size；

}ngx_radix_tree_t；

上面的pool对象用来分配内存。每次删除1个节点时，ngx_radix_tree_t基数树并不会释放这个节点占用的内存，而是把它添加到free单链表中。这样，在添加新的节点时，会首先查看free中是否还有节点，如果free中有未使用的节点，则会优先使用，如果没有，就会再从pool内存池中分配新内存存储节点。

对于ngx_radix_tree_t结构体来说，仅从使用的角度来看，我们不需要了解pool、free、start、size这些成员的意义，仅了解如何使用root根节点即可。