最近由于部门培训需要，仓促总结了一下redis常用数据类型的数据结构，其中借鉴了一些其他博主的总结，也希望能把这一块知识点串起来，后续会做一个详细的整理。。。

一.基础知识

redis常用的五种数据类型：string（字符串），hash（哈希），list（列表），set（无序集合）及zset(有序集合)；

Redis 还有比较高级的3种数据结构：HyperLogLog、Geo、BloomFilter。

Redis 数据结构并不是指 String（字符串）对象、List（列表）对象、Hash（哈希）对象、Set（集合）对象和 Zset（有序集合）对象，因为这些是 Redis 键值对中值的数据类型，也就是数据的保存形式，这些对象的底层实现的方式就用到了数据结构。

Redis 数据类型的底层数据结构随着版本的更新也有所不同，如下图：

a、在 Redis 3.0 版本中 List 对象的底层数据结构由「双向链表」或「压缩表列表」实现，但是在 3.2 版本之后，List 数据类型底层数据结构是由 quicklist 实现的；

b、在最新的 Redis 代码（还未发布正式版本）中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

由上可知新旧版本的数据结构有8种：SDS、双向链表、压缩列表、哈希表、跳表、整数集合、quicklist、listpack，针对这8种数据结构我们做一次培训学习；

二、数据结构

1.SDS

1）C语言字符串存在的缺陷：

C 语言的字符串其实就是一个字符数组，即数组中每个元素是字符串中的一个字符，字符数组的结尾位置就用“\0”表示，意思是指字符串的结束。

缺陷：

a、获取字符串长度的时间复杂度为 O（N）；

b、字符串的结尾是以 “\0” 字符标识，字符串里面不能包含有 “\0” 字符，因此不能保存二进制数据；

c、字符串操作函数不高效且不安全，比如有缓冲区溢出的风险，有可能会造成程序运行终止；

2）SDS结构设计

下图就是 Redis 5.0 的 SDS 的数据结构：

结构中的每个成员变量分别介绍下：

a、len，记录了字符串长度。这样获取字符串长度的时候，只需要返回这个成员变量值就行，时间复杂度只需要 O（1）。 b、alloc，分配给字符数组的空间长度。这样在修改字符串的时候，可以通过 alloc - len 计算出剩余的空间大小，可以用来判断空间是否满足修改需求，如果不满足的话，就会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出的问题。 c、flags，用来表示不同类型的 SDS。一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，后面在说明区别之处。 d、buf[]，字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。

总结：Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、alloc、flags，用来解决 C 语言字符串的缺陷。

注意：

1） SDS 不需要用 “\0” 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 “\0” 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 “\0” 字符；

2）当判断出缓冲区大小不够用时，Redis 会自动将扩大 SDS 的空间大小（小于 1MB 翻倍扩容，大于 1MB 按 1MB 扩容），以满足修改所需的大小；

3）节省内存空间：SDS 结构中有个 flags 成员变量，表示的是 SDS 类型；

​ redis一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64；

​ 这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。比如 sdshdr16 和 sdshdr32 这两个类型，它们的定义分别如下：

​ 之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。比如，在保存小字符串时，结构头占用空间也比较少。

链表

1）定义

Redis 的 List 对象的底层实现之一就是链表。C 语言本身没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构。

链表节点结构设计：

有前置节点和后置节点，可以看的出，这个是一个双向链表：

​ 链表结构设计：

​ Redis 在 listNode 结构体基础上又封装了 list 这个数据结构，这样操作起来会更方便，链表结构如下：

​

​ list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。

​ 相关命令

​ 1）lpush命令：加入一个元素到左边的头部

​ 2）rpush命令：加入一个元素到右边的底部

​ 【注意】为了避免头部底部混乱，这里统一把左边的认为是头部，右边是底部，下面也是按照这样的做法。

​ 3）lpop命令：从左边头部取出第一个元素

​ 4）rpop命令：从右边底部取出第一个元素

​ 5）lrange命令：从左边开始列出list的元素

​ 6）llen命令：获取list的长度。

​ 链表的优势：

​ a、listNode 链表节点的结构里带有 prev 和 next 指针，获取某个节点的前置节点或后置节点的时间复杂度只需O(1)，而且这两个指针都可以指向 NULL，所以链表是无环链表；

​ b、list 结构因为提供了表头指针 head 和表尾节点 tail，所以获取链表的表头节点和表尾节点的时间复杂度只需O(1)； ​ c、list 结构因为提供了链表节点数量 len，所以获取链表中的节点数量的时间复杂度只需O(1)； ​ d、listNode 链表节使用 void* 指针保存节点值，并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数，因此链表节点可以保存各种不同类型的值；

​ 链表的缺陷：

​ a、链表每个节点之间的内存都是不连续的，意味着无法很好利用 CPU 缓存。能很好利用 CPU 缓存的数据结构就是数组，因为数组的内存是连续的，这样就可以充分利用 CPU 缓存来加速访问。

​ b、还有一点，保存一个链表节点的值都需要一个链表节点结构头的分配，内存开销较大。

注：a、Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构；

​ b、压缩列表存在性能问题（具体什么问题，下面会说），所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List 对象的底层数据结构改由 quicklist 实现；

​ c、在 Redis 5.0 设计了新的数据结构 listpack，沿用了压缩列表紧凑型的内存布局，最终在最新的 Redis 版本，将 Hash 对象和 Zset 对象的底层数据结构实现之一的压缩列表，替换成由 listpack 实现。

3.压缩列表

1）定义

压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。

Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不大的情况才会使用压缩列表作为底层数据结构。

设计思想是*通过时间换空间*，而时间的损耗又相对来说比小（小到几乎可以忽略）

2）压缩列表结构设计

压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。

压缩列表在表头有三个字段：

​ a、zlbytes，记录整个压缩列表占用对内存字节数；

​ b、zltail，记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；

​ c、zllen，记录压缩列表包含的节点数量；

​ d、zlend，标记压缩列表的结束点，固定值 0xFF（十进制255）。

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1)。而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。

压缩列表节点（entry）的构成如下：

压缩列表节点包含三部分内容：

​ a、prevlen，记录了「前一个节点」的长度；

​ b、encoding，记录了当前节点实际数据的类型以及长度；

​ c、data，记录了当前节点的实际数据；

根据前一个节点的长度不同，prevlen属性设置不同的空间大小

当我们往压缩列表中插入数据时，压缩列表就会根据数据是字符串还是整数，以及数据的大小，会使用不同空间大小的 prevlen 和 encoding 这两个元素里保存的信息，这种根据数据大小和类型进行不同的空间大小分配的设计思想，正是 Redis 为了节省内存而采用的。

1）prevlen 这个部分以字节为单位以十进制的形式保存，记录压缩列表节点的长度。属性长度可以是1字节、5字节。逻辑如下： a、当前一个节点的长度小于254字节，那么就是一个字节表示 b、如果前一个字节的长度大于等于254字节，那么prevlen的属性的长度就为5字节，其中第一字节会被设置为0xFE(十进制254)，后面的四个字节就用于保存前一节点的长度

当然这样存，在特定的情况下会出现非常消耗性能的连锁更新问题： 如果在一个压缩列表中，有多个连续的，长度介于250字节到253字节之间的节点。如图所示

当我们在entry1节点前加入一个前置节点entry0,大小为258字节。如图所示

由于entry1保存前置节点的prevlen仅有1字节，无法存储，需要扩展到5字节存储，但是这样就会使entry1的字节长度变化到253+5=258字节长度，这样，entry2的prevlen又无法存储entry1的字节长度，又需要扩展到5字节存储，这样以此类推，程序需要不断的执行空间重分配操作。 当然发生这种情况的机率很低，首先得列表里恰好要有多个连续的，长度介于250-253字节之间的节点，其次只要被更新的节点数量不多，就不会对性能造成影响

删除节点时也会导致连锁更新

2）encoding

该属性记录了节点数据的类型及长度。这个就有点意思了，该属性可能有1、2或者4字节，而最高位如果是00、01、10则代表存储的为字节数组，如果是11则代表的是整数。具体如下

3）data

保持实际的值

连锁更新：

压缩列表新增某个元素或修改某个元素时，如果空间不不够，压缩列表占用的内存空间就需要重新分配。而当新插入的元素较大时，可能会导致后续元素的 prevlen 占用空间都发生变化，从而引起「连锁更新」问题，导致每个元素的空间都要重新分配，造成访问压缩列表性能的下降。

Redis 针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构：quicklist（Redis 3.2 引入） 和 listpack（Redis 5.0 引入）。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的「连锁更新」的问题。

4.哈希表

1）定义

哈希表是一种保存键值对（key-value）的数据结构。

Redis 的 Hash 对象的底层实现之一是压缩列表（最新 Redis 代码已将压缩列表替换成 listpack）。Hash 对象的另外一个底层实现就是哈希表。

Redis 采用了「链式哈希」来解决哈希冲突

set中哈希表的value都是null，只用map的key实现集合。

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

注：字典又称符号表，关联数组或者映射，是一种用于保存键值对的抽象数据结构。

2）哈希表结构设计

Redis 的哈希表结构如下：

可以看到，哈希表是一个数组（dictEntry **table），数组的每个元素是一个指向「哈希表节点（dictEntry）」的指针。

哈希表节点的结构如下：

dictEntry 结构里不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。

另外，这里还跟你提一下，dictEntry 结构里键值对中的值是一个「联合体 v」定义的，因此，键值对中的值可以是一个指向实际值的指针，或者是一个无符号的 64 位整数或有符号的 64 位整数或double 类的值。这么做的好处是可以节省内存空间，因为当「值」是整数或浮点数时，就可以将值的数据内嵌在 dictEntry 结构里，无需再用一个指针指向实际的值，从而节省了内存空间。

2）rahash

在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表了。

rehash 这三个过程：

这个过程看起来简单，但是其实第二步很有问题，如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。

3）渐进式 rehash

Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

rehash 的触发条件跟**负载因子（load factor）**有关系。

负载因子可以通过下面这个公式计算：

触发 rehash 操作的条件，主要有两个：

a、当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。 b、当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。

hash如何使用压缩链表的？？？

5.整数集合

1）定义

整数集合是 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素，并且元素数量不时，就会使用整数集这个数据结构作为底层实现。

集合中的所有元素都可以转换成整数值，且长度小于512，使用intset，否则用hashtable。

2）整数集合结构设计

整数集合本质上是一块连续内存空间，它的结构定义如下：

可以看到，保存元素的容器是一个 contents 数组，虽然 contents 被声明为 int8_t 类型的数组，但是实际上 contents 数组并不保存任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如： a、如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t； b、如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t； c、如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

3）整数集合的升级操作

整数集合会有一个升级规则，就是当我们将一个新元素加入到整数集合里面，如果新元素的类型（int32_t）比整数集合现有所有元素的类型（int16_t）都要长时，整数集合需要先进行升级，也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里，当然升级的过程中，也要维持整数集合的有序性。

整数集合升级的好处：

整数集合升级就能避免这种情况，如果一直向整数集合添加 int16_t 类型的元素，那么整数集合的底层实现就一直是用 int16_t 类型的数组，只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时，才会对数组进行升级操作。

因此，整数集合升级的好处是节省内存资源。

注意：不支持降级操作

6.跳表

1）定义

Redis 只有在 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。

Zset 对象是唯一一个同时使用了两个数据结构来实现的 Redis 对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

Zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采用了哈希表进行索引。

举例：

如果希望一个集合中的元素是有序的，很自然的，我们会想到用有序链表来实现：

这样，对这个链表进行插入和查找操作的时间复杂度是O(N)，那么有没有更加高效的方法呢？

我们将有序链表中的部分节点进行分层，每一层都是一个有序链表，如图：

如果要查找30， 先从第三层的第一个节点开始，发现是1，小于30，查找下一个节点；下一个节点是9，小于30，继续查找下一个节点；发现是null，那么下降一层，来到第二层，仍然是9，查找下一个节点，发现等于30，查找结束。

如果采用有序链表，需要进行5次查找，而采用跳表只需要3次查找，在节点数很大的时候，性能的提升会更加明显。如果跳表的节点高度设置的合理，时间复杂度可以达到O(lgN)，跳表是一个典型的用空间换时间的优化案例。

2）跳表结构设计

链表在查找元素的时候，因为需要逐一查找，所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。

「跳表节点」的数据结构：

「跳表」结构体：

level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，比如 leve[0] 就表示第一层，leve[1] 就表示第二层。zskiplistLevel 结构体里定义了「指向下一个跳表节点的指针」和「跨度」，跨度时用来记录两个节点之间的距离。

属性说明：

header：指向跳表的头节点，头节点是跳表的一个标记节点，他不存储任何元素信息（ele永远为NULL，score永远为0），他的level数组长度为64，头节点不计入跳表总长度，头节点在初始化时，64个元素的forward都指向NULL，span值都为0 tail：指向跳表的尾节点 length：跳表的节点的个数（不包含头节点） level：跳表的节点的最大高度（不包括头节点）

跳表的优点：

跳表可以保证增、删、查等操作时的时间复杂度为O(logN)，且维持结构平衡的成本比较低，完全依靠随机。而二叉查找树在多次插入删除后，需要Rebalance来重新调整结构平衡。

跳表的缺点：

跳表占用的空间比较大（多级索引），其实就是一种空间换时间的思想。

跳表的查询：

跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。

跳表的相邻两层的节点数量最理想的比例是 2:1，查找复杂度可以降低到 O(logN)。

下图的跳表就是，相邻两层的节点数量的比例是 2 : 1

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？

如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。

Redis 则采用一种巧妙的方法是，跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。

这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高最大限制是 64。

具体实现：

跳表节点层高最小为1，最大为ZSKIPLIST_MAXLEVEL = 64。zslRandomLevel函数随机生成一个1~64的整数，作为节点的高度，高度越大，出现的概率越低。

上述代码中，通过while循环每次随机生成一个随机值，取这个随机值的低16位 （random()&0xFFFF）作为x，当x小于0.25*0xFFFF时，level+=1，否则退出while循环，最终返回level和64两者中的较小值。这样，很容易计算每个层高出现的概率。设p=ZSKIPLIST_P=0.25：

1.节点层高为1的概率为 (1-p) 2.节点层高为2的概率为 (1-p)*p 3.节点层高为3的概率为 (1-p)*p^2 4… 5.节点层高为n的概率为 (1-p)*p^2 当然，当节点层高大于64时，最终也会取64，所以实际上节点层高为64的概率为：

1 - (节点层高小于64的概率值和)

一个skiplist的生成过程：

由于层数是每次随机出来的，所以新插入一个节点并不会影响其他节点的层数。插入一个节点只需要修改节点前后的指针即可，降低了插入的复杂度。

ZSet中的字典和跳表布局：

7.quicklist

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或者压缩列表。然后在 Redis 3.2 的时候，List 对象的底层改由 quicklist 数据结构实现。

其实 quicklist 就是「双向链表 + 压缩列表」组合，因为一个 quicklist 就是一个链表，而链表中的每个元素又是一个压缩列表。

在前面讲压缩列表的时候，我也提到了压缩列表的不足，虽然压缩列表是通过紧凑型的内存布局节省了内存开销，但是因为它的结构设计，如果保存的元素数量增加，或者元素变大了，压缩列表会有「连锁更新」的风险，一旦发生，会造成性能下降。

quicklist 解决办法，通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

quicklist 的结构体跟链表的结构体类似，都包含了表头和表尾，区别在于 quicklist 的节点是 quicklistNode。

quicklist 字段描述： head：头结点

tail：尾结点

count：在所有的 ziplist 中的 entry 总数

len：quicklistNode 节点总数

fill：每个 quicklist 节点的最大容量

compress：quicklist 的压缩深度，0 表示所有节点都不压缩，否则就表示从两端开始有多少个节点不压缩

bookmark_count：bookmarks 数组的大小

bookmarks：是一个可选字段，用来 quicklist 重新分配内存空间时使用，不使用时不占用空

注意：为什么不全部节点都压缩，而是流出 compress 这个可配置的口子呢？ 其实从统计来看，list 两端的数据变更最为频繁，像 lpush，rpush，lpop，rpop 等命令都是在两端操作，如果频繁压缩或解压缩会代码不必要的性能损耗。

这里还有个 fill 字段，它的含义是每个 quicknode 节点的最大容量，不同的数值有不同的含义，默认是 -2，当然也可以配置为其他数值，具体数值含义如下：

-1：每个 quicklistNode 节点的 ziplist 所占字节数不能超过 4kb。（建议配置）

-2：每个 quicklistNode 节点的 ziplist 所占字节数不能超过 8kb。（默认配置 & 建议配置）

-3：每个 quicklistNode 节点的 ziplist 所占字节数不能超过 16kb。

-4：每个 quicklistNode 节点的 ziplist 所占字节数不能超过 32kb。

-5：每个 quicklistNode 节点的 ziplist 所占字节数不能超过 64kb。

任意正数：表示 ziplist 结构所最多包含的 entry 个数，最大为215215。

可以通过Redis修改参数list-max-ziplist-size配置节点所占内存大小

quicklistNode 字段描述： prev：指向链表前一个节点的指针

next：指向链表后一个节点的指针

zl：数据指针。如果当前节点的数据没有压缩，那么它指向一个 ziplist 结构；否则，它指向一个 quicklistLZF 结构

sz：表示 zl 指向的 ziplist 的总大小（包括 zlbytes, zltail, zllen, zlend 和各个 entry）。需要注意的是：如果ziplist 被压缩了，那么这个 sz 的值仍然是压缩前的 ziplist 大小

count：表示 ziplist 里面包含的数据项个数。这个字段只有 16bit

encoding：表示 ziplist 是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2 表示被压缩了（而且用的是 LZF 压缩算法），1 表示没有压缩

container：是一个预留字段。本来设计是用来表明一个 quicklist 节点下面是直接存数据，还是使用 ziplist 存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫 container）。但是，在目前的实现中，这个值是一个固定的值 2，表示使用 ziplist 作为数据容器

recompress：表示当前节点是否是临时使用的解压后的节点，当我们使用类似 lindex 这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置 recompress=1 做一个标记，等有机会再把数据重新压缩

attempted_compress：这个值只对 Redis 的自动化测试程序有用。我们不用管它

extra：其它扩展字段。目前Redis的实现里也没用上

插入操作：

quicklist可以选择在头部或者尾部进行插入(quicklistPushHead和quicklistPushTail)，而不管是在头部还是尾部插入数据，都包含两种情况：

如果头节点（或尾节点）上ziplist大小没有超过限制（即_quicklistNodeAllowInsert返回1），那么新数据被直接插入到ziplist中（调用ziplistPush）。 如果头节点（或尾节点）上ziplist太大了，那么新创建一个quicklistNode节点（对应地也会新创建一个ziplist），然后把这个新创建的节点插入到quicklist双向链表中。

也可以从任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，要比在头部和尾部的进行插入要复杂一些。

当插入位置所在的ziplist大小没有超过限制时，直接插入到ziplist中就好了； 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的ziplist中； 当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小也超过限制，这时需要新创建一个quicklist链表节点插入。 对于插入位置所在的ziplist大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要把当前ziplist分裂为两个节点，然后再其中一个节点上插入数据。

为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：

一部分是解释字段，另一部分是存放具体的数据字段。 解释字段可以占用1～3个字节，数据字段可能不存在。 解释字段|数据|…|解释字段|数据 1 LZF压缩的数据格式有3种，即解释字段有3种：

000LLLLL：字面型，解释字段占用1个字节，数据字段长度由解释字段后5位决定；L是数据长度字段，数据长度是长度字段组成的字面值加1。例如：0000 0001代表数据长度为2 LLLooooo oooooooo：简短重复型，解释字段占用2个字节，没有数据字段，数据内容与前面数据内容重复，重复长度小于8；L是长度字段，数据长度为长度字段的字面值加2, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：0010 0000 0000 0100代表与前面5字节处内容重复，重复3字节。 111ooooo LLLLLLLL oooooooo：批量重复型，解释字段占3个字节，没有数据字段，数据内容与前面内容重复；L是长度字段，数据长度为长度字段的字面值加9, o是偏移量字段，位置偏移量是偏移字段组成的字面值加1。例如：1110 0000 0000 0010 0001 0000代表与前面17字节处内容重复，重复11个字节。

1）zs 该压缩node的的总长度

2）compressed压缩后的数据片段(多个)，每个数据片段由解释字段和数据字段组成

3）当前ziplist未压缩长度存在于quicklistNode->sz字段中

4）当ziplist被压缩时，node->zl字段将指向quicklistLZF

LZF数据压缩的基本思想是：数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。

压缩算法的流程如下：遍历输入字符串，对当前字符及其后面2个字符进行散列运算，如果在Hash表中找到曾经出现的记录，则计算重复字节的长度以及位置，反之直接输出数据。

根据LZF压缩后的数据格式，可以较为容易地实现LZF的解压缩。需要注意的是，可能存在重复数据与当前位置重叠的情况，例如在当前位置前的15个字节处，重复了20个字节，此时需要按位逐个复制。

可以看到，quicklistNode 结构体里包含了前一个节点和下一个节点指针，这样每个 quicklistNode 形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以 quicklistNode 结构体里有个指向压缩列表的指针 *zl。

在向 quicklist 添加一个元素的时候，不会像普通的链表那样，直接新建一个链表节点。而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。------可能与删除节点导致的连锁更新有关系

这里又出现了一个配置参数：list-compress-depth 其实，当链表很长的时候，最频繁访问的就是两端的数据，中间被访问的频率比较低，所以我们可以将中间部分节点进行压缩，从而能够进一步节省空间。上面说的list-compress-depth就是来设置这个的。 这个参数的取值含义如下：

0：是个特殊值，表示都不压缩。这是redis的默认值 1：表示quicklist两端各有一个节点不被压缩，中间节点进行压缩 2：表示quicklist两端各有两个节点不被压缩，中间节点进行压缩 3：表示quicklist两端各有三个节点不被压缩，中间节点进行压缩 …以此类推 也就是会出现问题所说的，两端节点为ziplist，中间节点为quicklistZF

看上面的redis配置文件的默认配置。

8.listpack

quicklist 虽然通过控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题。

因为 quicklistNode 还是用了压缩列表来保存元素，压缩列表连锁更新的问题，来源于它的结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构。

于是，Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

listpack 结构设计 listpack 采用了压缩列表的很多优秀的设计，比如还是用一块连续的内存空间来紧凑地保存数据，并且为了节省内存的开销，listpack 节点会采用不同的编码方式保存不同大小的数据。

我们先看看 listpack 结构：

listpack 头包含两个属性，分别记录了 listpack 总字节数和元素数量，然后 listpack 末尾也有个结尾标识。图中的 listpack entry 就是 listpack 的节点了。

每个 listpack 节点结构如下：

主要包含三个方面内容：

encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码； data，实际存放的数据； len，encoding+data的总长度； 可以看到，listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

数据编码：

元素编码分为三部分，encoding，data, element-total-len, 对于数字类型字符串在int64_t范围内的都可以编码为数字型，将无data字段，元素值存储在encoding中。

1）encoding编码

2）字符串

3）element-total-len编码

element-total-len表示当前元素的总长度，用于逆序遍历listpack时使用。

listpack每个数据元素尾部都包含一个表示当前数据长度占用总字节数的长度数据。这部分内容主要是用来从右往左遍历、搜索数据使用。其内部也采取了一种编码机制进行数据编码后存储。 下面图片描述了这中编码方式：

listpack内部进行编解码的函数分别为：lpEncodeBackLen和lpDecodeBackLen。

下面采取一个具体数值分别描述编解码过程：

编码规则： 编码从低位到高位填充内存字节，即从左到右； 解码从高位到低位读取内存字节，即从右到左； 每个字节8位，只用低7位保存数值，最高位用来表示当前字节是否还有更多字节，0表示没有了，1表示还有。 编码的时候，除第一个字节，其他后续所有字节高位都为1；解码的时候，根据这个标志位来判断什么时候终止。

例子：268435400。其二进制表示如下：0b1111111111111111111111001000（28位）按照一个字节7位，刚好填满4个字节的28位。 按照以上规则 大于 2097152，小于268435455。因此需要4个字节来存放。 存放的内存地址用p指针指向

编码顺序如下：

1，右移21位，留下高7位。即 剩下0b1111111(7位）对应16进制为0x7F；把0X7F保存在p[0]位置； 2，右移14位，留下高14位，因为最高的7位，步骤1已经处理了，在这里值需要处理剩下的7位，故此将其与127(即低7位全部为1）与运算，截取这7位内容，假如这个结果暂时保存在变量T中。由于编码规则是：“除了第一个字节高位为0，其他任何字节的高位都为1"，因此p[1]第1位也需要是1；那么只需要把T和128(128二进制是b1000 0000)相或即可；最后把或的结果保存在p[1]位置。 3，右移7位，留下高21位，步骤1，2处理掉了这剩余21位中的高14位，在此也只需要处理21位中的低7位。方式如步骤2，先与127与运算，结果在和128或运算，然后再保存在p[3]位置； 4，步骤1，2，3都处理高21位，现在只剩下低7位。到此只需要和127与，再和128或，就可以得到应该保存在p[3]位置的值。 以上4个步骤就是对数字268435400的编码过程。编码结果保存在p0-p4之间的内存空间。 下面是每个最终的保存内存结果示意图：

解码顺序如下：

【解码是从右往左，假设当前指针p指向的是p[4]的内存地址。结果保存在v变量】

1，首先解码p[3]地址的字节：与127相与，取低7位的数值：0xC8 & 127 = 72; 保存在v中(v = 72) 测试该字节的第8位是否为1，与128与运算。0xC8 & 128 = 128，即该位为1，因为128二进制表示，第8位为1；继续步骤2， 2，解码p[2]地址的字节：与127相与，取低7位的数值：0xFF & 127 = 127；因为这是第二个字节，故此其内容应该是原数据的低8到14位的内容。因此需要左移7位，即127