QuickList
简介
QuickList是一种结合了双向链表和Ziplist特性的数据结构，每个链表节点都是一个Ziplist。
具体实现
概述
QuickList可以理解为：链表节点元素为Ziplist的一个双向链表。一个包含4个节点的Quicklist，如果每个节点的Ziplist又包含3个数据项，那么对外表现上，这个list就总共包含12个数据项。结构如下图：
QuickList可以结合双向链表和Ziplist的优点，既不会有太大的内存开销，也方便进行两端的增删操作：
- 双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
- ziplist由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
节点元素限制
为了平衡内存使用和访问效率，避免单个Ziplist的元素数量过多，quicklist 对每个压缩列表节点中的entry数量进行了限制。可以通过配置参数 list-max-ziplist-size 来控制每个压缩列表节点中元素的最大数量。当一个压缩列表节点中的元素数量超过这个限制时，会创建一个新的Ziplist节点，并将其添加到双向链表中。
如果值为正，则代表ZipList的允许的entry个数的最大值
如果值为负，则代表ZipList的最大内存大小，分5种情况：
- -1：每个ZipList的内存占用不能超过4kb
- -2：每个ZipList的内存占用不能超过8kb
- -3：每个ZipList的内存占用不能超过16kb
- -4：每个ZipList的内存占用不能超过32kb
- -5：每个ZipList的内存占用不能超过64kb
其默认值为 -2
节点元素压缩
除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：
- 0：特殊值，代表不压缩
- 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
- 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
- 以此类推
总结
QuickList的特点：
- 是一个节点为ZipList的双端链表
- 节点采用ZipList，解决了传统链表的内存占用问题
- 控制了ZipList大小，解决连续内存空间申请效率问题
__END__
