《进击的巨人》 -- 三笠 vs 铠之巨人

Redis 数据结构与对象

下文介绍了 6 种数据结构 🐱

简单动态字符串
链表
字典
跳跃表
整数集合
压缩列表

5 种对象类型 🐶

字符串对象
列表对象
哈希对象
集合对象
有序集合对象

¶1 数据结构

¶1.1 简单动态字符串

¶1.1.1 结构

Redis 没有直接使用 C 语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并且 SDS 作为 Redis 的默认字符串表示。

其结构定义如下：

注意：🙋

🔹 buf 属性是一个 char 类型的数组，数组最后一个字节保存了空字符 \0；

🔸 len 属性长度并不包括 buf 最后一个空字符；

🔹 free 表示该 SDS 中 buf 剩余的字节数；

🔸 buf 的真实长度为 len + free + 1。

¶1.1.2 C 字符串和 SDS 之间的区别

1️⃣ SDS 可以直接通过 len 字段来获取长度

2️⃣ SDS 在进行操作之前会判断缓冲区大小

3️⃣ SDS 使用 空间预分配 和 惰性空间释放 来减少修改字符串时带来的内存重分配次数

4️⃣ SDS 的 buf 并不是用来保存字符，而是用来保存一系列二进制数据

5️⃣ SDS 的 API 总会将 SDS 保存的数据的末尾设置为空字符，并且总会在 buf 数组分配空间多分配一个字节来容纳这个字符，所以可以让保存文本数据的 SDS 重用一部分 <string.h> 库定义的函数。

注意：🙋‍♂

空间预分配 用于优化 SDS 的字符串增长操作：当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间。

根据 SDS 的长度分为如下两种策略：

🔹 len < 1 MB，共分配 2 * len + 1 给 buf，此时字段 len = len， free = len

🔸 len $\geq$ 1 MB，共分配 len + 1 MB + 1 给 buf，此时字段 len = len，free = 1 MB

惰性空间释放 用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

于此同时，SDS 也提供了相应的 API，让我们可以在有需要时候，真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

¶1.1.3 SDS API

《Redis 设计与实现》第二章

¶1.2 链表

¶1.2.1 链表和链表节点的结构与实现

链表节点结构定义如下：

多个 listNode 可以通过 prev 和 next 指针组成双端链表，如下所示：

虽然仅仅使用多个 listNode 结构就可以组成链表，但是 adlist.h/list 来持有链表，操作起来会更方便：

list 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match成员则是用于实现多态链表所需的类型特定函数：

◻️ dup 函数用于复制链表节点所保存的值；

◻️ free 函数用于释放链表节点所保存的值；

◻️ match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

list 结构和 listNode 结构组成的链表如下：

总结：⭐️

🔹 双端链表，无环，首位指向 NULL；

🔸 字段：head，tail 让程序获取表头或者表尾节点时间复杂度为 $O(1)$；

🔹 字段：len 让程序获取链表中节点数量的时间复杂度为 $O(1)$；

🔸 多态：链表节点使用 void* 指针来保存节点值，并且可以通过 list 结构的 dup、free 和 match 为节点值设置类型特定函数，所以链表可以用于保存不同类型的值。

¶1.2.2 链表和链表节点的 API

《Redis 设计与实现》第三章

¶1.3 字典

¶1.3.1 哈希表

Redis 字典需要使用哈希表，它由 dict.h/dictht 结构定义：

注意：🙋

🔹 table 属性是一个数组，数组中的每一个元素指向 dict.h/dictEntry 结构的指针，dictEntry 结构保存着一个键值对；

🔸 size 属性记录了哈希表大小，也即 table 数组的大小；

🔹 used 属性记录了哈希表目前已有节点的数量；

🔸 sizemask 属性的值总是等于 size - 1。

下图展示一个空的哈希表：

¶1.3.2 哈希表节点

哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对，其定义如下所示：

注意：🙋‍♂

🔹 key 属性保存着键值对中的键；

🔸 v 属性则保存着键值对中的值，是一个联合体，可以是 void*，也可以是 uint64_t，或者 int64_t 的整数；

🔹 next 属性是一个指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接，解决键冲突问题。

下图展示一个简单例子：

¶1.3.3 字典

Redis 中的字典由 dict.h/dict 结构表示：

注意：🙋

🔹 type 属性是指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同字典设置不同的类型特定函数；

🔸 private 属性则保存了需要传给那些特定函数的可选参数；

上面这两个属性是针对不同类型的键值对，为创建多态字典而设置的；

🔹 ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用；

🔸 rehashidx 属性记录rehash目前的进度，其值对应 dictEntry 数组索引，没有进行rehash 时为 -1。

普通状态下的字典如下图所示：

¶1.3.4 哈希算法

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

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

// 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

// 使用哈希表的 sizemask 属性和哈希值，计算出索引值
// 根据情况不同，ht[x] 可以是 ht[0] 或者 ht[1](在rehash过程中)
index = hash & dict->ht[x].sizemask;

假设第一步计算出了 k0 的哈希值为 8，针对 ht[0].size = 4 的情况，index = 8 & 3 = 0，所以该节点会被放在如下位置：

¶1.3.5 解决键冲突

Redis 的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next 指针，多个哈希表节点可以用 next指针构成单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，如下图所示：

¶1.3.6 rehash

随着操作的不断执行，哈希表保存的键值会逐渐地增多或者减少，为了让哈希表地负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或收缩，即 rehash操作。

¶1.3.6.1 扩展收缩条件

负载因子的计算公式：

1 2	// 负载因子 = 哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size

哈希表的扩展的条件：

🔹 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且 load_factor >= 1；

🔸 服务器正在进行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且 load_factor >= 5。

根据 BGSAVE 命令或 BGREWEITEAOF 命令是否执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要地内存写入操作，最大限度地节约内存。

哈希表的收缩的条件：load_factor < 0.1

¶1.3.6.2 rehash 步骤

Redis 对字典地哈希表执行 rehash 的步骤如下：

1️⃣ 为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0] 当前包含的键值对数量（也即 ht[0].used 属性的值）：

🔹 扩展操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 $2^n$;

🔸 收缩操作，那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 $2^n$。

2️⃣ 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面：rehash 指的是重新计算键值对的哈希值和索引值，然后将键值对放置到 ht[1] 哈希表的指定位置上。

3️⃣ 将 ht[0] 包含的所有键值对都迁移到 ht[1] 之后（ht[0] 变为空表），释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

¶1.3.6.3 渐进式 rehash

上文 rehash 动作并不是一次性、集中式地完成地，而是分多次、渐进式地完成地，为了避免 rehash 对服务器性能造成影响。渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

以下是哈希表渐进式 rehash 的详细步骤：

1️⃣ 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。(分配空间策略见上)

2️⃣ 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，表示 rehash 工作正式开始。

3️⃣ 在 rehash 进行期间，每次对字典执行添加、删除、查改或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 属性的值增一。

4️⃣ 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这是程序 rehashidx 属性设置为 -1，表示 rehash 操作已完成。

注意：🙋‍♂

🔹 因为在渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的 删改查 操作会在两个哈希表上进行（增操作直接作用在 ht[1] ）。例如，字典要查找一个键，程序会现在 ht[0] 里面进行查找，如果没有找到，就会继续到 ht[1] 里面查找。

🔸 在渐进式 rehash 执行期间，新添加到字典的键值对一律被保存到 ht[1] 里面，这保证了 ht[0] 包含的键值对数量只减不增，并随着 rehash 操作的执行最终变成空表。

¶1.3.7 字典 API

《Redis 设计与实现》第四章

¶1.4 跳跃表

¶1.4.1 基本结构

跳跃表（ skiplist ）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均 $O(logN)$、最坏 $O(N)$ 时间复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

一个跳跃表如下图所示：

1️⃣ 最左边是 zskiplist 结构，包含以下属性：

🔹 header：指向跳跃表的表头节点；

🔸 tail：指向跳跃表的表尾节点；

🔹 level：记录目前跳跃表内，层数最大的那个节点的层数（表头节点的层数不计算在内）；

🔸 length：记录跳跃表的长度，也即跳跃表目前包含的节点数量（表头节点不计算在内）。

zskiplist 结构定义如下：

typedef struct zskiplist {
    // 表头节点和表尾节点
    struct skiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int level;
} zskiplist;

2️⃣ 位于 zskiplist 结构右侧的是四个 zskiplistNode 结构，该结构包含以下属性：

🔹 level：表示层数的结构体，内部包含两个属性：前进指针和跨度。前进指针用于方位位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离；

🔸 backward：指向位于当前节点的前一个节点，后退指针在程序中从表尾向表头遍历时使用；

🔹 score：各个节点所保存的分值，在跳跃表中节点按各自所保存的分值从小到大排列；

🔸 obj：各个节点中所保存的成员对象。

zskiplistNode 结构定义如下：

总结：⭐️

🔹 header 和 tail 指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的时间复杂度为 $O(1)$；

🔸 length 属性来记录节点的数量，程序可以在$O(1)$时间复杂度内返回跳跃表的长度；

🔹 level 属性则用于在 $O(1)$ 时间复杂度内获取跳跃表中层高最大的那个节点的层数量；

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

🔹 每个节点只有一个后退指针，所以每次只能后退至前一个节点，所以可以通过其实现从表尾到表头的遍历；

🔸 指向 NULL 的所有前进指针的跨度都为 0，因为他们没有连向任何节点。

¶1.4.2 跳跃表 API

《Redis 设计与实现》第五章

¶1. 5 整数集合

¶1.5.1 基本结构

整数集合（ intset ）是 Redis 用于保存整数值的集合抽象数据结构，它可以保存类型为 int16_t 、 int32_t 或者 int64_t 的整数值，并且保证集合中不会出现重复元素。其结构定义如下所示：

注意：🙋

🔹 contents 数组是整数集合的底层实现：整数集合的每个元素都是 contents 数组的一个数组项，每个项在数组中按照值的大小从小到大有序地排列，并且数组中不包含重复项。虽然声明为 int8_t 类型地数组，但是实际上 contents 数组并不保存任何 int8_t 类型地值，contents 数组地真正取值类型取决于 encoding 属性地值。

🔸 encoding 属性有三种策略：INTSET_ENC_INT16 、 INTSET_ENC_INT32 和 INTSET_ENC_INT64 ；分别对应了int16_t 、 int32_t 或者 int64_t 整数值。

🔹 length 属性记录了整个整数集合包含的元素数量，也即是 contents 数组的长度。

🔸 注意 contents 数组的大小 size = sizeof(int16_t or int36_t or int64_t) * length

一个包含五个 int16_t 类型整数值的整数集合如下所示：

¶1.5.2 升级

每当将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

注意：🙋‍♂ 此时添加的新元素必定是大于当前类型最大值，或者小于当前类型最小值的。也即是添加的新元素必定大于当前数组内所有元素值，或者小于当前数组内所有元素值。

升级整数集合并添加新元素共分为三个步骤：

1️⃣ 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

2️⃣ 将底层数组现有的元素都转化成与新元素相同的类型，并将类型转化后的元素放置到正确的位置上，而且在放置过程中，需要继续维持底层数组的有序性质不变。

🔹 如果添加的元素大于当前所有元素，将当前数组内最大的元素转化类型并搬移到新分配空间正确的位置（新 contents 数组倒数第二个索引位置），并依次 从后往前（倒序） 执行其他元素的操作，搬移的位置依次往前一个索引；

🔸 如果添加的元素小于当前所有元素，将当前数组内最大的元素转化类型并搬移到新分配空间正确的位置（新 contents 数组最后一个索引位置），并依次 从后往前（倒序） 执行其他元素的操作，搬移的位置依次往前一个索引；

3️⃣ 将新元素添加到底层数组里面。

🔹 如果添加的元素大于当前所有元素，新添加的元素放在新 contents 数组最后一个索引位置即可；

🔸 如果添加的元素小于当前所有元素，新添加的元素放在新 contents 数组第一个索引位置即可；

4️⃣ 更新 encoding 和 length 属性为正确值。

升级的好处 🌻

🔹 提升灵活性。整数集合可以通过自动升级底层数组来适应新元素。

🔸 节约内存。升级操作只会在有需要的时候进行，可以尽量节省内存。

注意：🥀 没有**降级**操作，升级之后，编码就会一直保持升级后的状态。

¶1.5.3 整数集合 API

《Redis 设计与实现》第六章

¶1.6 压缩列表

压缩列表（ziplist）是列表键和哈希键的底层实现之一。压缩列表是 Redis 为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。

¶1.6.1 基本结构

压缩链表的各个组成部分，以及其细节如下图描述：

¶1.6.2 压缩列表节点的构成

压缩列表每个节点都由 previous_entry_length、encoding 和 content 三个部分组成，如下图所示：

每个压缩列表节点可以保存一个字节数组或一个整数值。

其中 字节数组 可以是以下三种长度的其中一种，下面表格解释了原因：

🔹 长度小于等于 $63(2^6 - 1)$ 字节的数组，编码长度为一个字节，编码前两位固定为 00

🔸 长度小于等于 $16383(2^{14} - 1)$ 字节的数组，编码长度为两个字节，编码前两位固定为 01

🔹 长度小于等于 $4294967295(2^{32} - 1)$ 字节的数组，编码长度为五个字节，编码前两位固定为 10

其中 整数值 可以是以下六种长度中选择：

🔹 4位长，介于 0-12之间的无符号整数；

🔸 1字节长的有符号整数；

🔹 3字节长的有符号整数；

🔸 int16_t 类型整数；

🔹 int32_t 类型整数；

🔸 int64_t 类型整数；

¶1.6.2.1 `previous_entry_length`

节点的 previous_entry_length 属性以字节为单位，记录了压缩列表前一个节点长度。previous_entry_length 属性的长度可以是 1 字节或者 5 字节；

🔹 如果前一节点长度小于 254 字节，那么该字段一个字节即可；

🔸 如果前一个节点长度大于等于 254字节，那么该字段设置为 5 个字节，其中第一个字节会被设置为 0xFE，后面四个字节用来保存前一个节点的长度（足够了）。

🌻 **通过previous_entry_length** 可以计算出前一个节点的地址，压缩列表从表尾向表头的遍历操作就是使用这一原理。

¶1.6.2.2 `encoding`

节点 encoding 属性记录了节点 content 属性保存数据的类型以及长度。

字节数组编码见 1.6.2 节表格。整数编码见下表：

¶1.6.2.3 `content`

节点的 content 属性负责保存节点的值，节点值可以是一个字节数组或者整数值，值的类型和长度由节点的 encoding 属性决定。

两个简单的例子如下：

¶1.6.3 连锁更新

因为前一节点长度小于 254 字节，大于等于 254 字节，previous_entry_length 属性的长度不同，所以多个连续、长度介于 250 字节到 253 字节的节点，会因为在最前方添加节点长度大于等于 254 字节的新节点而导致程序将会对压缩列表这一串节点中的每个节点都执行空间重分配，这种现象被称之为“连锁更新”。

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

😄 但是它真正造成的性能问题几率很低：

🔹 首先压缩列表里要恰好有多个连续的、长度介于 250 - 253 字节之间的节点，连锁更新才可能发生，实际中不常见。

🔸 即使出现了连锁更新，但是只要被更新的节点数量不多，就不会对性能造成任何影响。

正是以上原因，ziplistPush 等命令的平均复杂度仅为 $O(N)$。

¶1.6.4 压缩列表 API

《Redis 设计与实现》第七章

¶2 对象

Redis 并没有直接使用上文这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统包含字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象，每种对象都用到了至少一种前文所述的数据结构。

¶2.1 基本结构

Redis 中的每个对象都是由一个 redisObject 结构表示，这个结构中保存数据有关的三个属性分别是 type 、encoding 和 ptr 属性：

¶2.1.1 `type`

¶2.1.2 `encoding`

对象的编码以及底层数据结构：

不同对象类型可能对应的编码：

¶2.2 字符串对象

¶2.2.1 字符串对象分类

字符串对象的编码可以是 **int **、 raw 或者 embstr。

int 编码的字符串对象：

raw 编码的字符串对象：

embstr 编码的字符串对象：

补充 🍖： embstr 编码是专门用于保存段字符串的一种优化编码方式，这种编码和 raw 编码一样，都是用 redisObject 结构和 sdshdr 结构来表示字符串对象，但 raw 会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，而 embstr 编码则通过调用一次内存分配函数来分配一块连续空间，空间中依次包含 redisObject 和 sdshdr 两个结构。

使用 embstr 编码的字符串对象来保存短字符串值有以下好处 🌻：

🔹 embstr 编码将创建字符串对象所需的内存分配次数从 raw 编码的两次将为了一次。

🔸 释放 embstr 编码的字符串对象也只需要调用一次内存释放函数即可，而 raw 编码需要两次。

🔹 因为 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这种编码的字符串对象比 raw 编码的字符串对象能够更好的利用缓存带来的优势。

注意：🙋‍♂

可以用 long double 类型表示的浮点数，在 Redis 中也是作为字符串值来保存的，如果要保存一个浮点数到字符串对象里面，那么程序会先将这个浮点数转化成字符串值，然后再保存转化所得的字符串值。

在有需要的时候，程序会将保存在字符串对象里面的字符串转化回浮点数值，执行默写操作，然后再将执行所得的浮点数值转化回字符串值，并继续保存在字符串对象里面。

¶2.2.2 编码转化

int 编码的字符串对象和 embstr 编码的字符串对象在条件满足的情况下，会被转化为 raw 编码的字符串对象。

🔹 对于 int 编码的字符串来说，如果对象执行一些命令后保存的不再是整数值，而是一个字符串值，那么字符串对象的编码将从 int 变为 raw;

🔸 因为 Redis 没有为 embstr 编码的字符串对象编写任何相应的修改程序，所以 embstr 编码的字符串对象实际上是只读的。当我们对 embstr 编码的字符串对象执行任何修改命令时，程序将会先将对象的编码从 embstr 转化为 raw，然后再执行修改命令。

¶2.2.3 字符串命令的实现

《Redis 设计与实现》第八章：第二节

¶2.3 列表对象

¶2.3.1 列表对象分类

列表对象的编码可以时 ziplist 或者 linkedlist。

ziplist 编码的列表对象：

linkedlist 编码的列表对象：

注意：🙋

linkedlist 编码的列表对象再底层的双端链表结构中包含多个字符串对象。（字符串对象是 Redis 五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

¶2.3.2 编码转化

当列表对象可以同时满足以下两个条件时，列表对象使用 ziplist 编码：

◻️ 列表对象保存的所有字符串元素的长度都小于 64 字节；

◻️ 列表对象保存的元素数量小于 512 个。

否则，一律使用 linkedlist 编码。（上面两个上限值可以被修改）

¶2.3.3 列表命令的实现

《Redis 设计与实现》第八章：第三节

¶2.4 哈希对象

¶2.4.1 哈希对象分类

哈希对象的编码可以是 ziplist 或者 hashtable。

ziplist 编码的哈希对象：

注意：🙋‍♂

ziplist 编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序回先将保存了键的压缩列表节点推入压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾，因此：

🔹 保存了同一键值对的两个节点总是紧紧挨在一起的，保存键的节点在前，保存值的节点在后；

🔸 先添加到哈希对象中的键值会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

hashtable 编码的哈希对象：

¶2.4.2 编码转化

当哈希对象可以同时满足以下两个条件时，哈希对象使用 ziplist 编码：

◻️ 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节；

◻️ 哈希对象保存的键值对数量小于 512 个。

否则，一律使用 hashtable 编码。（上面两个上限值可以被修改）

¶2.4.3 哈希命令的实现

《Redis 设计与实现》第八章：第四节

¶2.5 集合对象

¶2.5.1 集合对象分类

集合对象的编码可以是 intset 或者 hashtable。

intset 编码的集合对象：

hashtable 编码的集合对象：

¶2.5.2 编码转化

当集合对象可以同时满足以下两个条件时，集合对象使用 intset 编码：

◻️ 集合对象保存的所有元素的长度都是整数；

◻️ 集合对象保存的元素数量小于 512 个。

否则，一律使用 hashtable 编码。（上面的上限值可以被修改）

¶2.5.3 集合命令的实现

《Redis 设计与实现》第八章：第五节

¶2.6 有序集合对象

¶2.6.1 有序集合对象分类

有序集合对象的编码可以是 ziplist 或者 skiplist。

ziplist 编码的有序集合对象：

skiplist 编码的有序集合对象：

注意：🙋 上图字典和跳跃表中重复展示了各个元素的成员和分值，但在实际中，字典和跳跃表会共享元素的成员和分值（使用指针），所以不会造成任何数据重复，也不会因此而浪费资源。

skiplist 编码的有序集合对象使用 zset 结构作为底层实现，一个 zset 结构同时包含一个字典和一个跳跃表：

typedef struct zset {
    zskiplist *zsl;
    dict *dict;
} zset;

¶2.6.2 编码转化

当有序集合对象可以同时满足以下两个条件时，有序集合对象使用 ziplist 编码：

◻️ 有序集合对象保存的元素数量小于 128 个；

◻️ 集合对象保存的所有元素成员的长度都小于 64 字节。

否则，一律使用 skiplist 编码。（上面的上限值可以被修改）

¶2.6.3 有序集合命令的实现

《Redis 设计与实现》第八章：第六节

¶3 参考资料

《Redis 设计与实现》

Redis 数据结构与对象

¶1 数据结构

¶1.1 简单动态字符串

¶1.1.1 结构

¶1.1.2 C 字符串和 SDS 之间的区别

¶1.1.3 SDS API

¶1.2 链表

¶1.2.1 链表和链表节点的结构与实现

¶1.2.2 链表和链表节点的 API

¶1.3 字典

¶1.3.1 哈希表

¶1.3.2 哈希表节点

¶1.3.3 字典

¶1.3.4 哈希算法

¶1.3.5 解决键冲突

¶1.3.6 rehash

¶1.3.6.1 扩展收缩条件

¶1.3.6.2 rehash 步骤

¶1.3.6.3 渐进式 rehash

¶1.3.7 字典 API

¶1.4 跳跃表

¶1.4.1 基本结构

¶1.4.2 跳跃表 API

¶1. 5 整数集合

¶1.5.1 基本结构

¶1.5.2 升级

¶1.5.3 整数集合 API

¶1.6 压缩列表

¶1.6.1 基本结构

¶1.6.2 压缩列表节点的构成

¶1.6.2.1 previous_entry_length

¶1.6.2.2 encoding

¶1.6.2.3 content

¶1.6.3 连锁更新

¶1.6.4 压缩列表 API

¶2 对象

¶2.1 基本结构

¶2.1.1 type

¶2.1.2 encoding

¶2.2 字符串对象

¶2.2.1 字符串对象分类

¶2.2.2 编码转化

¶2.2.3 字符串命令的实现

¶2.3 列表对象

¶2.3.1 列表对象分类

¶2.3.2 编码转化

¶2.3.3 列表命令的实现

¶2.4 哈希对象

¶2.4.1 哈希对象分类

¶2.4.2 编码转化

¶2.4.3 哈希命令的实现

¶2.5 集合对象

¶2.5.1 集合对象分类

¶2.5.2 编码转化

¶2.5.3 集合命令的实现

¶2.6 有序集合对象

¶2.6.1 有序集合对象分类

¶2.6.2 编码转化

¶2.6.3 有序集合命令的实现

¶3 参考资料

¶1.6.2.1 `previous_entry_length`

¶1.6.2.2 `encoding`

¶1.6.2.3 `content`

¶2.1.1 `type`

¶2.1.2 `encoding`