【后端那些事儿】Redis设计与实现(一) 数据结构，耐心看完你比Redis还懂Redis!

引言

本文章主要为了帮助读者认识Redis的数据结构，并深入了解Redis的数据结构，创作不易，希望得到大家的点赞、收藏、关注！谢谢！

1.简单动态字符串

1.1简单动态字符串(SDS)的定义

Redis的简单动态字符串（Simple Dynamic String，SDS）是Redis内部使用的字符串表示方式。SDS是一种可以自动扩展长度的字符串类型，它具有以下特点：

1. SDS的定义：SDS的定义如下。

struct sdshdr {
    int len;  
    int free; 
    char buf[];  
};

其中，len表示SDS中实际保存的字符串长度，free表示SDS中未被使用的字节长度，buf是实际保存字符串的数组。

2. SDS的优点：SDS相比C语言中的字符串，具有以下优点：

• 常数时间获取字符串长度：SDS的len字段记录了字符串的长度，可以在常数时间内获取。
• 避免缓冲区溢出：SDS会根据字符串的长度自动扩展或收缩，可以避免缓冲区溢出问题。
• 空间预分配：SDS会为字符串预先分配一定的空间，减少频繁改变字符串长度带来的内存重分配开销。
• 兼容部分C字符串函数：SDS的buf字段是以空字符结尾的C字符串，可以直接使用大部分C字符串函数操作SDS。

3. SDS的动态扩展：当字符串长度增加时，SDS会根据需要自动扩展空间。扩展的策略如下：

• 如果扩展后的空间大于1M，直接分配所需空间。
• 如果扩展后的空间小于1M，分配2倍于需要的空间。
• 如果扩展后的空间小于1M，且扩展后的空间小于1M，分配所需空间加上1M。

4. SDS的惰性缩减：当字符串长度减少时，SDS不会立即释放空间，而是将空余空间保留在free字段中，以备将来使用。只有当空余空间的长度大于SDS所保存的字符串长度的1/4时，SDS会释放空余空间。

总结来说，SDS提供了一种动态扩展和收缩的字符串表示方式，具有高效性、安全性和兼容性等优点，是Redis内部使用的字符串类型。

1.2SDS与C字符串的区别

Redis中的SDS（Simple Dynamic String）与C字符串在以下方面有所区别：

1. 存储结构：C字符串使用字符数组（char array）表示，以空字符(‘\0’)结尾。而SDS则是使用一种带有头部结构的动态数组来存储字符串内容。

2. 动态扩展：C字符串的长度固定，如果需要存储更长的字符串，需要手动重新分配更大的内存空间。而SDS可以自动扩展内存空间以适应字符串的增长，避免了频繁的内存重分配和拷贝操作。

3. 字符串长度获取：C字符串在获取其长度时需要遍历整个字符串，时间复杂度为O(n)，而SDS将字符串的长度保存在结构体中，可以在O(1)的时间复杂度内获取。

4. 安全性：C字符串没有边界检查，容易导致缓冲区溢出的问题。而SDS使用动态分配的方式避免了缓冲区溢出，保证了字符串的安全性。

5. 二进制安全性：C字符串以空字符作为字符串的终止符，不适合存储二进制数据。而SDS可以存储任意二进制数据，因为它使用了长度字段来记录字符串的长度。

6. 兼容性：虽然Redis内部使用SDS来表示字符串，但是Redis提供了一些兼容C字符串的API，使得可以方便地将C字符串与SDS进行转换和操作。

总的来说，SDS在功能、安全性和扩展性等方面相对于C字符串有更多的优势，是Redis中用于表示字符串的一种更高效和安全的数据结构。

1.3 SDS常用API

1. sdsnewlen(const void *init, size_t initlen)：创建一个新的SDS，并初始化为给定的字符串，长度为initlen。

2. sdsnew(const char *init)：创建一个新的SDS，并初始化为给定的C字符串。

3. sdsfree(sds s)：释放给定的SDS内存空间。

4. sdslen(const sds s)：返回给定SDS的长度。

5. sdscat(sds s, const char *t)：将C字符串t追加到SDS s的末尾，并返回拼接后的SDS。

6. sdscatsds(sds s, const sds t)：将SDS t追加到SDS s的末尾，并返回拼接后的SDS。

7. sdscpy(sds s, const char *t)：将C字符串t复制到SDS s中，并返回复制后的SDS。

8. sdscatlen(sds s, const void *t, size_t len)：将长度为len的二进制数据t追加到SDS s的末尾，并返回拼接后的SDS。

9. sdsdup(const sds s)：复制给定的SDS，并返回复制后的SDS。

10. sdstrim(sds s, const char *cset)：移除SDS s中给定的前导和尾部的字符集合cset包含的字符。

11. sdstolower(sds s)：将SDS s中的所有字符转换为小写。

12. sdsrange(sds s, int start, int end)：从给定的start位置到end位置截取SDS s中的字符，并返回截取后的SDS。

13. sdscmp(const sds s1, const sds s2)：比较两个SDS s1和s2的内容，返回一个整数表示两个SDS的大小关系。

14. sdsavail(const sds s)：返回SDS s中未使用的内存空间大小。

这些API可以方便地对SDS进行创建、释放、拼接、复制、截取等操作，提供了便捷的方式来处理字符串。

1.4重点回顾

• Redis 只会使用 C 字符串作为字面量， 在大多数情况下， Redis 使用 SDS （Simple Dynamic String，简单动态字符串）作为字符串表示。

• 比起 C 字符串， SDS 具有以下优点：

   		1. 常数复杂度获取字符串长度。
   		2. 杜绝缓冲区溢出。
   		3. 减少修改字符串长度时所需的内存重分配次数。
   		4. 二进制安全。
   		5. 兼容部分 C 字符串函数。
  

2.链表

2.1链表和链表节点的实现

Redis中的链表是一个双向链表，每个节点包含一个指向前一个节点的指针和一个指向后一个节点的指针。链表节点的结构如下：

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

每个节点的value指针指向存储在链表中的值。链表结构如下：

typedef struct list {
    listNode *head;
    listNode *tail;
    unsigned long len;
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);
    int (*match)(void *ptr, void *key);
} list;

链表结构中的head和tail分别指向链表的头节点和尾节点，len表示链表的长度。dup、free和match是用于处理节点值的函数指针，分别用于复制节点值、释放节点值和比较节点值。

Redis中链表的使用非常灵活，常用的链表操作包括：

1. listCreate()：创建一个新的空链表。

2. listAddNodeHead(list *list, void *value)：将一个新节点插入到链表的头部。

3. listAddNodeTail(list *list, void *value)：将一个新节点插入到链表的尾部。

4. listInsertNode(list *list, listNode *old_node, void *value, int after)：在链表中的某个节点之前或之后插入一个新节点。

5. listDelNode(list *list, listNode *node)：从链表中删除给定节点。

6. listGetIterator(list *list, int direction)：创建一个链表的迭代器。

7. listNext(listIter *iter)：取得迭代器指向节点的下一个节点。

8. listPrev(listIter *iter)：取得迭代器指向节点的前一个节点。

9. listReleaseIterator(listIter *iter)：释放迭代器。

10. listDup(list *orig)：复制一个链表。

11. listSearchKey(list *list, void *key)：根据节点值查找链表中对应的节点。

链表在Redis中用于实现列表、发布订阅模式中的订阅者列表以及慢查询日志等，具有灵活性和高效性的特点。

2.2链表和链表节点的常用API

1. 构造函数：LinkedListNode(data) - 创建一个新的链表节点，将数据存储在节点中。

2. 获取数据：getValue() - 返回节点中存储的数据。

3. 设置数据：setValue(data) - 将节点中存储的数据设置为指定的值。

4. 获取下一个节点：getNext() - 返回指向下一个节点的指针。

5. 设置下一个节点：setNext(next) - 将指向下一个节点的指针设置为指定的节点。

这些API可以用于创建和操作链表节点，例如：

# 创建链表节点
node1 = LinkedListNode(10)
node2 = LinkedListNode(20)
node3 = LinkedListNode(30)

# 打印节点的值
print(node1.getValue())  # 输出: 10

# 设置节点的值
node2.setValue(25)
print(node2.getValue())  # 输出: 25

# 设置节点的下一个节点
node1.setNext(node2)
node2.setNext(node3)

# 获取节点的下一个节点
next_node = node1.getNext()
print(next_node.getValue())  # 输出: 25

使用这些API，可以创建链表并操作节点之间的连接关系。这些API可以根据具体的编程语言和数据结构的实现略有不同，但是基本的原理和功能是相似的。

2.3重点回顾

• 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
• 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
• 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

3.字典

在Redis中，字典（Dict）是一种高效的数据结构，用于存储键值对。它类似于哈希表，通过使用哈希算法将键映射到对应的值，从而实现快速的查找和插入操作。

3.1字典的实现

3.1.1哈希表

在Redis中，哈希表的结构定义如下：

typedef struct dictEntry {
    void *key;          // 键
    union {
        void *val;      // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;  // 链表指针，指向下一个节点
} dictEntry;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);  // 哈希函数指针
    void *(*keyDup)(void *privdata, const void *key);  // 键复制函数指针
    void *(*valDup)(void *privdata, const void *obj);  // 值复制函数指针
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  // 键比较函数指针
    void (*keyDestructor)(void *privdata, void *key);  // 键释放函数指针
    void (*valDestructor)(void *privdata, void *obj);  // 值释放函数指针
} dictType;

typedef struct dict {
    dictType *type;      // 哈希表类型，定义了哈希函数等操作
    void *privdata;      // 私有数据，传递给哈希表操作函数
    dictht ht[2];        // 两个哈希表，用于渐进式rehash操作
    long rehashidx;      // 当前rehash进度，如果没有进行rehash则为-1
    int iterators;       // 当前迭代器数量
} dict;

• dictEntry：哈希表中的节点，用于存储键值对。其中，key指向键的内存地址，v是一个联合体，用于存储值的不同类型，next指向下一个节点的指针。
• dictType：哈希表类型，定义了哈希函数、键值复制函数、键值比较函数等操作。
• dict：哈希表的结构体。其中，type指向哈希表类型，privdata存储私有数据，用于传递给哈希表操作函数。ht[2]是两个哈希表，用于渐进式rehash操作。rehashidx记录了当前rehash的进度，如果没有进行rehash则为-1。iterators记录当前迭代器的数量。

通过这些定义，Redis的哈希表可以灵活存储不同类型的键值对，并支持动态扩容和收缩操作。

3.1.2哈希表节点

在Redis中，哈希表的节点使用结构体dictEntry来表示，其定义如下：

typedef struct dictEntry {
    void *key;                // 键
    union {
        void *val;            // 值
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;   // 链表指针，指向下一个节点
} dictEntry;

• key：指向键的内存地址。
• v：联合体，用于存储值的不同类型。可以通过val访问值的指针，也可以通过u64、s64、d来分别访问无符号整型、有符号整型和双精度浮点数值。
• next：链表指针，指向下一个节点。当发生哈希冲突时，多个节点会以链表的形式存储在同一个哈希槽中。

通过这个结构体，Redis的哈希表中的每个节点都存储了一个键值对，可以根据键快速查找对应的值，并支持解决哈希冲突的链表形式存储方式。

3.1.3 字典

在Redis中，字典使用结构体dict来表示，其定义如下：

typedef struct dict {
    dictType *type;             // 类型特定函数
    void *privdata;             // 私有数据
    dictht ht[2];               // 哈希表，0号用于读取，1号用于扩容和重新哈希
    long rehashidx;             // 重哈希索引
    unsigned long iterators;    // 当前正在运行的迭代器数量
} dict;

• type：指向dictType结构体的指针，用于保存字典的类型特定函数，包括哈希函数、键的比较函数和键的释放函数等。
• privdata：私有数据，用于传递给类型特定函数的额外参数。
• ht[2]：数组，其中0号哈希表用于读取操作，1号哈希表用于扩容和重新哈希操作。一个哈希表包含多个哈希槽，每个哈希槽对应一个哈希表节点。
• rehashidx：重哈希索引，表示当前字典正在进行扩容和重新哈希操作时，已经完成的索引位置。
• iterators：表示当前正在运行的迭代器数量。在字典进行重新哈希时，为了保证安全，不允许进行迭代操作，所以需要记录当前正在运行的迭代器数量。

通过这个结构体，Redis的字典实现了一个高效的键值对存储结构，支持常数级别的读写操作，并且在需要时可以进行扩容和重新哈希操作，来保证字典的性能和空间利用率。

3.2哈希算法

当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

Redis 计算哈希值和索引值的方法如下：

#使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
#使用哈希表的 sizemask 属性和哈希值，计算出索引值
#根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

举个例子， 对于图 4-4 所示的字典来说， 如果我们要将一个键值对 k0 和 v0 添加到字典里面， 那么程序会先使用语句：

hash = dict->type->hashFunction(k0);

计算键 k0 的哈希值。

假设计算得出的哈希值为 8 ， 那么程序会继续使用语句：

index = hash & dict->ht[0].sizemask = 8 & 3 = 0;
计算出键 k0 的索引值 0 ， 这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上， 如图 4-5 所示。

当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。

3.3解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时， 我们称这些键发生了冲突（collision）。

Redis 的哈希表使用链地址法（separate chaining）来解决键冲突： 每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

举个例子， 假设程序要将键值对 k2 和 v2 添加到图 4-6 所示的哈希表里面， 并且计算得出 k2 的索引值为 2 ， 那么键 k1 和 k2 将产生冲突， 而解决冲突的办法就是使用 next 指针将键 k2 和 k1 所在的节点连接起来， 如图 4-7 所示。

3.4rehash

rehash是指动态扩展或收缩哈希表的过程。这个过程会在哈希表的负载因子超过设定阈值时自动触发。

在Redis中，哈希表被用来实现字典类型。在初始状态下，哈希表会根据初始大小进行分配。然而，随着操作的进行，哈希表可能会变得过于拥挤或稀疏，从而导致性能下降。

当哈希表的负载因子超过设定阈值时，Redis会自动触发rehash过程。rehash过程会创建一个新的更大的哈希表，并将旧表中的所有键值对重新映射到新表中。这个过程是逐步进行的，每次只迁移一个键值对，直到所有的键值对都被迁移完成。在这个过程中，旧表仍然可以接收读取请求，但写入请求会同时被发送到旧表和新表。当所有键值对都成功迁移后，新表会被用作主表，而旧表会被释放。

3.5渐进式rehash

Redis的渐进式rehash是一种在哈希表进行扩展或收缩时逐步迁移键值对的算法。通过渐进式rehash，Redis可以在rehash过程中保持对哈希表的读取和写入操作，同时减少对系统性能的影响。

具体的渐进式rehash算法如下：

1. Redis会创建一个新的更大或更小的哈希表，用于替换当前的哈希表。
2. Redis将新哈希表的大小设置为当前哈希表的两倍大小。
3. 将哈希表的rehash索引值设置为0，表示迁移操作从头开始。
4. 在进行每次迁移操作时，Redis会从当前哈希表中选取一个非空的哈希槽(slot)。
5. Redis会一次迁移选中哈希槽中的一个键值对到新哈希表中。
6. 在迁移过程中，Redis可以同时处理对旧哈希表和新哈希表的读取和写入操作。对于写入操作，会将键值对同时写入两个表中，并在读取操作时从两个表中读取对应的值。
7. 每次迁移完成后，Redis会将rehash索引值递增，选择下一个非空的哈希槽进行迁移，直到所有的键值对都迁移到新哈希表中。

通过这种渐进式rehash算法，Redis可以平滑地迁移大量的键值对，而不会对系统的读写性能产生明显的影响。在rehash过程中，Redis会根据当前的负载情况和系统资源的可用性，动态调整迁移的速度，以保证系统的稳定性和性能。

3.6字典常用API

1. HSET：在哈希表中设置一个字段的值。如果字段不存在，则创建新字段并设置值；如果字段已存在，则更新其值。
   示例：HSET key field value

2. HGET：获取哈希表中指定字段的值。
   示例：HGET key field

3. HGETALL：获取哈希表中所有字段和值的列表。
   示例：HGETALL key

4. HDEL：删除哈希表中一个或多个字段。
   示例：HDEL key field1 field2 …

5. HEXISTS：检查哈希表中是否存在指定字段。
   示例：HEXISTS key field

6. HKEYS：获取哈希表中所有字段的列表。
   示例：HKEYS key

7. HVALS：获取哈希表中所有值的列表。
   示例：HVALS key

8. HLEN：获取哈希表中字段的数量。
   示例：HLEN key

9. HMSET：同时设置哈希表中多个字段的值。
   示例：HMSET key field1 value1 field2 value2 …

10. HMGET：获取哈希表中多个字段的值。
    示例：HMGET key field1 field2 …

11. HINCRBY：将哈希表中指定字段的值增加指定增量。
    示例：HINCRBY key field increment

3.7重点回顾

• 字典被广泛用于实现 Redis 的各种功能， 其中包括数据库和哈希键。
• Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
• 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
• 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。

4.跳跃表

4.1跳跃表的实现

在Redis中，跳跃表（Skip List）的结构定义如下：

typedef struct zskiplistNode {
    // 节点的成员对象
    robj *obj;
    // 分值，用于有序集合中的排序
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层级
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度，表示当前层级到下一个节点的距离
        unsigned int span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    // 头节点和尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量
    unsigned long length;
    // 层数
    int level;
} zskiplist;

其中，zskiplistNode表示跳跃表中的节点，包含了成员对象 obj，用于存储实际的键值对数据；score 表示节点的分值，用于有序集合中的排序；backward 是一个指向前一个节点的指针；level 是一个柔性数组，用于存储层级信息，表示当前节点在每个层级上的指针和跨度。

zskiplist 表示整个跳跃表，包含了头节点和尾节点，以及节点数量 length 和层数 level。

跳跃表的结构定义允许节点在不同的层级上具有不同的前进指针和跨度，这样可以快速导航到目标节点，进而提高了对节点的查找和操作效率。

4.1.1跳跃表节点

Redis跳跃表节点的结构定义如下：

typedef struct zskiplistNode {
    sds ele;  // 节点元素的值
    double score;  // 节点元素的分值
    struct zskiplistNode *backward;  // 指向前一个节点的指针
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 指向下一个节点的指针
        unsigned int span;  // 跨越的节点数量
    } level[];
} zskiplistNode;

上述定义中，ele字段保存节点元素的值，score字段保存节点元素的分值。backward字段指向前一个节点，用于快速反向遍历。level字段是一个柔性数组，每个元素代表一个层级，保存指向下一个节点以及跨越的节点数量。

跳跃表是由多个跳跃表节点组成的，每个节点包含了多个层级。每个层级都是一个链表，节点之间通过forward指针连接起来。

跳跃表节点的层级数量是动态的，可以根据需要进行调整，这就是所谓的柔性数组。对于新插入的节点，可以通过随机算法确定它具有的层级数量，从而在整个跳跃表中能够快速地进行查找和插入操作。

1. 层

跳跃表节点的 level 数组可以包含多个元素， 每个元素都包含一个指向其他节点的指针， 程序可以通过这些层来加快访问其他节点的速度， 一般来说， 层的数量越多， 访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候， 程序都根据幂次定律 （power law，越大的数出现的概率越小） 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。

图 5-2 分别展示了三个高度为 1 层、 3 层和 5 层的节点， 因为 C 语言的数组索引总是从 0 开始的， 所以节点的第一层是 level[0] ， 而第二层是 level[1] ， 以此类推。

2. 前进指针

每个层都有一个指向表尾方向的前进指针（level[i].forward 属性）， 用于从表头向表尾方向访问节点。

图 5-3 用虚线表示出了程序从表头向表尾方向， 遍历跳跃表中所有节点的路径：

	(1)  迭代程序首先访问跳跃表的第一个节点（表头）， 然后从第四层的前进指针移动到表中的第二个节点。
	(2) 在第二个节点时， 程序沿着第二层的前进指针移动到表中的第三个节点。
	(3) 在第三个节点时， 程序同样沿着第二层的前进指针移动到表中的第四个节点。
	(4) 当程序再次沿着第四个节点的前进指针移动时， 它碰到一个 NULL ， 程序知道这时已经到达了跳跃表的表尾， 于是结束这次遍历。

3. 跨度

层的跨度（level[i].span 属性）用于记录两个节点之间的距离：

• 两个节点之间的跨度越大， 它们相距得就越远。
• 指向 NULL 的所有前进指针的跨度都为 0 ， 因为它们没有连向任何节点。
  初看上去， 很容易以为跨度和遍历操作有关， 但实际上并不是这样 —— 遍历操作只使用前进指针就可以完成了， 跨度实际上是用来计算排位（rank）的： 在查找某个节点的过程中， 将沿途访问过的所有层的跨度累计起来， 得到的结果就是目标节点在跳跃表中的排位。

举个例子， 图 5-4 用虚线标记了在跳跃表中查找分值为 3.0 、 成员对象为 o3 的节点时， 沿途经历的层： 查找的过程只经过了一个层， 并且层的跨度为 3 ， 所以目标节点在跳跃表中的排位为 3 。

再举个例子， 图 5-5 用虚线标记了在跳跃表中查找分值为 2.0 、 成员对象为 o2 的节点时， 沿途经历的层： 在查找节点的过程中， 程序经过了两个跨度为 1 的节点， 因此可以计算出， 目标节点在跳跃表中的排位为 2 。

4. 后退指针

节点的后退指针（backward 属性）用于从表尾向表头方向访问节点： 跟可以一次跳过多个节点的前进指针不同， 因为每个节点只有一个后退指针， 所以每次只能后退至前一个节点。

图 5-6 用虚线展示了如果从表尾向表头遍历跳跃表中的所有节点： 程序首先通过跳跃表的 tail 指针访问表尾节点， 然后通过后退指针访问倒数第二个节点， 之后再沿着后退指针访问倒数第三个节点， 再之后遇到指向 NULL 的后退指针， 于是访问结束。

5. 分值和成员

节点的分值（score 属性）是一个 double 类型的浮点数， 跳跃表中的所有节点都按分值从小到大来排序。

节点的成员对象（obj 属性）是一个指针， 它指向一个字符串对象， 而字符串对象则保存着一个 SDS 值。

在同一个跳跃表中， 各个节点保存的成员对象必须是唯一的， 但是多个节点保存的分值却可以是相同的： 分值相同的节点将按照成员对象在字典序中的大小来进行排序， 成员对象较小的节点会排在前面（靠近表头的方向）， 而成员对象较大的节点则会排在后面（靠近表尾的方向）。

举个例子， 在图 5-7 所示的跳跃表中， 三个跳跃表节点都保存了相同的分值 10086.0 ， 但保存成员对象 o1 的节点却排在保存成员对象 o2 和 o3 的节点之前， 而保存成员对象 o2 的节点又排在保存成员对象 o3 的节点之前， 由此可见， o1 、 o2 、 o3 三个成员对象在字典中的排序为 o1 <= o2 <= o3 。

4.2跳跃表API

Redis跳跃表的API包括以下几个主要操作：

1. 创建跳跃表：

zskiplist *zslCreate(void);

2. 释放跳跃表：

void zslFree(zskiplist *zsl);

3. 插入节点：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele);

4. 删除节点：

int zslDelete(zskiplist *zsl, double score, sds ele);

5. 查找节点：

zskiplistNode *zslGetElementByScore(zskiplist *zsl, double score, sds ele);

6. 获取跳跃表的长度：

unsigned long zslLength(zskiplist *zsl);

7. 获取跳跃表中指定范围内的节点：

unsigned long zslGetRangeByScore(zskiplist *zsl, double min, double max, int *count);

以上是一些常见的跳跃表操作API，可以根据需要使用这些API对跳跃表进行插入、删除、查找等操作。在Redis中，跳跃表被广泛应用于有序集合（sorted set）的实现中，用于快速查询、排序和范围查找等操作。

4.3重点回顾

• 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
• Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点。
• 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
• 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。
• 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。

5.整数集合

5.1整数集合的实现

Redis整数集合是一种特殊的集合结构，用于存储整数值的集合。它的结构定义如下：

typedef struct intset {
    uint32_t encoding;         // 编码方式
    uint32_t length;           // 长度
    int8_t contents[];         // 内容
} intset;

其中，encoding字段表示整数集合的编码方式，用于标识整数集合中元素的数据类型和所占空间大小。Redis整数集合支持三种编码方式：

1. INTSET_ENC_INT16：使用int16_t类型存储元素，占用2个字节。
2. INTSET_ENC_INT32：使用int32_t类型存储元素，占用4个字节。
3. INTSET_ENC_INT64：使用int64_t类型存储元素，占用8个字节。

length字段表示整数集合的长度，即集合中元素的个数。

contents字段是一个柔性数组（Flexible Array），用于存储整数集合的元素。根据不同的编码方式，元素将以相应的数据类型存储在这个数组中。

通过这种结构定义，Redis整数集合实现了紧凑的存储方式，能够高效地存储整数值集合，同时提供了常数时间复杂度的增删查操作。

5.2升级

Redis整数集合在插入新元素时可能需要进行升级操作，以保证集合的编码方式足够存储新元素。升级操作的过程如下：

1. 当插入的新元素超出当前整数集合的编码范围时，需要将整数集合升级为更高编码方式。

2. 首先，根据新元素的值确定应该升级到的编码方式。如果新元素的值可以被当前编码方式所容纳，则无需升级。否则，需要将整数集合升级为能够容纳新元素值的更高编码方式。

3. 创建一个新的整数集合，使用新的编码方式，并将原整数集合中的所有元素转移至新集合。转移过程会根据元素值的类型和编码范围，进行类型转换和空间调整。

4. 最后，将新元素插入到升级后的整数集合中。

在升级过程中，Redis采用了惰性升级的策略，即只有在插入新元素时才会进行升级操作。这种策略能够保证在大部分情况下，整数集合的编码方式不会频繁地变化，从而提高了性能和空间效率。

整数集合的升级操作是一种优化机制，它能够根据插入元素的情况动态调整集合的编码方式，使得整数集合在不同情况下都能够以最优的方式存储和操作整数值。

5.3升级的好处

5.3.1提升灵活性

因为 C 语言是静态类型语言， 为了避免类型错误， 我们通常不会将两种不同类型的值放在同一个数据结构里面。

比如说， 我们一般只使用 int16_t 类型的数组来保存 int16_t 类型的值， 只使用 int32_t 类型的数组来保存 int32_t 类型的值， 诸如此类。

但是， 因为整数集合可以通过自动升级底层数组来适应新元素， 所以我们可以随意地将 int16_t 、 int32_t 或者 int64_t 类型的整数添加到集合中， 而不必担心出现类型错误， 这种做法非常灵活。

5.3.2节约内存

当然， 要让一个数组可以同时保存 int16_t 、 int32_t 、 int64_t 三种类型的值， 最简单的做法就是直接使用 int64_t 类型的数组作为整数集合的底层实现。 不过这样一来， 即使添加到整数集合里面的都是 int16_t 类型或者 int32_t 类型的值， 数组都需要使用 int64_t 类型的空间去保存它们， 从而出现浪费内存的情况。

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值， 又可以确保升级操作只会在有需要的时候进行， 这可以尽量节省内存。

比如说， 如果我们一直只向整数集合添加 int16_t 类型的值， 那么整数集合的底层实现就会一直是 int16_t 类型的数组， 只有在我们要将 int32_t 类型或者 int64_t 类型的值添加到集合时， 程序才会对数组进行升级。

5.4降级

整数集合不支持降级操作， 一旦对数组进行了升级， 编码就会一直保持升级后的状态。

举个例子， 对于图 6-11 所示的整数集合来说， 即使我们将集合里唯一一个真正需要使用 int64_t 类型来保存的元素 4294967295 删除了， 整数集合的编码仍然会维持 INTSET_ENC_INT64 ， 底层数组也仍然会是 int64_t 类型的， 如图 6-12 所示。

5.5整数集合API

Redis中提供了一些API来操作整数集合：

1. SADD key member [member ...] - 将一个或多个整数添加到集合中
2. SREM key member [member ...] - 从集合中移除一个或多个整数
3. SISMEMBER key member - 检查一个整数是否存在于集合中
4. SCARD key - 获取集合中整数的数量
5. SMEMBERS key - 返回集合中的所有整数
6. SUNION key [key ...] - 返回给定集合的并集
7. SDIFF key [key ...] - 返回给定集合的差集
8. SINTER key [key ...] - 返回给定集合的交集
9. SRANDMEMBER key [count] - 从集合中随机返回一个或多个整数
10. SPOP key [count] - 从集合中随机弹出一个或多个整数
11. SMOVE source destination member - 将一个整数从一个集合移动到另一个集合
12. SSCAN key cursor [MATCH pattern] [COUNT count] - 迭代集合中的整数

5.6重点回顾

• 整数集合是集合键的底层实现之一。
• 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型。
• 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
• 整数集合只支持升级操作， 不支持降级操作。

6.压缩列表

6.1压缩列表的构成

Redis的压缩列表（ziplist）是一种紧凑的、存储有序元素的数据结构。它主要用于保存列表和哈希的底层实现。

压缩列表的结构定义如下：

|<------------------------ ziplist ------------------------>|
|-<zlbytes(4 bytes)>-|-<zltail(4 bytes)>-|-<zllen(2 bytes)>-|
|<--------------------------- entry ----------------------->|

entry: |<prevlen(1 or 5 bytes)>-|-<encoding(1 or 5 bytes)>-|-<content>|

• zlbytes：压缩列表的总字节数（不包括头部的10字节）。
• zltail：尾节点到压缩列表起始位置的偏移量的字节数。
• zllen：压缩列表包含的节点数量（元素数量）。
• entry：压缩列表的节点，保存了元素的前一个节点长度、编码方式和实际内容。

压缩列表的每个节点（entry）由以下组成：

• prevlen：表示前一个节点的长度，1个字节或5个字节，根据前一个节点的长度而定。
• encoding：表示当前节点内容的编码方式，1个字节或5个字节，根据内容的长度和类型而定。
• content：实际的节点内容，可以是整数、字符串或者字节数组。

压缩列表通过紧凑的存储方式来节省内存空间，并提供快速的随机访问和插入操作。

6.2压缩列表节点的构成

Redis压缩列表（ziplist）是一种特殊的数据结构，用于存储小型列表。每个压缩列表节点的结构定义如下：

|<---- prevEntryLength ---->|<--- encoding --->|<----- entryValue ----->|
|<----------------------------- zlentry ------------------------------>|

• prevEntryLength：前一个节点的长度，用于快速定位到前一个节点。如果当前节点是第一个节点，该字段的值为 0。
• encoding：表示 entryValue 的编码方式，可以有以下几种取值：
  • 00xxxxxx：7 位整数，entryValue 占用 1 个字节。
  • 01xxxxxx xxxxxxxx：14 位整数，entryValue 占用 2 个字节。
  • 10xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx：29 位整数，entryValue 占用 4 个字节。
  • 11000000：从下一个字节开始，后续的字节是一个长度不定的字符串，entryValue 的长度通过下一个字节表示。
  • 1101xxxx：固定长度的数字字符串，entryValue 的长度为 xxxx。
  • 1110xxxx：从下一个字节开始，后续的字节是一个长度不定的字节数组，entryValue 的长度通过下一个字节表示。
• entryValue：实际存储的数据。根据 encoding 的不同，其类型也可能不同。

这种结构定义使得压缩列表可以灵活地存储各种类型的数据，同时又能够节约内存空间。

6.3连锁更新

前面说过， 每个节点的 previous_entry_length 属性都记录了前一个节点的长度：

• 如果前一节点的长度小于 254 字节， 那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
• 如果前一节点的长度大于等于 254 字节， 那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

现在， 考虑这样一种情况： 在一个压缩列表中， 有多个连续的、长度介于 250 字节到 253 字节之间的节点 e1 至 eN ， 如图 7-11 所示。

因为 e1 至 eN 的所有节点的长度都小于 254 字节， 所以记录这些节点的长度只需要 1 字节长的 previous_entry_length 属性， 换句话说， e1 至 eN 的所有节点的 previous_entry_length 属性都是 1 字节长的。

这时， 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点， 那么 new 将成为 e1 的前置节点， 如图 7-12 所示。

因为 e1 的 previous_entry_length 属性仅长 1 字节， 它没办法保存新节点 new 的长度， 所以程序将对压缩列表执行空间重分配操作， 并将 e1 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

现在， 麻烦的事情来了 —— e1 原本的长度介于 250 字节至 253 字节之间， 在为 previous_entry_length 属性新增四个字节的空间之后， e1 的长度就变成了介于 254 字节至 257 字节之间， 而这种长度使用 1 字节长的 previous_entry_length 属性是没办法保存的。

因此， 为了让 e2 的 previous_entry_length 属性可以记录下 e1 的长度， 程序需要再次对压缩列表执行空间重分配操作， 并将 e2 节点的 previous_entry_length 属性从原来的 1 字节长扩展为 5 字节长。

正如扩展 e1 引发了对 e2 的扩展一样， 扩展 e2 也会引发对 e3 的扩展， 而扩展 e3 又会引发对 e4 的扩展……为了让每个节点的 previous_entry_length 属性都符合压缩列表对节点的要求， 程序需要不断地对压缩列表执行空间重分配操作， 直到 eN 为止。

Redis 将这种在特殊情况下产生的连续多次空间扩展操作称之为“连锁更新”（cascade update）， 图 7-13 展示了这一过程。

除了添加新节点可能会引发连锁更新之外， 删除节点也可能会引发连锁更新。

考虑图 7-14 所示的压缩列表， 如果 e1 至 eN 都是大小介于 250 字节至 253 字节的节点， big 节点的长度大于等于 254 字节（需要 5 字节的 previous_entry_length 来保存）， 而 small 节点的长度小于 254 字节（只需要 1 字节的 previous_entry_length 来保存）， 那么当我们将 small 节点从压缩列表中删除之后， 为了让 e1 的 previous_entry_length 属性可以记录 big 节点的长度， 程序将扩展 e1 的空间， 并由此引发之后的连锁更新。

因为连锁更新在最坏情况下需要对压缩列表执行 N 次空间重分配操作， 而每次空间重分配的最坏复杂度为 O(N) ， 所以连锁更新的最坏复杂度为 O(N^2) 。

要注意的是， 尽管连锁更新的复杂度较高， 但它真正造成性能问题的几率是很低的：

首先， 压缩列表里要恰好有多个连续的、长度介于 250 字节至 253 字节之间的节点， 连锁更新才有可能被引发， 在实际中， 这种情况并不多见；
其次， 即使出现连锁更新， 但只要被更新的节点数量不多， 就不会对性能造成任何影响： 比如说， 对三五个节点进行连锁更新是绝对不会影响性能的；
因为以上原因， ziplistPush 等命令的平均复杂度仅为 O(N) ， 在实际中， 我们可以放心地使用这些函数， 而不必担心连锁更新会影响压缩列表的性能。

6.4压缩列表API

Redis提供了一些常用的API用于操作压缩列表：

1. ZLLEN key：返回压缩列表键的长度，即压缩列表中节点的数量。
2. ZLINSERT key SP where pivot value：在压缩列表的指定位置插入一个新节点，其中：
   • SP：表示插入方式，可以是 BEFORE 或 AFTER。
   • where：表示插入位置，可以是 FIRST、LAST 或者一个整数索引。
   • pivot：表示插入位置的依据节点，可以是一个整数或字节数组。
   • value：要插入的新节点的值，可以是整数或字节数组。
3. ZLDELETE key pivot：删除压缩列表中的一个节点，其中 pivot 是要删除节点的值。
4. ZLGET key index：获取压缩列表中指定索引位置的节点的值。
5. ZLSET key index value：设置压缩列表中指定索引位置的节点的值。
6. ZLINDEX key index：获取压缩列表中指定索引位置的节点的值的指针地址。

这些API提供了对压缩列表的基本操作，可以用于插入、删除、获取和修改压缩列表中的节点，以及获取压缩列表的长度等操作。

6.5重点回顾

• 压缩列表是一种为节约内存而开发的顺序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
• 添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高。

到这里我们关于Redis数据结构的分享就结束了，关于Redis的数据结构你还有哪些知识点不清楚，在评论区或私信告诉我吧，下一章节我们将讲述Redis的对象，如果你觉得本文章对你有帮助，跪求三连！文章来源地址https://www.toymoban.com/news/detail-815509.html

到了这里，关于【后端那些事儿】Redis设计与实现(一) 数据结构，耐心看完你比Redis还懂Redis!的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！