Trie / Radix TreePrefix index

按键的前缀分支；压缩变体合并单分支路径。

核心约束: 共享前缀共享路径；节点表示的前缀必须一致。
适用问题: IP 前缀、token 前缀、字符串前缀匹配。
边界与取舍: 路径压缩、粒度和节点表示随项目变化。

常见操作#

L 为键长，S 为所有键的总长度，R 为字母表大小；固定整数索引可令 L 为位数。

操作	时间复杂度	条件与说明
Trie：精确查找 / 插入 / 删除	$O(L)$	每层分支选择 $O(1)$ ，例如固定字母表的数组；删除可沿路径清理空节点。
压缩 Radix：精确查找 / 插入 / 删除	$O(L)$	总共比较的边标签长度受键长约束，分支选择为 $O(1)$ ；插入可能拆分压缩边。
最长前缀匹配	$O(L)$	沿键路径前进并记录最近终止节点，不是普通字符串子串匹配。
按前缀枚举	定位 $O(L)$ ，再加子树遍历与输出成本	输出所有匹配键的成本与结果总字符数有关；稠密子节点数组还需扫描空槽。

时间与空间#

时间复杂度: 键操作 $O(L)$ ，取决于分支表示
存储空间: 稀疏 Trie $O(S)$ ；稠密子节点数组 $O(RS)$

压缩路径可减少节点；若分支用平衡字典，路径成本还需乘各节点分支查找开销。

概念与变体#

Trie: 沿键的组成单位逐层分支，共享前缀共享路径。
压缩 Radix Tree: 合并只有单个分支的路径；节点可能代表多位或多个字符。

工程中的应用#

2 个案例 · 附源码

nginx·Geo 地址匹配release-1.26.3

按 IP 最长前缀选择配置值

nginx geo 的 CIDR 模式使用二进制 radix tree，为请求地址查找最具体的网络前缀配置。

Trie / Radix Tree

附源码片段 · 索引与查找

SGLang·RadixAttention70528762bf0800793dab10d1b51d40f21a0608ba · 2024-01-17

RadixAttention：共享请求前缀

用压缩前缀树组织 token 序列，让多轮对话和分支生成共享已有 KV。

Trie / Radix Tree LRU 淘汰

附源码片段 · 缓存与复用

基础原理参考资料

Princeton · TriesR 向 Trie 的查找、前缀枚举及字符表对空间的影响。

Redis rax · Design压缩边、节点分裂及内存布局的具体实现。