Redis深度历险-基数树

Redis中的基数树是一种有序字典树，zset也是一种有序字典但是是按照score进行排序的，rax是按照key进行排序的；平衡二叉树、跳表都可以用来实现这种有序集合，不过要考虑复杂度

数据结构

数据结构

基数树简图.png

基数树有点类似与前缀树trie树，主要用于Redis Stream中存储消息队列，因为消息的key是时间戳+序号，而时间戳的编码也是按照年月日时分秒毫秒微秒纳秒一级一级划分
有以下特点：

• 从根节点到叶子结点上的所有字符组合起来就是该叶子结点对应的字符串，即key
• 如果节点只有一个字节点，允许跳多个字符，如图中的朋友越过了end
• 如果节点有多个子节点，只允许跳一个字符到子节点，如图中的灾难节点必须先经过s

节点

typedef struct raxNode {
    uint32_t iskey:1;     //用来标识根节点，没有key的是根节点
    uint32_t isnull:1;    //标志数据结构所需的中间节点，没有存储value
    uint32_t iscompr:1;   //是否压缩存储
    uint32_t size:29;     //子节点数量或压缩字符串的长度
    unsigned char data[];   //数据
} raxNode;

raxNode有多种情况

• 根节点
• 中间节点
• 压缩节点：有多个字节点
• 非压缩节点：只有一个字节点

压缩节点

在代码中并没有通过结构体表述出来，而是通过内存排布来决定的

[header iscompr=1][xyz][z-ptr](value-ptr?)

压缩结构.png

一个压缩节点的data包含三部分

• 路由键：最多一个，如果是叶子结点就没有路由键了
• 子节点指针：如果是叶子结点也没有子节点了
• value：如果是中间节点（isnull标识），就没有value部分了

非压缩节点

非压缩结构.png

主要有两部分：

• 路由键：也是一个字符串，但是每一个字符标识一个子节点
• 子节点指针：和路由键的字符一一对应

总结

  涉及到这种内存操作的逻辑会非常复杂，很容易陷入细节逻辑中，有时间再补充细节吧