Radix Tree（基数树） 和 Patricia Trie（Practical Algorithm To Retrieve Information Coded In Alphanumeric） 是两种高度相关的压缩前缀树结构，常被混用，但在严格定义下存在细微差别。它们在 IP 路由、数据库索引、搜索引擎等领域广泛应用。

下面从定义、异同、优缺点及适用场景进行系统对比：

🔍 一、核心定义与关系
名称 定义 特点
Radix Tree 一种压缩的 Trie，按字符或位串分段，合并单子节点路径 - 边可为任意长度字符串- 支持任意字母表

Patricia Trie Radix Tree 的特例，每次分裂恰好在一个位（bit）或字符上，确保每个内部节点至少有两个子节点 - 更严格的压缩- 常用于二进制键（如 IP 地址）

✅ 通俗理解：
所有 Patricia Trie 都是 Radix Tree
但并非所有 Radix Tree 都是 Patricia Trie
Patricia = Radix Tree + 最大化压缩（无单子节点）

✅ 二、共同优点（vs 普通 Trie）

内存高效
合并单链路径 → 节点数大幅减少
典型节省：50%~90% 内存

查询更快（缓存友好）
树高降低 → 指针跳转次数减少
节点更少 → 更大概率驻留 CPU 缓存

支持前缀匹配 & 范围查询
天然支持 startswith、longest prefix match（如路由表）

⚖️ 三、Radix Tree vs Patricia Trie：关键区别
维度 Radix Tree Patricia Trie
边的粒度 任意长度字符串（如 “apple”） 固定粒度：- 字符级（Classic Patricia）- 位级（Binary Patricia，最常见）

分裂方式 在最长公共前缀处分裂 在第一个差异位/字符处分裂

内部节点 可能有单子节点（若未完全压缩） 严格保证 ≥2 子节点

典型应用 字符串字典、文件路径 IP 路由（32/128 位）、数据库索引

实现复杂度 中等 高（需处理位操作）

✅ 四、各自优点与缺点

🌟 Radix Tree 优点
灵活：支持任意字符串（Unicode、URL、文件名）
直观：边为可读字符串，调试方便
构建简单：插入时按 LCP（最长公共前缀）分裂即可

❌ Radix Tree 缺点
边匹配开销：需字符串比较（若出边多）
内存碎片：每条边可能分配独立字符串
非最优压缩：若实现不彻底，仍保留单子节点

🌟 Patricia Trie 优点
极致压缩：绝对无单子节点，节点数最小
位级操作高效：对二进制键（如 IP）可直接位运算
确定性结构：相同输入必得相同树形（利于持久化）

💡 Linux 内核的 fib_trie 就是 Patricia Trie，用于 IPv4/IPv6 路由

❌ Patricia Trie 缺点
实现复杂：
需处理位偏移、掩码
插入/删除涉及多级指针调整
仅适合定长键：如 32 位 IP、64 位哈希值
不直观：边是位偏移，难以人工解析

📊 五、性能对比（以 IP 路由为例）
操作 普通 Trie Radix Tree Patricia Trie
查询时间 O(32) 次跳转 O(5~10) 次 O(1~5) 次

内存占用 高（稀疏） 中 最低

插入复杂度 简单 中等 复杂

范围查询 支持 支持 高效支持

✅ 在 BGP 路由表（50 万+ 条目） 中，Patricia Trie 比普通 Trie 快 10 倍以上

🧪 六、代码示例对比

Radix Tree（字符串边）
class RadixNode {
Map children = new HashMap();
boolean isWord;
}
// 插入 “apple” → 边 “apple”

Patricia Trie（位级，简化版）
struct patricia_node {
int bit; // 分裂位（0~31 for IPv4）
struct patricia_node *left, *right;
uint32_t key; // 存储完整 IP
};
// 插入 192.168.1.1 → 按 bit 0,1,2… 逐位分裂

✅ 七、如何选择？
场景 推荐结构
字符串字典 / 自动补全 Radix Tree（灵活、易实现）✅

IP 路由 / CIDR 匹配 Patricia Trie（位级） ✅

数据库索引（定长键） Patricia Trie 或 B+ 树

LeetCode 算法题 普通 Trie（足够）⚠️

极致内存优化 DAFSA（后缀共享）> Patricia > Radix

✅ 总结
特性 Radix Tree Patricia Trie
通用性 ⭐⭐⭐⭐⭐（任意字符串） ⭐⭐（定长二进制键）

压缩率 ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐

实现难度 ⭐⭐ ⭐⭐⭐⭐

查询速度 ⭐⭐⭐⭐ ⭐⭐⭐⭐⭐

工业应用 搜索引擎、文件系统 网络路由、内核

💡 一句话口诀：
“字符串用 Radix，IP 用 Patricia；要简单选前者，要极致选后者。”

两者都是 Trie 的高效变体，在正确场景下能带来数量级的性能提升。理解其差异，方能合理选型。