Redis之Rax

2021-11-21 04:43:38

Rax全称redis tree，是一个有序字典树，可以根据key进行排序，支持快速定位、插入与删除，与hash/zset不同在于hash不具备排序功能，zset则根据score进行排序。
【trie简介】
在计算机科学中，trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
Trie这个术语来自于retrieval。根据词源学，trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是，其他作者把它读作/ˈtraɪ/ "try"。
与二叉查找树不同，Trie树的键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie树优点是最大限度地减少无谓的字符串比较，查询效率比较高。核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
（1）插入、查找的时间复杂度均为O(N)，其中N为字符串长度。
（2）空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）。
它有3个基本性质：
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同。
【rax与压缩trie】
Trie树其实依然比较浪费空间，有人曾经反馈他们在实际的项目发现，随着key的数量的增加，发现Trie树会占用大量的内存和空间。
看标准的trie树存储的结构如图：

其实可以将没有分支的链路节点合并，如图：

Redis中存储的trie树就是这种压缩过的结构，也就是Rax树。
【结构】
计算机对于Radix树的处理是以bit（或二进制数字）来读取的。一次被对比r个bit，2的r次方是radix树的基数。这也是基数树的这个名字的由来。
现在把上面的三个单词变成二进制的样子，然后一位一位的看：
dog: 01100100 01101111 01100111
doge: 01100100 01101111 01100111 01100101
dogs: 01100100 01101111 01100111 01110011
按照字符串的比对，会发现dog是dogs和doge的子串。但我们现在比对二进制，一位一位的比对，会发现dog和doge是在第二十五位的时候不一样的。dogs和doge是在第二十八位不一样的。这就是计算机的方式。

此时来看看Rax中的几种结构，之前说过Rax是压缩过的trie，它的结构有三种类型，根节点、叶子结点、中间节点。有些中间节点带value，有些是结构性需要，没有value。

struct raxNode {
    int<1> isKey;         // 是否有key，没key是根节点
    int<1> isNull;        // 没有对应的value，中间节点
    int<1> isCompressed;  // 是否存储压缩
    int<29> size;           // 叶子节点数量或者是压缩字符串长度
    byte[] data;              // 用于存储路由键、叶子节点指针、value
}

redis中的rax在结构上不是标准的Radix Tree，如果一个中间节点有多个叶子节点，路由键就是一个字符；如果只有一个叶子节点，路由键就是一个字符串。
只有一个叶子节点的时候，就是压缩节点(多个字符压在一起的字符串)，下图中的深蓝色节点就是压缩节点：

isCompressed记录了这个节点是不是压缩结构，压缩或者不压缩会直接反映在data的结构里。
--对于压缩的节点：

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

如果压缩节点后面没有节点了，childNode就不存在，如果是中间节点，那么value字段也不存在。这里要注意的是，中间节点其实可以是压缩节点的，但是不能有多个叶子节点，如果是多个叶子节点，那就不能是压缩节点，而必须用单个字符作为路由键。
--对于非压缩的节点：
叶子节点有多个，就不是压缩节点，存在多个路由键，一个键就是一个字符。

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

结构如图所示：

【参考】
《Redis深度历险核心原理与应用实践》
https://developer.aliyun.com/article/38231
https://cloud.tencent.com/developer/article/1597128

码农公寓

相关文章