我们在使用Redis对外暴露的list数据结构时，给我们带来极大的便利性。其底层实现所依赖的内部数据结构就是quicklist。
我们先来回忆下list这种数据结构的特点：
表list是一个能维持数据项先后顺序的双向链表
在表list的两端追加和删除数据极为方便，时间复杂度为O(1)
表list也支持在任意中间位置的存取操作，时间复杂度为O(N)
表list经常被用作队列使用
本篇文章我们来讨论下quicklist，
先来看下Redis官方quicklist.c和quicklist.h对quicklist的描述
quicklist是一个ziplist的双向链表（双向链表是由多个节点Node组成的）。也就是说quicklist的每个节点都是一个ziplist。ziplist本身也是一个能维持数据项先后顺序的列表（按插入位置），而且是一个各个数据项在内存上前后相邻的列表。
一、quicklist结构定义
双向链表在表的两端进行push和pop操作十分的便节，但是它的内存开销比较大。
首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；
其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
ziplist由于是一整块连续内存，所以存储效率很高。
首先，它不利于修改操作，每次数据变动都会引发一次内存的realloc。
其次，当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
Redis基于空间和时间的考虑，于是quicklist结合双向链表和ziplist的优点。
注意点：
quicklistNode 中sz，如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
从上述的定义中，我们了解到quicklist 在64位系统中占用32字节的空间，quicklistNode 是一个32字节的结构。
上面提到了两个重要参数配置：
list-max-ziplist-size
1、list-max-ziplist-size取值，可以取正值，也可以取负值。
当取正值的时候，表示按照数据项个数来限定每个quicklist节点上的ziplist长度。比如，当这个参数配置成5的时候，表示每个quicklist节点的ziplist最多包含5个数据项。
当取负值的时候，表示按照占用字节数来限定每个quicklist节点上的ziplist长度。这时，它只能取-1到-5这五个值，每个值含义如下：
-5: 每个quicklist节点上的ziplist大小不能超过64 Kb。（注：1kb => 1024 bytes）
-4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
-3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
-2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（-2是Redis给出的默认值）
-1: 每个quicklist节点上的ziplist大小不能超过4 Kb。
2、list-max-ziplist-size配置产生的原因？
每个quicklist节点上的ziplist越短，则内存碎片越多。内存碎片多了，有可能在内存中产生很多无法被利用的小碎片，从而降低存储效率。这种情况的极端是每个quicklist节点上的ziplist只包含一个数据项，这就蜕化成一个普通的双向链表了。
每个quicklist节点上的ziplist越长，则为ziplist分配大块连续内存空间的难度就越大。有可能出现内存里有很多小块的空闲空间（它们加起来很多），但却找不到一块足够大的空闲空间分配给ziplist的情况。这同样会降低存储效率。这种情况的极端是整个quicklist只有一个节点，所有的数据项都分配在这仅有的一个节点的ziplist里面。这其实蜕化成一个ziplist了。
可见，一个quicklist节点上的ziplist要保持一个合理的长度。那到底多长合理呢？Redis提供了一个配置参数list-max-ziplist-size，就是为了让使用者可以来根据实际应用场景进行调整优化。
list-compress-depth
其表示一个quicklist两端不被压缩的节点个数。注：这里的节点个数是指quicklist双向链表的节点个数，而不是指ziplist里面的数据项个数。实际上，一个quicklist节点上的ziplist，如果被压缩，就是整体被压缩的。
1、list-compress-depth的取值：
0: 是个特殊值，表示都不压缩。这是Redis的默认值。
1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩。
3: 表示quicklist两端各有3个节点不压缩，中间的节点压缩。
依此类推…
由于0是个特殊值，很容易看出quicklist的头节点和尾节点总是不被压缩的，以便于在表的两端进行快速存取。
2、list-compress-depth配置产生原因？
当表list存储大量数据的时候，最容易被访问的很可能是两端的数据，中间的数据被访问的频率比较低（访问起来性能也很低）。如果应用场景符合这个特点，那么list还提供了一个选项，能够把中间的数据节点进行压缩，从而进一步节省内存空间。Redis的配置参数list-compress-depth就是用来完成这个设置的。
二、quicklist典型基本操作函数
当我们使用lpush或rpush等命令第一次向一个不存在的list里面插入数据的时候，Redis会首先调用quicklistCreate接口创建一个空的quicklist。
1、quicklist的创建
从上述代码中，我们看到quicklist是一个不包含空余头节点的双向链表（head和tail都初始化为NULL）。
2、quicklist的push操作
从上述的代码中，我们可以看到
不管是在头部还是尾部插入数据，都包含两种情况：
如果头节点（或尾节点）上ziplist大小没有超过限制（即
_quicklistNodeAllowInsert返回1），那么新数据被直接插入到ziplist中（调用ziplistPush）。如果头节点（或尾节点）上ziplist太大了，那么新创建一个quicklistNode节点（对应地也会新创建一个ziplist），然后把这个新创建的节点插入到quicklist双向链表中（调用
_quicklistInsertNodeAfter）。
3、quicklist的pop操作
quicklist的pop操作是调用quicklistPopCustom来实现的。
quicklistPopCustom的实现过程基本上跟quicklistPush相反：
首先，从头部或尾部节点的ziplist中把对应的数据项删除；
其次，如果在删除后ziplist为空了，那么对应的头部或尾部节点也要删除；
最后，删除后还可能涉及到里面节点的解压缩问题。
quicklist不仅实现了从头部或尾部插入，也实现了从任意指定的位置插入。quicklistInsertAfter和quicklistInsertBefore就是分别在指定位置后面和前面插入数据项。这种在任意指定位置插入数据的操作，情况比较复杂。
当插入位置所在的ziplist大小没有超过限制时，直接插入到ziplist中就好了
当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小没有超过限制，那么就转而插入到相邻的那个quicklist链表节点的ziplist中
当插入位置所在的ziplist大小超过了限制，但插入的位置位于ziplist两端，并且相邻的quicklist链表节点的ziplist大小也超过限制，这时需要新创建一个quicklist链表节点插入
对于插入位置所在的ziplist大小超过了限制的其它情况（主要对应于在ziplist中间插入数据的情况），则需要把当前ziplist分裂为两个节点，然后再其中一个节点上插入数据
三、总结
quicklist将双向链表和ziplist两者的优点结合起来，在时间和空间上做了一个均衡，能较大程度上提高Redis的效率。push和pop等操作操作的时间复杂度也都达到了最优。
--EOF--