Redis5.0 基数树浅析

Redis5.0 基数树浅析,第1张

Redis5.0 基数树浅析

文章目录

前言应用数据结构

前言

Rax 是 Redis 内部比较特殊的一个数据结构,它是一个有序字典树(基数树 Radix Tree),按照 key 的字典序排列,支持快速地定位、插入和删除 *** 作。Redis 五大基础数据结构里面,能作为字典使用的有 hash 和 zset。hash 不具备排序功能,zset 则是按照 score 进行排序的。rax 跟 zset 的不同在于它是按照 key 进行排序的。

应用


你可以将一本英语字典看成一棵 radix tree,它所有的单词都是按照字典序进行排列,每个词汇都会附带一个解释,这个解释就是 key 对应的 value。有了这棵树,你就可以快速地检索单词,还可以查询以某个前缀开头的单词有哪些。
也可以将公安局的人员档案信息看成一棵 radix tree,它的 key 是每个人的身份z号,value 是这个人的履历。因为身份z号的编码的前缀是按照地区进行一级一级划分的,这点和单词非常类似。有了这棵树,你就可以快速地定位出人员档案,还可以快速查询出某个小片区都有哪些人。

数据结构

rax 中有非常多的节点,根节点、叶节点和中间节点,有些中间节点带有 value,有些中间节点纯粹是结构性需要没有对应的 value。

struct raxNode {
	int<1> isKey;// 是否没有key,没有key 的是根节点
	int<1> isNull; // 是否没有对应的value,无意义的中间节点
	int<1> isCompressed;// 是否压缩存储
	int<29> size; // 子节点的数量或者是压缩字符串的长度(isCompressed)
	byte[] data;// 路由键、子节点指针、value 都在这里
}

rax 是一棵比较特殊的 radix tree,它在结构上不是标准的 radix tree。如果一个中间节点有多个子节点,那么路由键就只是一个字符。如果只有一个子节点,那么路由键就是一个字符串。后者就是所谓的「压缩」形式,多个字符压在一起的字符串。比如前面的那棵字典树在 Rax 算法中将呈现出如下结构:

图中的深蓝色节点就是「压缩」节点。
接下来我们再细看 raxNode.data 里面存储的东西,它按照压缩与否分为两种结构。
压缩结构
子节点如果只有一个,那就是压缩结构,data 字段如下伪代码所示:

struct data {
	optional struct {	// 取决于 header 的 size 字段是否为零
	byte[] childKey; // 路由键
	raxNode* childNode;	// 子节点指针
	} child;
	optional string value;	// 取决于 header 的 isNull 字段
}

非压缩节点
如果子节点有多个,那就不是压缩结构,存在多个路由键,一个键是一个字符。

struct data {
	byte[] childKeys; // 路由键字符列表
	raxNode*[] childNodes;// 多个子节点指针
	optional string value;// 取决于header 的isNull 字段
}


如果子节点只有一个,并且路由键字符串的长度为 1,压缩和非压缩在数据结构表现形式上是一样的,不管 isCompressed 是0 还好是 1,结构都是一样的。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5712743.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-18
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存