1.简介

基数树（Radix Trie）也叫基数特里树或压缩前缀树，是一种多叉树，一种更节省空间的 Trie（前缀树）。

基数树中作为唯一子结点的每个结点都与其父结点合并，每个内部结点的子结点数最多为基数树的基数 r，r 为正整数且等于2^n(n>=1)。这使得基数树更适用于对于较小的集合（尤其是字符串很长的情况下）和有很长相同前缀的字符串集合。

不像一般的 Trie，基数树的边可以是一个或者多个元素。

2.为什么要设计基数树？

举个例子，一目了然。对于下面四个kv键值对，我们如何存储？

<0101,"abc">
<010,"abcd">
<001,"bcde">
<0110,"cdef">

有人说用hash表，是可以，但是hash表有两个问题：
1.hash冲突。hash函数不好设计，容易产生冲突，需要解决hash冲突
2.hash表大小不好确定。hash表底层还是数组实现的，数组的大小不好确定，涉及到扩容的问题

如果用 Radix Tree 就很容易解决上面两个问题，看下图：

上图就是 r=2 的基数树。是否似曾相识？没错，字典树(Trie Tree)就是 r=26 的基数树。或者说基数树是字典树的一个扩展。

当 key 的长度很大，那这棵树岂不是很高？比如 key=01110001010001010101101。为了减少树的高度，一般用多个比特位作为一个节点，但多比特位会使槽位变多，增大节点的体积，一般用 2-4 个比特作为一个节点。如图：

上图是 r=4 的基数树。

3.应用

Radix 树主要用于字符串的存储和检索，常见的应用包括：

• 前缀匹配和自动补全：Radix 树可以用于实现前缀匹配和自动补全功能，比如搜索引擎中的搜索提示和自动完成。
• 模式匹配和字符串搜索：Radix 树可以用于实现模式匹配和字符串搜索功能，比如文本编辑器中的搜索和替换功能。
• IP 路由：Radix 树可以用于将 IP 地址映射为其对应的路由器，从而实现高效的路由和负载均衡。
• 数据库索引和查询优化：Radix 树可以用于实现数据库索引和查询优化，比如在 NoSQL 数据库中存储 JSON 数据。
• 文件系统的路径匹配：Radix 树可以用于实现文件系统中的路径匹配，比如 Unix 文件系统中的路径解析。

此外，著名的 Golang Web 框架 Gin 在 route 搜索上便使用了基数树。

4.操作

Radix tree支持插入、删除、搜索等方面的操作。

插入

插入操作是添加一个新的字符串到 Trie 树中并尝试最小化数据存储（即对某些节点进行合并）。

对于一颗空树的初始状态，基数树和字典树是一致的，只有 root 节点。

对基数树和字典树插入相同的字符串【abcd】，因为新子串无额外分叉，因此可以对子串压缩。

对基数树和字典树插入相同的字符串【abce】，当基数树的某一个节点需要分叉时，则对该节点进行分裂后再加入新节点。

对基数树和字典树插入相同的字符串【aecb】。

对基数树和字典树插入相同的字符串【aecd】。

如上图的结果，基数树在这组 case 中，比字典树的深度少 1。以牺牲建树过程中的额外引入分裂操作，来优化查找时的效率。

删除

基于上文中的树，对基数树和字典树删除相同的字符串【abcd】，可以看到因为节点(bc)的分叉消失，因此和子节点合并为(bce)。

对基数树和字典树删除相同的字符串【abce】，同理，节点(a)和其子节点(ec)合并为(aec)。

对基数树和字典树删除相同的字符串【aecb】。

对基数树和字典树删除相同的字符串【aecd】后，两树为空。

查找

因为基数树的本质依然属于字典树，因此在查找使用上和字典树并无不同。从根节点开始遍历字符串，对于每个字符，检查当前节点的子节点是否包含该字符，如果包含，则继续遍历下一个字符，否则说明该字符串不存在于 Radix 树中。

Radix 树的查找操作相对于 Trie 树的查找操作有一个优点，因为基数树通过压缩，使得在前缀有一定规律的串在树中的深度更低，因此查找效率也较高。

5.小结

Radix 树是一种高效存储和搜索字符串的数据结构，它通过一些优化策略实现了比 Trie 树更好的时间和空间复杂度。Radix 树的节点代表字符串的前缀，具有一些特殊的性质，可以应用于很多领域，比如路由和负载均衡、前缀匹配和自动补全、模式匹配和字符串搜索、数据库索引和查询优化、文件系统中的路径匹配

---

参考文献

OpenAI ChatGPT
Radix tree - Wikipedia
基数树(Radix Tree) - 掘金
图解基数树(RadixTree) - 梦旭随想