一、ngx_queue_t双向链表
1.ngx_queue_t容器的优势在于:
1) 实现了排序功能;
2) 它非常轻量级，是一个纯粹的双向链表。它不负责链表元素所占内存的分配，与Nginx封装的ngx_pool_t内存池完全无关。
3) 支持两个链表间的合并。
typedef struct ngx_queue_s ngx_queue_t;struct ngx_queue_s {ngx_queue_t *prev;ngx_queue_t *next;};
2.ngx_queue_t容器提供的操作方式
3.ngx_queue_t双向链表容器所支持的方法
4. ngx_queue_t双向链表中的元素所支持的方法
5.空容器时ngx_queue_t结构体成员的值
6.当仅含1个元素时，容器、元素中的ngx_queue_t结构体成员的值
7.当含有两个或多个元素时，容器、元素中的ngx_queue_t结构体中prev、next成员的值
二、ngx_array_t动态数组
ngx_array_t是一个顺序容器，它在Nginx中大量使用。ngx_array_t容器以数组的形式存储元素，并支持在达到数组容量的上限时动态改变数组的大小。
优点:
1)访问速度快
2)允许元素个数具备不确定性;
3)负责元素占用内存的分配，这些内存将由内存池统一管理。
1.ngx_array_t动态数组的实现仅使用1个结构体，如下:
typedef struct ngx_array_s ngx_array_t;struct ngx_array_s {//elts指向数组的首地址void *elts;//nelts是数组中已经使用的元素个数ngx_uint_t nelts;//每个数组元素占用的内存大小size_t size;//当前数组中能够容纳元素个数的总大小ngx_uint_t nalloc;//内存池对象ngx_pool_t *pool;};
2.ngx_array_t动态数组结构体中的成员及其提供的方法
3.ngx_array_t动态数组提供的方法
三、ngx_list_t单向链表
相当于动态数组与单向链表的结合体。
四、ngx_rbtree_t红黑树
ngx_rbtree_t是使用红黑树实现的一种关联容器，Nginx的核心模块(如定时器管理、文件缓存模块等)在需要快速检索、查找的场合下都使用了ngx_rbtree_t容器。
顺序容器的检索效率通常情况下都比较差，一般只能遍历检索指定元素。当需要容器的检索速度很快，或者需要支持范围查询时，ngx_rbtree_t红黑树容器是一个非常好的选择。
什么是自平衡二叉查找树?在不断地向二叉查找树中添加、删除节点时，二叉查找树自身通过形态的变换，始终保持着一定程度上的平衡，即为自平衡二叉查找树。自平衡二叉查找树有许多种不同的实现方式，如AVL树和红黑树。红黑树是一种自平衡性较好的二叉查找树，它在Linux内核、C++的STL库等许多场合下都作为核心数据结构使用。
ngx_rbtree_t红黑树容器中的元素都是有序的，它支持快速的检索、插入、删除操作，也支持范围查询、遍历等操作，是一种应用场景非常广泛的高级数据结构。
红黑树是指每个节点都带有颜色属性的二叉查找树，其中颜色为红色或黑色。除了二叉查找树的一般要求以外，对于红黑树还有如下的额外的特性。
特性1:节点时红色或黑色。
特性2:根节点是黑色。
特性3:所有叶子节点都是黑色(叶子是NIL节点，也叫“哨兵”)。
特性4:每个红色节点的两个子节点都是黑色(每个叶子节点到根节点的所有路径上不能有两个连续的红色节点)>
特性5:从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
1.ngx_rbtree_t红黑树的典型图示
2.红黑树节点的结构体及其提供的方法
3.ngx_rbtree_node_t结构体的定义
typedef struct ngx_rbtree_s ngx_rbtree_t;/*为解决不同节点含有相同关键字的元素冲突问题，红黑树设置了ngx_rbtree_insert_pt指针，这样可灵活地添加冲突元素 */typedef void (*ngx_rbtree_insert_pt)(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);struct ngx_rbtree_s {//指向树的根节点。注意，根节点也是数据元素ngx_rbtree_node_t *root;//指向NIL哨兵节点ngx_rbtree_node_t *sentinel;//表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增ngx_rbtree_insert_pt insert;};
ngx_rbtree_t结构体的root成员指向根节点，而sentinel成员指向哨兵节点。
4.Nginx为红黑树已经实现好的3种数据添加方法
5.ngx_str_rbtree_insert_value的实现
五、ngx_radix_tree_t基数树
详见资料
六、支持通配符的散列表
6.1 ngx_hash_t基本散列表
详见资料
6.2 支持通配符的散列表
详见资料
