Redis 五种数据结构

一、SDS 简单动态字符串

Redis 在存储 可能发生改变、非字面量 的字符串时，都会使用 SDS，比如：redis 的 key 和 value 等。

1. 结构体定义

struct sdshdr{
    // 字符串真是长度
    int len;
    // buf 中空闲的长度
    int free;
    // 存储字符串的 char 数组
    char buf[];
}

• len，字符串真实长度。
• free，buf 中空闲的长度（与 预分配 和 惰性释放 有关）
• buf，用于存储字符串的 char 数组。

2. SDS 和 C 字符串的区别

• SDS 获取字符串长度的时间复杂度是 O(1)，C 获取字符串长度的时间复杂度是 0(n)
• 通过 SDS 的 API 操作字符串（末尾追加、截取等）完全避免了 内存的溢出和泄露，而 C 字符串则需要手动维护内存，存在溢出和泄露风险。
• SDS 减少了 内存分配的次数
  • 内存预分配：SDS 通过 alloc = (len <= 1024) ? 2 * len : len + 1024 的方式，预留了一部分内存空间，相比 C 字符串，在 增加字符串长度 的场景上，有效的减少了内存分配的次数。
  • 惰性释放：SDS 在释放空间时，并不立即释放空间，而是 在 free 字段中记录了【空闲】空间的长度，等待未来使用。C 字符串则每次都需要手动释放。且 SDS 的 API 也支持像 C 字符串那样的 立即释放。
• 相比 C 字符串，SDS 是 二进制安全的（不会像 C 字符串一样，以为空格是结尾）

二、链表

redis 通过链表，实现了 队列 相关的操作。

1. 结构体

• 链表节点：listNode（双向）

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;

• 链表：list

typedef stuct list {
    // 头结点
    listNode *head;
    // 尾节点
    listNode *tail;
    // 链表长度
    unsigned long len;
    // 节点复制函数
    void *(*dup)(void *ptr);
    // 节点释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
} list;

2. 特点

• 双向：获取某个节点的前置、后置节点的时间负责度是 0(1)
• 无环：head.prev 和 tail.next 是 null
• 带头、尾指针：获取链表的 表头节点 和 表尾节点 的时间复杂度是 O(1)

3. 部分API

三、字典

详见：
redis 源码分析（一）HashTable 上篇
redis 源码分析（二）HashTable 下篇

四、跳跃表

redis 的有序结合，当有序集合的 元素数量比较多 或者 元素的值是比较长的字符串 时，redis 使用跳跃表来实现 有序集合。

1. 结构体

• 节点：zskiplistNode

typedef struct zskiplistNode {
    // 前一个节点的指针
    struct zskiplistNode *backword;
    // 当前节点的分值
    double score;
    // 当前节点的值对象
    robj *obj;
    struct zskiplistLevel {
        // 下一个节点的指针
        zskiplistNode *forword;
        // 到下一个节点的跨度
        unsigned int span;
    } level[];
    
} zskiplistNode;

• 跳跃表：zskiplist

typedef struct zskiplist {
    // 跳跃表头节点
    struct zskiplistNode *head;
    // 跳跃表尾节点
    struct zskiplistNode *tail;
    // 跳跃表的长度
    unsigned long length;
    // 跳跃表中层数最大的节点的层数
    int level;
} zskiplist;

2. 有序集合的 查找

• 普通的双向链表节点：DoubleLinkedListNode

typedef struct DoubleLinkedListNode {
    // 后一个节点的指针
    struct DoubleLinkedListNode *next;
    // 前一个节点的指针
    struct DoubleLinkedListNode *prev;
    // 当前节点的分值
    double score;
    // 当前节点的值对象
    robj *obj;
} DoubleLinkedListNode;

• 普通的双向链表节点，查找的逻辑就是遍历，时间复杂度是 O(n)
  
  10万元素跳跃表.png

如上图，假设一个跳跃表存储了 a1 到 a100001 这 10 万个元素，他们的分数分别是 1.0 到 100001.0

• 上述跳跃表有 五层：
  • 第一层跨度为1，即：1->2->3...
  • 第二层跨度为10，即：1->11->21...
  • 第三层跨度为100，即：1->101->201...
  • 第四层跨度为1000，即：1->1001->2001...
  • 第五层跨度为10000，即：1->10001->20001...
• 查找 65536 的过程：
  1. 第五层 查找 （8次） ：1->10001->20001->30001->40001->50001->60001，看到 70001 时发现：比 65536 大，去 第四层 继续查找。
  2. 第四层 查找 （6次）：61001->62001->63001->64001->65001，看到 66001 时发现：比 65536 大，去 第三层 继续查找。
  3. 第三层 查找 （6次）：65101->65201->65301->65401->65501，看到 65601 时发现：比 65536 大，去 第二层 继续查找。
  4. 第二层 查找 （4次）：65511->65521->65531，看到 65541 时发现：比 65536 大，去 第一层 继续查找。
  5. 第一层 查找 （4次）：65532->65533->65534，看到 65535 时发现目标，得到结果。
• 结论：
  • 跳跃表的节点，将普通双向链表的节点的 next 指针，从1个升级到了多个，以层的方式管理。
  • 不同层级的指针，跨度不一样：第一层就是普通双向链表节点的 next 指针。以后的各层，跨度不断增大，以达到 跳过一些节点，进行查找的目的。
  • 指针的层数越高，对查找的性能优化越明显，即：时间复杂度从 O(n) 减少到了 O(logN)

3. 其他有序集合操作

其他有序集合操作，像 范围查找（正向、逆向）、是否存在 等，其实都是基于 查找 的结果，利用 前置、后置指针 进行的遍历。

五、整数集合

当集合中的元素都是整数时，Redis 会使用 整数集合 作为集合的底层实现

1. 结构体

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合长度
    uint32_t length;
    // 集合元素
    int8_t contents[];
} intset;

其中，encoding 指明了 contents 中的数据类型：

• INTSET_ENC_INT16，范围：[-2^15=-32768, 2^15-1=32767]
• INTSET_ENC_INT32，范围：[-2^31=-2147483648, 2^31-1=2147483647]
• INTSET_ENC_INT64，范围：[-2^63, 2^63-1]

2. 编码升级

当一个编码为更小范围，如 INTSET_ENC_INT16 ，的整数集合，要添加一个更大范围，如 INTSET_ENC_INT32，的元素时，整体集合的编码方式需要升级。具体思路是：

• 根据新元素的类型和集合的元素数量，扩展集合空间。
• 将集合中的其他元素升级，并保证之前的有序顺序。
• 将新元素添加到集合中（因为范围更大，所以位置一定是：第一个或者最后一个）

3. 升级的好处

• 集合更加灵活。屏蔽了不同范围整数的存储实现。
• 更加节省空间。在有需要的时候再进行升级，避免了一开始就使用 INTSET_ENC_INT64 来存储集合元素。

4. 不存在降级

升级后的整数集合，并不会因为，唯一一个更大范围的元素被删除，就进行降级。