共计 1978 个字符,预计需要花费 5 分钟才能阅读完成。
Redis 实现了不定长压缩前缀的 radix tree,用在集群模式下存储 slot 对应的的所有 key 信息。本文将详述在 Redis 中如何实现 radix tree。
核心数据结构
raxNode 是 radix tree 的核心数据结构,其结构体如下代码所示:
typedef struct raxNode {
uint32_t iskey:1;
uint32_t isnull:1;
uint32_t iscompr:1;
uint32_t size:29;
unsigned char data[];} raxNode;
-
iskey:表示这个节点是否包含 key
- 0:没有 key
- 1:表示从头部到其父节点的路径完整的存储了 key,查找的时候按子节点 iskey= 1 来判断 key 是否存在
- isnull:是否有存储 value 值,比如存储元数据就只有 key,没有 value 值。value 值也是存储在 data 中
- iscompr:是否有前缀压缩,决定了 data 存储的数据结构
- size:该节点存储的字符个数
- data:存储子节点的信息
-
- iscompr=0:非压缩模式下,数据格式是:
[header strlen=0][abc][a-ptr][b-ptr][c-ptr](value-ptr?)
,有 size 个字符,紧跟着是 size 个指针,指向每个字符对应的下一个节点。size 个字符之间互相没有路径联系。 - iscompr=1:压缩模式下,数据格式是:
[header strlen=3][xyz][z-ptr](value-ptr?)
,只有一个指针,指向下一个节点。size 个字符是压缩字符片段
- iscompr=0:非压缩模式下,数据格式是:
Rax Insert
以下用几个示例来详解 rax tree 插入的流程。假设 j 是遍历已有节点的游标,i 是遍历新增节点的游标。
场景一:只插入 abcd
z-ptr 指向的叶子节点 iskey=1,使用了压缩前缀。
场景二:在 abcd 之后插入 abcdef
从 abcd 父节点的每个压缩前缀字符比较,遍历完所有 abcd 节点后指向了其空子节点,j = 0,i < len(abcded)。
查找到 abcd 的空子节点,直接将 ef 赋值到子节点上,成为 abcd 的子节点。ef 节点被标记为 iskey=1,用来标识 abcd 这个 key。ef 节点下再创建一个空子节点,iskey= 1 来表示 abcdef 这个 key。
场景三:在 abcd 之后插入 ab
ab 在 abcd 能找到前两位的前缀,也就是 i =len(ab),j < len(abcd)。
将 abcd 分割成 ab 和 cd 两个子节点,cd 也是一个压缩前缀节点,cd 同时被标记为 iskey=1,来表示 ab 这个 key。
cd 下挂着一个空子节点,来标记 abcd 这个 key。
场景四:在 abcd 之后插入 abABC
abcABC 在 abcd 中只找到了 ab 这个前缀,即 i < len(abcABC),j < len(abcd)。这个步骤有点复杂,分解一下:
- step 1:将 abcd 从 ab 之后拆分,拆分成 ab、c、d 三个节点。
- step 2:c 节点是一个非压缩的节点,c 挂在 ab 子节点上。
- step 3:d 节点只有一个字符,所以也是一个非压缩节点,挂在 c 子节点上。
- step 4:将 ABC 拆分成了 A 和 BC,A 挂在 ab 子节点上,和 c 节点属于同一个节点,这样 A 就和 c 同属于父节点 ab。
- step 5:将 BC 作为一个压缩前缀的节点,挂在 A 子节点下。
- step 6:d 节点和 BC 节点都挂一个空子节点分别标识 abcd 和 abcABC 这两个 key。
场景五:在 abcd 之后插入 Aabc
abcd 和 Aabc 没有前缀匹配,i = 0,j = 0。
将 abcd 拆分成 a、bcd 两个节点,a 节点是一个非压缩前缀节点。
将 Aabc 拆分成 A、abc 两个节点,A 节点也是一个非压缩前缀节点。
将 A 节点挂在和 a 相同的父节点上。
同上,在 bcd 和 abc 这两个节点下挂空子节点来分别表示两个 key。
Rax Remove
删除
删除一个 key 的流程比较简单,找到 iskey 的节点后,向上遍历父节点删除非 iskey 的节点。如果是非压缩的父节点并且 size > 1,表示还有其他非相关的路径存在,则需要按删除子节点的模式去处理这个父节点,主要是做 memove 和 realloc。
合并
删除一个 key 之后需要尝试做一些合并,以收敛树的高度。
合并的条件是:
- iskey= 1 的节点不能合并
- 子节点只有一个字符
- 父节点只有一个子节点(如果父节点是压缩前缀的节点,那么只有一个子节点,满足条件。如果父节点是非压缩前缀的节点,那么只能有一个字符路径才能满足条件)
结束语
云数据库 Redis 版(ApsaraDB for Redis)是一种稳定可靠、性能卓越、可弹性伸缩的数据库服务。基于飞天分布式系统和全 SSD 盘高性能存储,支持主备版和集群版两套高可用架构。提供了全套的容灾切换、故障迁移、在线扩容、性能优化的数据库解决方案。欢迎各位购买使用: 云数据库 Redis 版
本文作者:羽洵
阅读原文
本文为云栖社区原创内容,未经允许不得转载。