Nginx高级数据结构简介

th.jpeg

Nginx的两个特点：跨平台和C实现

这两个特点导致Nginx不宜使用第三方中间件的容器，因此Nginx的作者将基础的数据结构和算法从头实现了一遍(或许这就是大佬啊)，本文试图基于《深入理解Nginx》，对Nginx提供的高级数据结构做一个小总结。

总的来说，Nginx实现了6中基本容器，分别是：

• 双向链表(ngx_queue_t)
• 动态数组(ngx_array_t)
• 单向链表(ngx_list_t)
• 红黑树(ngx_rbtree_t)
• 基数树(ngx_radix_tree_t)
• 支持通配符的散列表

0.概览

1. 双向链表
   双向链表是Nginx提供的轻量级链表容器，它与Nginx内存池无关，因此不要指望双向链表为你分配内存空间，它只能为你存储已经分配好内存的元素，它只做元素间的连接工作。双向链表虽然功能很简单，但它量级很轻，只要求用户数据增加两个指针域即可。除此之外，它还提供了简易的插入排序算法。

2. 动态数组
   Nginx的动态数组类似于STL中的vector，它使用连续内存存储元素，所以按下标随机存取效率很高。 相比数组，动态数组的优势是动态扩容，当容量达到最大值时自动扩容(扩容算法与vector不同)。另外，动态数组负责内存分配。它在支持通配符的散列表中有所应用。

3.单向链表
单向链表与双向链表是完全不同的。首先，它负责内存分配，这一点与动态数组相同，但是它使用不连续空间存储元素，有点像“数组+单链表”。

4.红黑树
红黑树是一种十分高效的高级数据结构，Linux中作为核心数据结构存在。检索时不必遍历整个容器，查找的时间仅跟树的高度有关。与散列表相比，它支持范围查询。Nginx的许多模块都用到了红黑树，在需要快速检索元素的场景中，首先考虑是不是可以用红黑树。

5. 基数树
   与红黑树一样，基数树也是一种二叉查找树，具备红黑树同样的高效特点。但是基数树的应用场景比红黑树要窄，因为基数树要求必须以整型(long)作为关键字。但由于基数树插入、删除时不需要旋转操作，因此其变更效率比红黑树高。使用也比红黑树简单许多。

6. 支持通配符的散列表
   这是Nginx的独创。Nginx首先实现了一般的散列表，然后在其基础上根据web服务器的特点，针对URL场景设计了支持通配符的散列表。不过，只支持前置和后置两种匹配模式，即只支持".baidu.com"和"www.baidu."两种模式。这种散列表实现较为复杂。