底层架构解析：Nginx中ngx_radix_tree_t基数树的路由查找-Nginx-PHP中文网

nginx 的 ngx_radix_tree_t 是专用于 ip 地址最长前缀匹配的基数树，支持 ipv4/ipv6，用于 geo、map、limit_conn 等模块；其 o(32)/o(128) 查找效率远超哈希与红黑树，不支持 uri 或 host 匹配。

底层架构解析：nginx中ngx_radix_tree_t基数树的路由查找

在 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），以适配基数树的位级结构
树一旦构建完成，不支持运行时动态增删节点（配置重载时重建整棵树）