基数树(Radix Tree)

定义

基数树(Radix Tree,又称压缩前缀树、Patricia Trie)是字典树的空间优化版本:把只有一个孩子的连续节点链合并,让每条边携带一段字符串而非单个字符,从而消除冗余节点。Patricia 一词源于 Morrison 于 1968 年的论文。

原理

查找沿边逐段比较公共前缀;插入时若新键与现有边部分匹配,则在分歧点分裂该边。以比特为单位的二进制基数树每个内部节点恰有两个分支,常用于 IP 地址这类定长键。

应用

路由器的最长前缀匹配(IP 路由表)是基数树最经典的用途;Linux 内核用 radix tree(及其后继 xarray)索引页缓存;Go 语言的 httprouter、Gin 框架用基数树做 URL 路由匹配;Redis Stream 的底层索引 rax 也是基数树。

优缺点

优点是比朴素 Trie 省空间、前缀查询天然高效、键有序;缺点是边分裂逻辑比普通 Trie 复杂,稀疏长键场景下仍不如哈希表的平均查找速度。