共计 3485 个字符，预计需要花费 9 分钟才能阅读完成。

baiyan
全部视频：https://segmentfault.com/a/11…

乍一看标题，我们可能还不知道 ziplist 是何许人也。但是如果我说 list、hash、zset 这几种数据结构，大家就很熟悉了。而 ziplist 就是这几种数据结构的底层实现之一：

list：3.2.x 之前为（ziplist + linkedlist）之后为 quicklist

hash：数据量小的时候使用 ziplist，量大时使用 hashtable（dict）

zset：数据量小的时候使用 ziplist，量大时使用 skiplist

我们可以看到，ziplist 总是在一种列表、哈希、有序集合这几种结构在存储的数据量小的时会使用。随着数据量的增长，会转换到相对应较复杂的类型。我们可以猜测，ziplist 是一种轻巧、简单、且占用内存小的数据结构。它能够解决在 redis 数据量小时的存储问题。

在 redis 的设计思想中，大多数情况下，都是以 时间换空间 。由于 redis 基于内存，且内存资源是相当宝贵的，所以节省空间的“性价比”相对于节省时间，显然更高一些。在学习数据结构与算法的过程中，我们常常将数组和链表放在一起比较。由于数组使用一块连续的内存，而链表分为指针域和数据域， 数组在空间利用率上明显要高于链表。参考以上设计思想，如果让我们自己去设计 ziplist 的结构，我们如何思考呢？

需要一块连续的内存空间去存储真正的数据

需要一些额外的信息字段去记录它的长度、结束标志、还有数据的总量等辅助信息

在 ziplist 中，是按照如下结构进行存储的，是否符合你的预期呢？

每个字段的含义如下：

zlbytes：4 个字节。记录压缩列表总共占用的字节数，在对压缩列表进行内存重分配时使用

zltail：4 个字节。可通过这个字段快速定位到链表末尾

zllen：2 个字节。记录总共有多少个 entry

entry：具体数据的内容就存在这里

zlend：1 个字节。为十六进制值 0xFF，标记一个压缩列表的末尾

具体的数据存放在 entry 中。在 ziplist 中，可以存储两种数据：

字符串（字节数组）

整数

举一个例子，一个 zset 在数据量少的情况下，会将元素名和分值按 从小到大 的顺序在 ziplist 的 entry 中连续存储：

那么问题来了，我们在读取数据的时候，我们怎么知道是应该按照读取字符串还是整数类型的方式去读取呢？我们需要知道当前 entry 存储数据的类型，即一个 encoding 字段，用来标识当前 entry 数据的类型。
除此之外，我们在查找一个元素的时候，需要对其进行遍历，在 ziplist 中是如何遍历的呢？回想我们在数组中的遍历方式：

普通数组的遍历是根据数组里存储的 数据类型 来找到下一个元素的，例如 int 类型的数组（也是指针）访问下一个元素时每次只需要加上相应类型的指针偏移量即可（如果用下标法表示数组，p[0]到 p[1]就等效于 p +1*sizeof(int)这个过程；如果用指针法，可以用 p + 1 来表示，它也等效于 p +1*sizeof(int)）

那么在 ziplist 中，我们不知道数据类型，也不知道这个数据的长度，该如何将遍历用的指针往后挪呢？这就需要一个字段去完成这个任务，这里就是 previous_entry_length，它记录前一个 entry 的长度，可以利用它完成压缩列表的遍历
最后，就是最重要的字段，即存储真正数据的字段 content
以我们上图的例子，继续我们画出 entry 的结构：

previous_entry_length：记录了压缩列表中 前一个 entry 的长度 。占用1 或5字节

encoding：表示当前 entry 存储数据的类型与数据的长度。占用 1、2 或 5 字节

content：真正 存储数据 的地方

正向遍历 ziplist：首先指针 p 在第一个 entry 的起始位置，即 previous_entry_length 字段的位置。由于 previous_entry_length 可能占用 1 个字节、也可能占用 5 个字节，所以我们需要知道如何区分这个字段占用了 1 还是 5 字节。表示方法如下：

如果前一个 entry 的长度小于 254 字节时，previous_entry_length 用 1 字节表示

如果前一个 entry 的长度大于等于 254 字节时，previous_entry_length 用 5 字节表示。注意此时第一个字节是固定的标志 0xFE（254），后面 4 个字节用来表示前一个 entry 的长度

这样一来，我们就能够知道：由于我们当前的指针为 unsigned char * 类型（见源码），指针运算 p + 1 就等于往后偏移 1 个字节（即 8 位）。所以只需要读取当前指针的第一个字节的内容，即 p[0]的值是否在二进制的 00000000 ~ 11111110（即 0~254）之间。如果在这个区间内，就说明 previous_entry_length 只占用 1 个字节，使用 p + 1 就能够得到 encoding 的首地址了；如果 p[0]的值为 11111111（255），说明 previous_entry_length 占用了 5 个字节，使用 p + 5 也能够得到 encoding 的首地址。
现在我们的指针来到了 encoding 字段起始地址的位置。那么，encoding 字段是如何存储数据类型和长度的呢？为了节省 encoding 字段所占用的内存空间，将所有字符数组（字符串）类型以及整数类型按照如下编码方式区分：

观察上图 encoding 的编码方式，我们发现，只需要读取当前指针位置往后偏移两位的内容，就能够得到 encoding 字段的长度。（00、11 占用 1 字节；01 占用 2 字节；10 占用 5 字节）。那么我们相应的 p +1、p+2、p+ 5 即可将指针偏移到 content 的位置。
由于我们在 encoding 字段中知道 content 字段的数据类型的长度（如 int16 等）再将指针往后偏移之前 encoding 字段中存储的的相应数据类型长度，就可以偏移到 content 字段的末尾了。后面如果有多个同样的 entry 结构，也同理，这样就成功实现了 ziplist 的正序遍历。

由于 previous_entry_length 字段的存在，我们首先取出外部 zltail 字段，也就是指向 ziplist 结构末尾的指针，然后一次又一次地将指针减去 entry 中 previous_entry_length 字段的值，就能够将指针偏移到 ziplist 的头部，原理很简单，相信大家都能够理解，不再赘述。所以我们能够发现，ziplist 更适合从后往前遍历。

其实 ziplist 就是借鉴了数组的思想，skiplist 借鉴了链表的思想。不管是正向还是反向遍历，还是在 ziplist 的插入或者删除中需要将后面的元素往后挪或者往前挪，所有操作的复杂度均为 O(n)。比起 zset 的另一种实现 dict+skiplist 中查询 O(1)的时间复杂度，还有插入以及删除的 O(logn)复杂度，它在效率方面并没有优势。但是之前讲过，redis 的设计思想一般都是以时间换空间，所以，相比 skiplist 需要维护大量的指针、在多层上面重复的数据（skiplist 占用的空间为 2n，详情请看上一篇笔记），ziplist 在空间复杂度的使用上优势尽显。
但是我们不得不说，ziplist 在时间复杂度上面的劣势依然存在，所以我们不能把劣势无限放大开来，而是要扬长避短。所以，redis 开发者也反复权衡，考虑到了这一点。就拿 zset 来说，只有符合如下两个条件，才会使用 ziplist 编码，否则使用 skiplist 进行编码：

zset 中的对象保存的元素数量不超过 128 个

zset 中保存的所有元素成员的长度小于 64 字节

这样一来，由于 ziplist 只处理少量、且规模很小的数据，这使得时间复杂度 O(n)在 ziplist 处理少量数据的时候，这个 n 是非常小的。所以，这样就能够将其时间复杂度的影响降到了最低，将其空间复杂度的优势发挥到最大，这就是为什么需要进行编码转换的根本原因。

至于 ziplist 的关键之处就讲完了。至于其增删改查的具体源码，有兴趣的读者可以去 ziplist.c 中深入查看，笔者在这篇文章里再复制粘贴一次意义也不大。学习的过程中，我阅读了大量的资料，但是内容质量参差不齐。这里我想说，我们在学习一种新知识的时候，不仅仅要知道它是什么样子，也要知道它为什么是这样的、为什么这么做而不采用其它的替代方案？它的比较优势在哪里？而不要简单的堆砌概念。在学习的同时，如果没有经过自己的思考，收效甚微。

Redis5源码学习20190417-压缩列表ziplist

为什么需要 ziplist

ziplist 的结构

ziplist 的遍历

正向遍历

反向遍历

redis 编码转换的根本原因

站内搜索