图解基数树(RadixTree)

2022/04/23 14:14 下午 posted in  算法&数据结构

基数树(RadixTree),是一种比较有趣的数据结构,最近需要一种比较高效的查找,两度遇到了基数树,便整理下来给有相关需求的伙伴提供一种思路。

基本原理

对数据结构有些练习的小伙伴对字典树肯定不陌生,一句话解释基数树就是带压缩的字典树,从维基百科示例图中也可以明显看得这一点:

对于一般字典树(Trie),每条边是由一个字母组成,同样可以从维基百科中的示例图中看出字典树的一般规律:

因为基数树是对字典树的压缩,因此基本操作和字典树基本一致,只是多了节点的合并和分裂操作。下面我们就通过树的操作对比下基数树和字典树的不同。

新增值

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

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

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

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

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

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

删除值

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

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

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

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

查找

因为基数树的本质依然属于字典树,因此在查找使用上和字典树并无不同,只是因为基数树通过压缩,使得在前缀有一定规律的串在树中的深度更低,因此查找效率也较高。

近期的使用

基数树在很早之前就了解到,因为著名的 golang web 框架 gin 在 route 搜索上使用了该数据结构,所以在串查找上自然而然的想到了该数据结构。

串查找

近期的第一次相遇是在实现一个支持通配符的 EventBus 上,我预期实现一个 Golib 用于程序内部的事件驱动编程,使用方式类似:

func bobDoSomething() {
	fmt.Println("Bob do something")
}

func aliceDoSomething() {
	fmt.Println("Alice do something")
}

func main() {
	_, _ = bus.Subscribe("partner.bob.do", bobDoSomething)
	_, _ = bus.Subscribe("partner.alice.do", aliceDoSomething)
	bus.Publish("partner.*.do")
}

具体的 EventBus 的代码可以参考 https://github.com/hyponet/eventbus,这是一个非常轻量的事件库,其中基数树的逻辑实现在 bus/exchange.go 中。

对于没有通配符的场景,通过 Hash 是一种非常高效且简单的实现,但是如果考虑到通配符匹配,基于树的查找更适合。

考虑到事件的 Topic 本身就是一个规律性很强的串,因此非常适合使用基数树,比如对于如下 Topic:

sys.file.file1.create
sys.file.file1.delete
sys.dir.*.delete

可进行建树:

页缓存

近期的第二次和基数树相遇是在实现一个高效的缓存上,最近在思考如何实现一个通用且高效的文件缓存,突然意识到可以参考 Linux 的 PageCache,巧合的是,PageCache 居然也是使用的基数树。

Linux 的基数树实现在 lib/radix-tree.c 中,和上文提到的不同,Linux 并不是对一个字符串进行存储,而是一个无符号长整型名为 index 的值,可以从树操作的 Api 中看出:

// 插入值
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
// 删除值
void *radix_tree_delete(struct radix_tree_root *tree, unsigned long key);

Linux 的实现复杂但又精巧,全部展开的话估计又要新开一篇文章,简单来说,Linux 的 radix tree 是围绕下面三个参数展开的:

  • RADIX_TREE_MAP_SHIFT 定义基数,内核通过CONFIG选项,可设置为 4 或 6,默认为 6;
  • RADIX_TREE_MAP_SIZE 该数值定义指针数组 slot 的容量;
  • RADIX_TREE_MAP_MASK 使用移位与掩码操作实现位组提取;

这三个值之间的关系,可以用 Golang 下面的常量值表示:

const (
	RADIX_TREE_MAP_SHIFT    = 6
	RADIX_TREE_MAP_SIZE     = 1 << RADIX_TREE_MAP_SHIFT
	RADIX_TREE_MAP_MASK     = RADIX_TREE_MAP_SIZE - 1
)

要理解这三个参数的作用,首先要再次明确 Linux 基数树的存储值是无符号长整型,名为 index(而不是字符串)。对于一个数字来说,比如 16 位 int,无论其值大小,占用的 bit 数是固定的(都是 16 个 bit)。

int16(100)    // 二进制表示:0000000001100100
int16(1000)   // 二进制表示:0000001111101000

基数树的核心在于通过压缩控制树的深度,对于整形 index 来说,压缩的内容便是 bit 前缀。使用固定步长对 bit 进行右移时,可以获得确定长度的前缀。

int16(100)  // shift=12 treeLevel=0 val=0000
int16(1000) // shift=12 treeLevel=0 val=0000
int16(100)  // shift=6  treeLevel=1 val=0000000001
int16(1000) // shift=6  treeLevel=1 val=0000001111
int16(100)  // shift=0  treeLevel=2 val=0000000001100100
int16(1000) // shift=0  treeLevel=2 val=0000001111101000

如果每次右移一个固定步长后,树的深度加一,则树的深度也是固定的(比特位数/步长)。而 RADIX_TREE_MAP_SHIFT 就是 bit 位的步长,Linux 默认值为 6,其含义是每右移 6 个 bit 为一个单位,因此对于上面的数字,可以建树为:

RADIX_TREE_MAP_SIZERADIX_TREE_MAP_MASK 本质是在实现 hash 桶操作,前者定义了桶的大小,而后者进行 hash 运算(就是取余)。对 index 右移之后,可以通过 hash 桶操作,获取确定的子节点。

最简单的 hash 操作便是取余,RADIX_TREE_MAP_MASK 是一个小技巧,如下的两种写法是等效的:

(index >> shift) % RADIX_TREE_MAP_SIZE
(index >> shift) & RADIX_TREE_MAP_MASK

对于一个 index,可以通过如下 hash 计算,获取下一个节点:

slot := index >> currentNode.shift & RADIX_TREE_MAP_MASK
currentNode = currentNode.slots[slot]

最后,通过如下 int16 的若干 index 建树举例:

int16(60)     // 二进制表示:0000000000111100
int16(1000)   // 二进制表示:0000001111101000
int16(10000)  // 二进制表示:0010011100010000
int16(55520)  // 二进制表示:1101100011100000
int16(65001)  // 二进制表示:1111110111101001

可以建树为:

以 index=1000 举例注释:

  1. 1000 >> 12 % 64 == 0 所以在 slots[0]
  2. 1000 >> 6 % 64 == 15 所以在 slots[15]
  3. 1000 >> 0 % 64 == 40 所以在 slots[40]

Linux 的基数树实现非常复杂,因为 radix-tree.c 是一个公共方法,除了页缓存,IP 寻址也用到了该逻辑,可能过于抽象,阅读起来的确很不好理解,不过我实现了一个精简的版本,可以在 https://github.com/basenana/nanafspkg/files/chain.go 中找到(也可以仓库内搜 pageCacheChain)。