baiyan完整视频：https://segmentfault.com/a/11...为什么我们需要ziplist乍一看，我们可能不知道什么是ziplist也是人。但是如果说到list、hash、zset这些数据结构，大家就会很熟悉了。而ziplist就是这些数据结构的底层实现之一：list：3.2.x之前（ziplist+linkedlist）然后是quicklisthash：数据量小的时候用ziplist，数据量大的时候用hashtable（dict）zset:数据量小的时候用ziplist，量大的时候用skiplist+hashtable。我们可以看到，在使用list、hash、orderedset的结构时，存储数据量较小时，总是使用ziplist。随着数据量的增长，它会被转换成相应更复杂的类型。我们可以猜测，ziplist是一个轻量级、简单、小内存的数据结构。可以解决redis数据量小的存储问题。ziplist的结构在redis的设计思路中。在大多数情况下，时间是用空间来交换的。由于redis是基于内存的，内存资源相当宝贵，节省空间的“性价比”明显高于节省时间。在学习数据结构和算法的过程中，我们经常会把数组和链表放在一起比较。由于数组使用的是连续内存，而链表分为指针域和数据域，数组的空间利用率明??显高于链表。参考上面的设计思路，如果让我们自己设计ziplist的结构，我们应该怎么想呢？需要一个连续的内存空间来存储真实的数据，还需要一些附加的信息域来记录它的长度、结束标志、数据总量等辅助信息。在ziplist中，按照如下结构存储。它适合你吗？期望？各字段含义如下：zlbytes：4字节。记录压缩列表占用的总字节数，在为压缩列表重新分配内存时使用zltail:4bytes。该字段可用于快速定位链表的末尾zllen：2字节。记录总共有多少个entryentry：具体数据的内容存在这里zlend:1byte。十六进制值0xFF标记压缩列表的结尾。具体数据存储在条目中。在ziplist中，可以存储两种数据：字符串（字节数组）和整型。例如，当一个zset数据量较小时，元素名和分数会在ziplist条目中按升序连续。存储：那么问题来了，当我们读取数据的时候，我们怎么知道是读取一个字符串还是一个整数呢？我们需要知道当前条目存储的数据类型，也就是一个编码字段来标识当前条目数据的类型。另外，我们在查找一个元素的时候，需要遍历它。如何在ziplist中遍历它？回想一下我们在数组中的遍历方法：普通数组的遍历是根据数组中存储的数据类型来查找下一个元素，比如int类型的数组（也是指针）只需要在每个元素上加上对应的类型即可访问下一个元素时指针偏移就够了（如果用下标方式表示数组，p[0]到p[1]相当于p+1*sizeof(int)的过程；如果指针方法，可以使用p+1也相当于p+1*sizeof(int))那么在ziplist中，我们不知道数据类型，也不知道数据的长度，如何将遍历指针移回？这就需要一个字段来完成这个任务，这里是previous_entry_length，它记录了前一个条目的长度，可以用来完成压缩列表的遍历。最后就是最重要的字段，也就是存放真实数据的字段内容。比如我们继续画出entry的结构：previous_entry_length：记录压缩列表中前一个entry的长度。Occupies1or5bytesencoding：表示当前表项存储的数据类型和长度。占用1、2或5个字节的内容：遍历实际存放数据的ziplist遍历是搜索操作的基础，遍历是学习任何数据结构的关键。正向遍历正向遍历ziplist：首先，指针p在第一个entry的起始位置，即previous_entry_length字段的位置。由于previous_entry_length可能占用1个字节或5个字节，我们需要知道如何区分这个字段是占用1个字节还是5个字节。表示方法如下：如果前一个条目的长度小于254字节，则previous_entry_length用1字节表示；如果前一个条目的长度大于等于254字节，则previous_entry_length用5个字节表示。注意第一个字节是固定标志0xFE（254），接下来的4个字节用来表示前一个条目的长度。这样我们就可以知道：由于我们当前的指针是unsignedchar*类型的（见源码），指针操作p+1相当于向后移1个字节（即8位）。所以只需要读取当前指针第一个字节的内容，即p[0]的值是否在二进制00000000~11111110（即0~254）之间。如果在这个范围内，说明previous_entry_length只占1个字节，使用p+1即可得到编码首地址；如果p[0]的值为11111111（255），说明previous_entry_length占5字节，使用p+5也可以得到编码的首地址。现在我们的指针位于编码字段的起始地址。那么，编码字段是如何存储数据类型和长度的呢？为了节省编码字段占用的内存空间，所有的字符数组（字符串）类型和整数类型都按照如下编码方式进行区分：观察上图中encoding的编码方式，我们发现我们只需要读取当前指针位置向后偏移两位的内容即可得到编码字段的长度。（00、11占1个字节；01占2个字节；10占5个字节）。那么我们对应的p+1、p+2、p+5就可以将指针偏移到content的位置。由于我们知道编码域中内容域的数据类型的长度（如int16等），然后将指针偏移回之前编码域中存储的对应数据类型的长度，我们就可以偏移到内容字段的末尾。如果后面有多个相同的entry结构，也是如此，这样就成功实现了ziplist的正序遍历。反向遍历由于previous_entry_length字段的存在，我们先取出外部的zltail字段，也就是指向ziplist结构末尾的指针，然后在entry中previous_entry_length字段的值中减去该指针，一遍又一遍将指针偏移到ziplist的头部，原理很简单，相信大家都能看懂，不再赘述。所以我们可以发现ziplist更适合从后向前遍历。redis编码转换的根本原因其实是ziplist借用了数组的思想，而skiplist借用了链表的思想。不管是正向遍历还是反向遍历，还是ziplist的插入删除，下面的元素都需要向后或者向前移动，所有操作的复杂度都是O(n)。与zset的另一种实现dict+skiplist的查询时间复杂度O(1)，插入删除的O(logn)复杂度相比，ziplist在效率上没有优势。但是我们之前说过，redis的设计思路一般都是用时间换空间。因此，相对于skiplist需要维护大量的指针和多层重复数据（skiplist占用的空间为2n，详见上一篇文章注释），ziplist在空间复杂度上显示出优势。但是不得不说ziplist在时间复杂度方面的劣势还是存在的，所以我们不能无限放大劣势，而是要扬长避短。因此，redis的开发者对此也进行了反复权衡和考虑。以zset为例，只有满足以下两个条件才会使用ziplist编码，否则使用skiplist编码：zset中对象存储的元素个数不超过128个，且所有元素成员的长度存储在zset中的是小于64字节这样，由于ziplist只处理小规模的少量数据，这使得ziplist在处理少量数据时的时间复杂度为O(n)，这个n很小。因此，这样一来，可以最大限度地减少其时间复杂度的影响，同时最大限度地发挥其空间复杂度的优势，这也是为什么需要进行编码转换的根本原因。至于ziplist的要点，就这些吧。至于其增删改查的具体源码，有兴趣的读者可以去ziplist。在学习的过程中，看了很多资料，但内容质量参差不齐。这里我想说的是，我们在学习一门新知识的时候，不仅要知道它长什么样子，还要知道为什么会这样，为什么要这样做而不是用其他的替代方法呢？它的比较优势在哪里？而不是简单地堆砌概念。在学习的过程中，如果自己不去思考，是收效甚微的。
