张图 为了拿捏 40 完整版 数据结构 我画了 Redis

大家好，我是小林。

前几天发了一篇「为了拿捏 Redis 数据结构，我画了 20张图」，收获了很多好评，然而过后急于发文，有些中央没有写完，也有些中央写的不是很完善。

而后我最近花了很多时期来完善文章，不只参与了 Redis 新版本的两个数据结构，也在之前的文章内容参与了很多内容。

这次完整版终于来了，加了亿点点物品!

Redis 为什么那么快?

除了它是内存数据库，使得一切的操作都在内存上启动之外，还有一个关键起因，它成功的数据结构，使得咱们对数据启动增删查改操作时，Redis能高效的处置。

因此，这次咱们就来好好聊一下 Redis 数据结构，这个在面试中太常问了。

留意，Redis 数据结构并不是指 String(字符串)对象、List(列表)对象、Hash(哈希)对象、Set(汇合)对象和Zset(有序汇合)对象，由于这些是 Redis 键值对中值的数据类型，也就是数据的保留方式，这些对象的底层成功的方式就用到了数据结构。

我画了一张 Redis 数据类型(也叫 Redis 对象)和底层数据结构的对应关图，左边是 Redis 3.0版本的，也就是《Redis设计与成功》这本书解说的版本，如今看还是有点过期了，左边是如今 Github 最新的 Redis 代码的(还未颁布正式版本)。

可以看到，Redis 数据类型的底层数据结构随着版本的更新也有所不同，比如：

这次，小林把新旧版本的数据结构说图解一遍，共有 9种数据结构：SDS、双向链表、紧缩列表、哈希表、跳表、整数汇合、quicklist、listpack。

不多 BB 了，间接发车!

键值对数据库是怎样成功的?

在开局讲数据结构之前，先给引见下 Redis 是怎样成功键值对(key-value)数据库的。

Redis 的键值对中的 key 就是字符串对象，而 value 可以是字符串对象，也可以是汇合数据类型的对象，比如 List 对象、Hash对象、Set 对象和 Zset 对象。

举个例子，我这里列出几种 Redis 新增键值对的命令：

>HSETperson>RPUSHstu

这些命令代表着：

这些键值对是如何保留在 Redis 中的呢?

Redis 是经常使用了一个「哈希表」保留一切键值对，哈希表的最大好处就是让咱们可以用 O(1)的时期复杂度来极速查找到键值对。哈希表其实就是一个数组，数组中的元素叫做哈希桶。

Redis 的哈希桶是怎样保留键值对数据的呢?

哈希桶寄存的是指向键值对数据的指针(dictEntry*)，这样经过指针就能找到键值对数据，而后由于键值对的值可以保留字符串对象和汇合数据类型的对象，所以键值对的数据结构中并不是间接保留值自身，而是保留了void * key 和 void * value 指针，区分指向了实践的键对象和值对象，这样一来，即使值是汇合数据，也可以经过 void * value指针找到。

我这里画了一张 Redis 保留键值对所触及到的数据结构。

这些数据结构的外部细节，我先不开展讲，前面在讲哈希表数据结构的时刻，在详细的说说，由于用到的数据结构是一样的。这里先大略说下图中触及到的数据结构的名字和用途：

特意说明下，void * key 和 void * value 指针指向的是 Redis 对象，Redis 中的每个对象都由 redisObject结构示意，如下图：

对象结构里蕴含的成员变量：

我画了一张 Redis 键值对数据库的全景图，你就能明晰知道 Redis 对象和数据结构的相关了：

接下里，就好好聊一下底层数据结构!

字符串在 Redis 中是很罕用的，键值对中的键是字符串类型，值有时也是字符串类型。

Redis 是用 C 言语成功的，然而它没有间接经常使用 C 言语的 char* 字符数组来成功字符串，而是自己封装了一个名为繁难灵活字符串(simpledynamic string，SDS) 的数据结构来示意字符串，也就是 Redis 的 String 数据类型的底层数据结构是 SDS。

既然 Redis 设计了 SDS 结构来示意字符串，必需是 C 言语的 char* 字符数组存在一些毛病。

要了解这一点，得先来看看 char* 字符数组的结构。

C 言语字符串的毛病

C 言语的字符串其实就是一个字符数组，即数组中每个元素是字符串中的一个字符。

比如，下图就是字符串“xiaolin”的 char* 字符数组的结构：

没学过 C 言语的同窗，或许会猎奇为什么最后一个字符是“\0”?

在 C 言语里，对字符串操作时，char * 指针只是指向字符数组的起始位置，而字符数组的开头位置就用“\0”示意，意思是指字符串的完结。

因此，C 言语规范库中的字符串操作函数就经过判别字符是不是 “\0” 来选择要不要中止操作，假设字符不是 “\0”，说明字符串还没完结，可以继续操作，假设字符是 “\0” 是则说明字符串完结了，就要中止操作。

举个例子，C 言语失掉字符串长度的函数 strlen，就是经过字符数组中的每一个字符，并启动计数，等遇到字符为 “\0”后，就会中止遍历，而后前往曾经统计到的字符个数，即为字符串长度。下图显示了 strlen 函数的执行流程：

很显著，C 言语失掉字符串长度的时期复杂度是 O(N)(这是一个可以改良的中央)

C 言语字符串用 “\0” 字符作为开头标志有个毛病。假定有个字符串中有个 “\0” 字符，这时在操作这个字符串时就会延迟完结，比如“xiao\0lin” 字符串，计算字符串长度的时刻则会是 4，如下图：

因此，除了字符串的末尾之外，字符串外面不能含有 “\0” 字符，否则最先被程序读入的 “\0” 字符将被误以为是字符串开头，这个限度使得 C言语的字符串只能保留文本数据，不能保留像图片、音频、视频文明这样的二进制数据(这也是一个可以改良的中央)

另外， C 言语规范库中字符串的操作函数是很不安保的，对程序员很不友好，稍微一不留意，就会造成缓冲区溢出。

举个例子，strcat 函数是可以将两个字符串拼接在一同。

//将src字符串拼接到dest字符串前面

C 言语的字符串是不会记载自身的缓冲区大小的，所以 strcat 函数假定程序员在执行这个函数时，曾经为 dest 调配了足够多的内存，可以容纳 src字符串中的一切内容，而一旦这个假定不成立，就会出现缓冲区溢出将或许会形成程序运转中断，(这是一个可以改良的中央)。

而且，strcat 函数和 strlen 函数相似，时期复杂度也很高，也都要求先经过遍历字符串才干失掉指标字符串的末尾。而后关于 strcat函数来说，还要再遍历源字符串才干成功追加，对字符串的操作效率不高。

好了， 经过以上的剖析，咱们可以得悉 C 言语的字符串无余之处以及可以改良的中央：

Redis 成功的 SDS 的结构就把上方这些疑问处置了，接上去咱们一同看看 Redis 是如何处置的。

SDS 结构设计

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

结构中的每个成员变量区分引见下：

总的来说，Redis 的 SDS 结构在原本字符数组之上，参与了三个元数据：len、alloc、flags，用来处置 C 言语字符串的毛病。

O(1)复杂度失掉字符串长度

C 言语的字符串长度失掉 strlen 函数，要求经过遍历的方式来统计字符串长度，时期复杂度是 O(N)。

而 Redis 的 SDS 结构由于参与了 len 成员变量，那么失掉字符串长度的时刻，间接前往这个成员变量的值就行，所以复杂度只要 O(1)。

二进制安保

由于 SDS 不要求用 “\0” 字符来标识字符串开头了，而是有个专门的 len 成员变量来记载长度，所以可存储蕴含 “\0” 的数据。然而 SDS为了兼容局部 C 言语规范库的函数， SDS 字符串开头还是会加上 “\0” 字符。

因此， SDS 的 API 都是以处置二进制的方式来处置 SDS 寄存在 buf[]里的数据，程序不会对其中的数据做任何限度，数据写入的时刻时什么样的，它被读取时就是什么样的。

经过经常使用二进制安保的 SDS，而不是 C 字符串，使得 Redis 不只可以保留文本数据，也可以保留恣意格局的二进制数据。

不会出现缓冲区溢出

C 言语的字符串规范库提供的字符串操作函数，大少数(比如 strcat追加字符串函数)都是不安保的，由于这些函数把缓冲区大小能否满足操作需求的上班交由开发者来保障，程序外部并不会判别缓冲区大小能否足够用，当出现了缓冲区溢出就有或许形成程序意外完结。

所以，Redis 的 SDS 结构里引入了 alloc 和 len 成员变量，这样 SDS API 经过 alloc - len计算，可以算出残余可用的空间大小，这样在对字符串做修正操作的时刻，就可以由程序外部判别缓冲区大小能否足够用。

而且，当判别出缓冲区大小不够用时，Redis 会智能将扩展 SDS 的空间大小(小于 1MB 翻倍扩容，大于 1MB 按 1MB扩容)，以满足修正所需的大小。

在扩展 SDS 空间之前，SDS API 会优先审核未经常使用空间能否足够，假设不够的话，API 不只会为 SDS 调配修正所必要求的空间，还会给 SDS调配额外的「未经常使用空间」。

这样的好处是，下次在操作 SDS 时，假设 SDS 空间够的话，API 就会间接经常使用「未经常使用空间」，而毋庸执行内存调配，有效的缩小内存调配次数。

所以，经常使用 SDS 即不要求手动修正 SDS 的空间大小，也不会出现缓冲区溢出的疑问。

节俭内存空间

SDS 结构中有个 flags 成员变量，示意的是 SDS 类型。

Redos 一共设计了 5 种类型，区分是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。

这 5 种类型的关键区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

比如 sdshdr16 和 sdshdr32 这两个类型，它们的定义区分如下：

可以看到：

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

除了设计不同类型的结构体，Redis 在编程上还经常使用了专门的编译提升来节俭内存空间，即在 struct 申明了 __attribute__((packed)) ，它的作用是：通知编译器敞开结构体在编译环节中的提升对齐，按如实践占用字节数启动对齐。

比如，sdshdr16 类型的 SDS，自动状况下，编译器会依照 16 字节对齐的方式给变量调配内存，这象征着，即使一个变量的大小不到 16个字节，编译器也会给它调配 16 个字节。

举个例子，假定上方这个结构体，它有两个成员变量，类型区分是 char 和 int，如下所示：

大家猜猜这个结构体大小是多少?我先间接说答案，这个结构体大小计算进去是 8。

这是由于自动状况下，编译器是经常使用「字节对齐」的方式调配内存，只管 char 类型只占一个字节，然而由于成员变量里有 int 类型，它占用了 4个字节，所以在成员变量为 char 类型调配内存时，会调配 4 个字节，其中这多余的 3 个字节是为了字节对齐而调配的，相当于有 3 个字节被糜费掉了。

假设不想编译器经常使用字节对齐的方式启动调配内存，可以驳回了 __attribute__ ((packed))属性定义结构体，这样一来，结构体实践占用多少内存空间，编译器就调配多少空间。

比如，我用 __attribute__ ((packed)) 属性定义上方的结构体 ，雷同蕴含 char 和 int两个类型的成员变量，代码如下所示：

这时打印的结果是 5(1 个字节 char + 4 字节 int)。

可以看得出，这是按如实践占用字节数启动调配内存的，这样可以节俭内存空间。

链表

大家最相熟的数据结构除了数组之外，我置信就是链表了。

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

链表节点结构设计

先来看看「链表节点」结构的样子：

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

链表结构设计

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

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

举个例子，上方是由 list 结构和 3 个 listNode 结构组成的链表。

链表的优势与毛病

Redis 的链表成功优势如下：

链表的毛病也是有的：

因此，Redis 3.0 的 List对象在数据量比拟少的状况下，会驳回「紧缩列表」作为底层数据结构的成功，它的优势是节俭内存空间，并且是内存紧凑型的数据结构。

不过，紧缩列表存在性能疑问(详细什么疑问，上方会说)，所以 Redis 在 3.2 版本设计了新的数据结构 quicklist，并将 List对象的底层数据结构改由 quicklist 成功。

而后在 Redis 5.0 设计了新的数据结构 listpack，沿用了紧缩列表紧凑型的内存规划，最终在最新的 Redis 版本，将 Hash 对象和Zset 对象的底层数据结构成功之一的紧缩列表，交流成由 listpack 成功。

紧缩列表

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

然而，紧缩列表的毛病也是有的：

因此，Redis 对象(List 对象、Hash 对象、Zset 对象)蕴含的元素数量较少，或许元素值不大的状况才会经常使用紧缩列表作为底层数据结构。

接上去，就跟大家详细聊下紧缩列表。

紧缩列表结构设计

紧缩列表是 Redis 为了浪费内存而开发的，它是由延续内存块组成的顺序型数据结构，有点相似于数组。

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

在紧缩列表中，假设咱们要查找定位第一个元素和最后一个元素，可以经过表头三个字段的长度间接定位，复杂度是O(1)。而查找其余元素时，就没有这么高效了，只能逐一查找，此时的复杂度就是 O(N) 了，因此紧缩列表不适宜保留过多的元素。

另外，紧缩列表节点(entry)的构成如下：

紧缩列表节点蕴含三局部内容：

当咱们往紧缩列表中拔出数据时，紧缩列表就会依据数据是字符串还是整数，以及数据的大小，会经常使用不同空间大小的 prevlen 和 encoding这两个元素里保留的消息，这种依据数据大小和类型启动不同的空间大小调配的设计思维，正是 Redis 为了节俭内存而驳回的。

区分说下，prevlen 和 encoding 是如何依据数据的大小和类型来启动不同的空间大小调配。

紧缩列表里的每个节点中的 prevlen 属性都记载了「前一个节点的长度」，而且 prevlen 属性的空间大小跟前一个节点长度值无关，比如：

encoding 属性的空间大小跟数据是字符串还是整数，以及字符串的长度无关：

假设节点的数据是整数，则 encoding 会经常使用 1 字节的空间启动编码。

假设节点的数据是字符串，依据字符串的长度大小，encoding 会经常使用 1 字节/2字节/5字节的空间启动编码。

连锁更新

紧缩列表除了查找复杂度高的疑问，还有一个疑问。

紧缩列表新增某个元素或修正某个元素时，假设空间不不够，紧缩列表占用的内存空间就要求从新调配。而当新拔出的元素较大时，或许会造成后续元素的 prevlen占用空间都出现变动，从而惹起「连锁更新」疑问，造成每个元素的空间都要从新调配，形成访问紧缩列表性能的降低。

前面提到，紧缩列表节点的 prevlen 属性会依据前一个节点的长度启动不同的空间大小调配：

如今假定一个紧缩列表中有多个延续的、长度在 250～253 之间的节点，如下图：

由于这些节点长度值小于 254 字节，所以 prevlen 属性要求用 1 字节的空间来保留这个长度值。

这时，假设将一个长度大于等于 254 字节的新节点参与到紧缩列表的表头节点，即新节点将成为 e1 的前置节点，如下图：

由于 e1 节点的 prevlen 属性只要 1 个字节大小，不可保留新节点的长度，此时就要求对紧缩列表的空间重调配操作，并将 e1 节点的prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

多米诺牌的效应就此开局。

e1 原本的长度在 250～253 之间，由于刚才的扩展空间，此时 e1 的长度就大于等于 254 了，因此原本 e2 保留 e1 的 prevlen属性也必需从 1 字节扩展至 5 字节大小。

正如扩展 e1 引发了对 e2 扩展一样，扩展 e2 也会引发对 e3 的扩展，而扩展 e3 又会引发对 e4 的扩展…. 不时继续到开头。

这种在不凡状况下发生的延续屡次空间扩展操作就叫做「连锁更新」，就像多米诺牌的效应一样，第一张牌倒下了，推进了第二张牌倒下;第二张牌倒下，又推进了第三张牌倒下….，

紧缩列表的毛病

空间扩展操作也就是从新调配内存，因此连锁更新一旦出现，就会造成紧缩列表占用的内存空间要屡次从新调配，这就会间接影响到紧缩列表的访问性能。

所以说，只管紧缩列表紧凑型的内存规划能节俭内存开支，然而假设保留的元素数量参与了，或是元素变大了，会造成内存从新调配，最蹩脚的是会有「连锁更新」的疑问。

因此，紧缩列表只会用于保留的节点数量不多的场景，只需节点数量足够小，即使出现连锁更新，也是能接受的。

虽说如此，Redis 针对紧缩列表在设计上的无余，在起初的版本中，新增设计了两种数据结构：quicklist(Redis 3.2 引入) 和listpack(Redis 5.0 引入)。这两种数据结构的设计指标，就是尽或许地坚持紧缩列表节俭内存的优势，同时处置紧缩列表的「连锁更新」的疑问。

哈希表

哈希表是一种保留键值对(key-value)的数据结构。

哈希表中的每一个 key 都是唯一无二的，程序可以依据 key 查找到与之关联的 value，或许经过 key 来更新 value，又或许依据 key来删除整个 key-value等等。

在讲紧缩列表的时刻，提到过 Redis 的 Hash 对象的底层成功之一是紧缩列表(最新 Redis 代码已将紧缩列表交流成 listpack)。Hash对象的另外一个底层成功就是哈希表。

哈希表优势在于，它能以 O(1) 的复杂度极速查问数据。怎样做到的呢?将 key 经过 Hash函数的计算，就能定位数据在表中的位置，由于哈希表实践上是数组，所以可以经过索引值极速查问到数据。

然而存在的危险也是有，在哈希表大小固定的状况下，随着数据不时增多，那么哈希抵触的或许性也会越高。

处置哈希抵触的方式，有很多种。

Redis驳回了「链式哈希」来处置哈希抵触，在不扩容哈希表的前提下，将具备相反哈希值的数据串起来，构成链接起，以便这些数据在表中依然可以被查问到。

接上去，详细说说哈希表。

哈希表结构设计

Redis 的哈希表结构如下：

//哈希表大小掩码，用于计算索引值//该哈希表已有的节点数量

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

哈希表节点的结构如下：

//指向下一个哈希表节点，构成链表

dictEntry结构里不只蕴含指向键和值的指针，还蕴含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相反的键值对链接起来，以此来处置哈希抵触的疑问，这就是链式哈希。

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

哈希抵触

哈希表实践上是一个数组，数组里多每一个元素就是一个哈希桶。

当一个键值对的键经过 Hash 函数计算后失掉哈希值，再将(哈希值 % 哈希表大小)取模计算，失掉的结果值就是该 key-value对应的数组元素位置，也就是第几个哈希桶。

什么是哈希抵触呢?

举个例子，有一个可以寄存 8 个哈希桶的哈希表。key1 经过哈希函数计算后，再将「哈希值 % 8 」启动取模计算，结果值为 1，那么就对应哈希桶1，相似的，key9 和 key10 区分对应哈希桶 1 和桶 6。

此时，key1 和 key9 对应到了相反的哈希桶中，这就出现了哈希抵触。

因此，当有两个以上数量的 kay 被调配到了哈希表中同一个哈希桶上时，此时称这些 key 出现了抵触。

链式哈希

Redis 驳回了「链式哈希」的方法来处置哈希抵触。

链式哈希是怎样成功的?

成功的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next指针构成一个单项链表，被调配到同一个哈希桶上的多个节点可以用这个单项链表衔接起来，这样就处置了哈希抵触。

还是用前面的哈希抵触例子，key1 和 key9 经过哈希计算后，都落在同一个哈希桶，链式哈希的话，key1 就会经过 next 指针指向key9，构成一个单向链表。

不过，链式哈希局限性也很显著，随着链表长度的参与，在查问这一位置上的数据的耗时就会参与，毕竟链表的查问的时期复杂度是 O(n)。

要想处置这一疑问，就要求启动 rehash，也就是对哈希表的大小启动扩展。

接上去，看看 Redis 是如何成功的 rehash 的。

哈希表结构设计的这一小节，我给大家引见了 Redis 经常使用 dictht 结构体示意哈希表。不过，在实践经常使用哈希表时，Redis 定义一个 dict结构体，这个结构体里定义了两个哈希表(ht[2])。

//两个Hash表，交替经常使用，用于rehash操作

之所以定义了 2 个哈希表，是由于启动 rehash 的时刻，要求用上 2 个哈希表了。

在反常服务恳求阶段，拔出的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被调配空间。

随着数据逐渐增多，触发了 rehash 操作，这个环节分为三步：

为了繁难你了解，我把 rehash 这三个环节画在了上方这张图：

这个环节看起来繁难，然而其实第二步很有疑问，假设「哈希表 1 」的数据量十分大，那么在迁徙至「哈希表 2 」的时刻，由于会触及少量的数据拷贝，此时或许会对Redis 形成阻塞，不可服务其余恳求。

渐进式 rehash

为了防止 rehash 在数据迁徙环节中，因拷贝数据的耗时，影响 Redis 性能的状况，所以 Redis 驳回了渐进式rehash，也就是将数据的迁徙的上班不再是一次性性迁徙成功，而是分屡次迁徙。

渐进式 rehash 步骤如下：

这样就奇妙地把一次性性少量数据迁徙上班的开支，摊派到了屡次处置恳求的环节中，防止了一次性性 rehash 的耗时操作。

在启动渐进式 rehash 的环节中，会有两个哈希表，所以在渐进式 rehash启动时期，哈希表元素的删除、查找、更新等操作都会在这两个哈希表启动。

比如，查找一个 key 的值的话，先会在「哈希表 1」 外面启动查找，假设没找到，就会继续到哈希表 2 外面启动找到。

另外，在渐进式 rehash 启动时期，新增一个 key-value 时，会被保留到「哈希表 2 」外面，而「哈希表 1」则不再启动任何参与操作，这样保障了「哈希表 1 」的 key-value 数量只会缩小，随着 rehash 操作的成功，最终「哈希表 1」就会变成空表。

rehash 触发条件

引见了 rehash 那么多，还没说什么时状况下会触发 rehash 操作呢?

rehash 的触发条件跟负载因子(load factor)有相关。

负载因子可以经过上方这个公式计算：

触发 rehash 操作的条件，关键有两个：

整数汇合

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

整数汇合结构设计

整数汇合实质上是一块延续内存空间，它的结构定义如下：

可以看到，保留元素的容器是一个 contents 数组，只管 contents 被申明为 int8_t 类型的数组，然而实践上 contents数组并不保留任何 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如：

不同类型的 contents 数组，象征着数组的大小也会不同。

整数汇合的更新操作

整数汇合会有一个更新规定，就是当咱们将一个新元素参与到整数汇合外面，假设新元素的类型(int32_t)比整数汇合现有一切元素的类型(int16_t)都要长时，整数汇合要求先启动更新，也就是按新元素的类型(int32_t)扩展contents 数组的空间大小，而后才干将新元素参与到整数汇合里，当然更新的环节中，也要维持整数汇合的有序性。

整数汇合更新的环节不会从新调配一个新类型的数组，而是在原本的数组上扩展空间，而后在将每个元素按距离类型大小宰割，假设 encoding 属性值为INTSET_ENC_INT16，则每个元素的距离就是 16 位。

举个例子，假定有一个整数汇合里有 3 个类型为 int16_t 的元素。

如今，往这个整数汇合中参与一个新元素 65535，这个新元素要求用 int32_t 类型来保留，所以整数汇合要启动更新操作，首先要求为 contents数组扩容，在原本空间的大小之上再扩容多 80 位(4x32-3x16=80)，这样就能保留下 4 个类型为 int32_t 的元素。

扩容完 contents 数组空间大小后，要求将之前的三个元素转换为 int32_t类型，并将转换后的元素搁置到正确的位上方，并且要求维持底层数组的有序性不变，整个转换环节如下：

整数汇合更新有什么好处呢?

假设要让一个数组同时保留 int16_t、int32_t、int64_t 类型的元素，最繁难做法就是间接经常使用 int64_t类型的数组。不过这样的话，当假设元素都是 int16_t 类型的，就会形成内存糜费的状况。

整数汇合更新就能防止这种状况，假设不时向整数汇合参与 int16_t 类型的元素，那么整数汇合的底层成功就不时是用 int16_t类型的数组，只要在咱们要将 int32_t 类型或 int64_t 类型的元素参与到汇合时，才会对数组启动更新操作。

因此，整数汇合更新的好处是节俭内存资源。

整数汇合允许升级操作吗?

不允许升级操作，一旦对数组启动了更新，就会不时坚持更新后的形态。比如前面的更新操作的例子，假设删除了 65535 元素，整数汇合的数组还是 int32_t类型的，并不会因此升级为 int16_t 类型。

跳表

Redis 只要在 Zset 对象的底层成功用到了跳表，跳表的优势是能允许平均 O(logN) 复杂度的节点查找。

Zset 对象是惟逐一个同时经常使用了两个数据结构来成功的 Redis对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能启动高效的范围查问，也能启动高效单点查问。

Zset 对象能允许范围查问(如 ZRANGEBYSCORE 操作)，这是由于它的数据结构设计驳回了跳表，而又能以常数复杂度失掉元素权重(如 ZSCORE操作)，这是由于它同时驳回了哈希表启动索引。

接上去，详细的说下跳表。

跳表结构设计

链表在查找元素的时刻，由于要求逐一查找，所以查问效率十分低，时期复杂度是O(N)，于是就出现了跳表。跳表是在链表基础上改良上来的，成功了一种「多层」的有序链表，这样的好处是能快读定位数据。

那跳表长什么样呢?我这里举个例子，下图展现了一个层级为 3 的跳表。

图中头节点有 L0~L2 三个头指针，区分指向了不同层级的节点，而后每个层级的节点都经过指针衔接起来：

假设咱们要在链表中查找节点 4 这个元素，只能从头开局遍历链表，要求查找 4 次，而经常使用了跳表后，只要求查找 2 次就能定位到节点4，由于可以在头节点间接从 L2 层级跳到节点 3，而后再往前遍历找到节点 4。

可以看到，这个查找环节就是在多个层级上跳来跳去，最后定位到元素。当数据量很大时，跳表的查找复杂度就是 O(logN)。

那跳表节点是怎样成功多层级的呢?这就要求看「跳表节点」的数据结构了，如下：

//节点的数组，保留每层上的前向指针和跨度

Zset 对象要同时保留元素和元素的权重，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score变量。每个跳表节点都有一个后向指针，指向前一个节点，目的是为了繁难从跳表的尾节点开局访问节点，这样倒序查找时很繁难。

跳表是一个带有层级相关的链表，而且每一层级可以蕴含多个节点，每一个节点经过指针衔接起来，成功这一个性就是靠跳表节点结构体中的zskiplistLevel结构体类型的 level 数组。

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

比如，上方这张图，展现了各个节点的跨度。

第一眼看到跨度的时刻，以为是遍历操作无关，实践上并没有任何相关，遍历操作只要求用前向指针就可以成功了。

跨度实践上是为了计算这个节点在跳表中的排位。详细怎样做的呢?由于跳表中的节点都是按序陈列的，那么计算某个节点排位的时刻，从头节点点到该结点的查问门路上，将沿途访问过的一切层的跨度累加起来，失掉的结果就是指标节点在跳表中的排位。

举个例子，查找图中节点 3 在跳表中的排位，从头节点开局查找节点 3，查找的环节只经过了一个层(L3)，并且层的跨度是 3，所以节点 3 在跳表中的排位是3。

另外，图中的头节点其实也是 zskiplistNode 跳表节点，只不过头节点的后向指针、权重、元素值都会被用到，所以图中省略了这局部。

疑问来了，由谁定义哪个跳表节点是头节点呢?这就引见「跳表」结构体了，如下所示：

跳表结构里蕴含了：

跳表节点查问环节

查找一个跳表节点的环节时，跳表会从头节点的最上层开局，逐一遍历每一层。在遍历某一层的跳表节点时，会用跳表节点中的 SDS类型的元素和元素的权重来启动判别，共有两个判别条件：

假设上方两个条件都不满足，或许下一个节点为空时，跳表就会经常使用目前遍历到的节点的 level数组里的下一层指针，而后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

举个例子，下图有个 3 层级的跳表。

假设要查找「元素：abcd，权重：4」的节点，查找的环节是这样的：

跳表节点层数设置

跳表的相邻两层的节点数量的比例会影响跳表的查问性能。

举个例子，下图的跳表，第二层的节点数量只要 1 个，而第一层的节点数量有 6 个。

这时，假构想要查问节点 6，那基本就跟链表的查问复杂度一样，就要求在第一层的节点中依次顺序查找，复杂度就是 O(N)了。所以，为了降低查问复杂度，咱们就要求维持相邻层结点数间的相关。

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

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

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

假设驳回新增节点或许删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开支。

Redis 则驳回一种奇妙的方法是，跳表在创立节点的时刻，随机生成每个节点的层数，并没有严厉维持相邻两层的节点数量比例为 2 : 1 的状况。

详细的做法是，跳表在创立节点时刻，会生成范围为[0-1]的一个随机数，假设这个随机数小于 0.25(相当于概率 25%)，那么层数就参与 1层，而后继续生成下一个随机数，直到随机数的结果大于 0.25 完结，最终确定该节点的层数。

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

在 Redis 3.0 之前，List 对象的底层数据结构是双向链表或许紧缩列表。而后在 Redis 3.2 的时刻，List 对象的底层改由quicklist 数据结构成功。

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

在前面讲紧缩列表的时刻，我也提到了紧缩列表的无余，只管紧缩列表是经过紧凑型的内存规划节俭了内存开支，然而由于它的结构设计，假设保留的元素数量参与，或许元素变大了，紧缩列表会有「连锁更新」的危险，一旦出现，会形成性能降低。

quicklist处置方法，经过控制每个链表节点中的紧缩列表的大小或许元素个数，来规避连锁更新的疑问。由于紧缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。

quicklist 结构设计

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

//一切紧缩列表中的总元素个数

接上去看看，quicklistNode 的结构定义：

//紧缩列表的的字节大小unsigned

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

我画了一张图，繁难你了解 quicklist 数据结构。

在向 quicklist参与一个元素的时刻，不会像普通的链表那样，间接新建一个链表节点。而是会审核插上天位的紧缩列表能否能容纳该元素，假设能容纳就间接保留到 quicklistNode结构里的紧缩列表，假设不能容纳，才会新建一个新的 quicklistNode 结构。

quicklist 会控制 quicklistNode结构里的紧缩列表的大小或许元素个数，来规避潜在的连锁更新的危险，然而这并没有齐全处置连锁更新的疑问。

quicklist 只管经过控制 quicklistNode结构里的紧缩列表的大小或许元素个数，来缩小连锁更新带来的性能影响，然而并没有齐全处置连锁更新的疑问。

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

我看了 Redis 的 Github，在最新 6.2 发行版本中，Redis Hash 对象、Set 对象的底层数据结构的紧缩列表还未被交流成listpack，而 Redis 的最新代码(还未颁布版本)曾经将一切用到紧缩列表底层数据结构的 Redis 对象交流成 listpack数据结构来成功，预计不久未来，Redis 就会颁布一个将紧缩列表为 listpack 的发行版本。

listpack 结构设计

listpack 驳回了紧缩列表的很多低劣的设计，比如还是用一块延续的内存空间来紧凑地保留数据，并且为了节俭内存的开支，listpack节点会驳回不同的编码方式保留不同大小的数据。

咱们先看看 listpack 结构：

listpack 头蕴含两个属性，区分记载了 listpack 总字节数和元素数量，而后 listpack 末尾也有个开头标识。图中的 listpackentry 就是 listpack 的节点了。

每个 listpack 节点结构如下：

关键蕴含三个方面内容：

可以看到，listpack 没有紧缩列表中记载前一个节点长度的字段了，listpack 只记载节点的长度，当咱们向 listpack参与一个新元素的时刻，不会影响其余节点的长度字段的变动，从而防止了紧缩列表的连锁更新疑问。

参考资料：

总结

终于完工了，松一口吻。

良久没写那么长的图解技术文啦，这次潇洒脱洒写了 2 万字 + 画了 35 多张图，破费了不少时期，又是看书，又是看源码。

宿愿这篇文章，能帮你废弃 Redis 数据结构的迷雾!

我是小林，咱们下次再见。