Nginx 的 ngx_radix_tree_t 是专用于 IP 地址最长前缀匹配的基数树，支持 IPv4/IPv6，用于 geo、map、limit_conn 等模块；其 O(32)/O(128) 查找效率远超哈希与红黑树，不支持 URI 或 host 匹配。
在 Nginx 的核心路由匹配机制中，ngx_radix_tree_t 是一个轻量、高效、专为 IP 地址（IPv4/IPv6）前缀匹配设计的基数树（Radix Tree），而非通用字符串路由（如 location 匹配）。它不处理 URI 路径或 host 名，只负责 网络层地址的最长前缀匹配（LPM），典型用于 geo、map（IP 段映射）、limit_conn（按 IP 限连）等模块的快速查表。
为什么用基数树而不是哈希或红黑树？
IP 前缀匹配本质是“掩码逐位比较 + 最长匹配”，哈希无法支持前缀语义，红黑树虽可排序但范围查找效率低。基数树天然适合：
- 每个节点代表 1 位（IPv4 共 32 层，IPv6 共 128 层），路径即二进制前缀
- 叶子节点存储用户数据（如 geo 的 value、limit_conn 的连接计数器）
- 查找只需按 IP 二进制位一路向下，时间复杂度 O(32) 或 O(128)，恒定且极快
- 内存紧凑：Nginx 实现中采用“压缩”策略，连续相同分支合并为单节点，大幅减少空节点
树结构与关键字段解析
ngx_radix_tree_t 本身只含根节点指针和一个内存池引用：
typedef struct ngx_radix_node_s ngx_radix_node_t;
struct ngx_radix_node_s {
ngx_radix_node_t *left; // 位为 0 时的子节点
ngx_radix_node_t *right; // 位为 1 时的子节点
ngx_uint_t value; // 叶子节点：用户绑定的值（如 geo 的整型 value）
ngx_uint_t count; // 子树中叶子总数（用于快速剪枝）
};
注意：非叶子节点的 value 恒为 0，仅叶子有效；count 用于插入/删除时快速判断是否需回收空子树。
查找过程：从高位到低位逐位导航
以 IPv4 查找为例（假设 IP = 192.168.5.10，二进制 11000000 10101000 00000101 00001010）：
- 从根节点开始，取最高位（bit 31）= 1 → 走
right分支 - 取次高位（bit 30）= 1 → 继续
right - ……持续 32 次，每一步根据当前位选择 left/right
- 过程中，**只要遇到 value ≠ 0 的节点，就记录为候选结果**（因基数树不保证最深才是最长前缀）
- 最终停在第 32 层节点；返回所有候选中 depth 最大的那个（即最长前缀匹配）
Nginx 实际实现会提前终止：若某层节点 count == 0，说明该子树无有效前缀，直接回退；查找函数返回的是匹配到的 value，不是节点指针。
实际应用中的限制与注意点
这不是通用路由引擎 —— 它不支持通配符、正则、host 名或 URI 路径。常见误区：
-
geo $country { default ZZ; 192.168.0.0/16 CN; }→ 底层调用ngx_radix32tree_find() -
limit_conn addr 10;中的addr变量若来自$binary_remote_addr，也走 radix 树查限流键 - 添加 /24 网段时，Nginx 会将其拆解为多个更短前缀（如 /24 可能被优化为若干 /28），以适配基数树的位级结构
- 树一旦构建完成，不支持运行时动态增删节点（配置重载时重建整棵树）
