连续连接上一篇文章：REDIS压缩列表Ziplist，内存优化的道路
本文指的是源代码版本仍然是REDIS6.2。
QuickList是Redis底部的Redis最重要的数据结构之一。它是Redis提供的六个基本数据结构中列表的基本实现，并在Redis 3.2版本中引入。
在介绍QuickList之前，REDIS使用了压缩的链接列表和双向链接列表（链接列表）作为列表的基础实现。
这样做的主要原因是，当元素的长度很小时，Ziplist的使用可以有效地节省存储空间，但是Ziplist的存储空间是连续的。当元素数量更多时，在修改元素时必须分配存储空间。这将无疑会影响Redis的执行效率，因此它使用了一般的两条链接列表。
QuickList是由时间效率和空间效率引入的一种新型数据结构。
REDIS源代码中QuickList的评论是Ziplists的双链接列表；也就是说，QuickList是由Ziplist组成的两条链接列表。每个链接列表节点是一个独立的Ziplist结构。
优化的关键是如何控制每个Ziplist的大小
因此，合理的配置参数非常重要，不同的方案可能需要不同的配置。REDIS提供列表 - Ziplist尺寸的尺寸参数，用于配置，默认-2，表明每个Ziplist节点不超过8KB的8KB
在
作为链接列表结构，QuickList是整个QuickList在数据结构中的头部和尾指针。这样，您可以快速通过QuickList的数据结构来快速找到linkedlist头和链接列表的链接列表。
填充用于指示每个QuickListNode中拉链长度的长度。当填充是一个正数时，它表明当填充为负时，每个Ziplist中包含的数据项数量为负：如下：下面：
当填充数负数时，它必须大于-5。。
在考虑QuickListNode节点的数量时，我们经常在两端访问数据。为了进一步节省空间，REDIS允许压缩到中间的QuickListNode节点。通过修改参数列表 - 压缩的特定含义是，两端都有压缩节点而没有压缩。
QuickList总体结构：
QuickListNode中的Ziplist中的节点
在：
QuickList中使用的迭代器：
QuickList每个节点的实际数据存储结构是Ziplist。该结构的主要优点是节省存储空间。
为了进一步减少Ziplist所占据的空间，Redis允许对Ziplist进行进一步的压缩。REDIS使用的压缩算法是LZF。压缩数据可以分为多个片段。每个片段有2个部分：
QuickListlzf结构：
LZF数据压缩的基本思想是：重复的数据，记录重复的位置和重复长度，否则将直接记录原始数据内容。
压缩算法的过程如下：遍历输入字符串，扩展了当前字符和背后的两个字符。如果显示在哈希表中的记录，请计算重复字节的长度和位置，否则数据是直接输出数据。
根据LZF压缩的数据格式，LZF可以更易于解压缩。应该注意的是，在某些情况下，可以将数据复制与当前位置重叠。例如，在当前位置前面的第15个字节上，重复20个字节。目前，您需要一个一个一个复制它们。
API定义：
其中，在进入之前或之后，使用后的参数用于插入。
由于QuickList使用链接的列表结构，因此在插入新元素时，QuickList将首先检查插入位置的Ziplist是否可以容纳该元素。这是_quicklistnodelowinsert函数的判断。
_quicklistNodealLowinsert函数将计算新插入的元素（new_sz）的大小。此大小等于QuickListNode的当前大小（节点 - > sz），插入的元素的大小以及插入元素后的Ziplist的流量。
计算大小后，_quicklistNodeAllowinsert函数将确定新插入的数据（SZ）是否又符合要求，也就是说，单个Ziplist不超过8KB，还是单个Ziplist中的元素数量是否满足要求。
只要满足一个条件，QuickList就可以在当前的QuickListNode中插入新元素，否则QuickList将创建一个新的QuickListNode来保留新插入的元素。
通过这种方式，QuickList使用每个QuickListNode中的元素的大小或数量，在Ziplist中添加或修改元素后，可以有效地减少链条更新，从而提供更好的访问性能。
QuickList提供了两个方案：删除单个元素和删除元素的间隔元素。
1）要删除单个元素，您可以使用QuickList Interface QuickListDelentry实现它。您也可以通过QuickListPop弹出头部或尾部元素。
QuickListDelentry函数调用基础QuickListDelIndex函数。此函数可以删除QuickListNode指向的Ziplist中的某个元素，其中P是指Ziplist中某个条目的起始位置。
QuickListPop可以弹出头部或尾部元素。特定的实现是通过Ziplist的接口获得元素值，然后通过上述QuickListDelindex删除数据。
2）对于删除间隔元素，QuickList提供了QuickListDelrange接口，该接口可以从指定位置从指定位置删除指定元素
启动是需要删除元素的起始位置，计数是需要删除的元素的数量。返回0表示没有删除元素。返回1并不意味着删除计数元素。由于计数可能大于QuickList的所有元素数量，因此它只能代表成功的操作。
总体删除逻辑是：无论哪种删除，它最终都会执行一个元素来通过Ziplist删除操作。首先尝试删除由链接列表节点指向的ziplist中的元素。如果Ziplist中的元素已经为空，则还删除了链接列表节点。
QuickList更改元素基于索引，主处理功能是QuickListrepLaceAtIndex。
它的基本思想是首先删除原始元素，然后插入新元素。QuickList不适合直接更改原始元素，这主要是因为其内部是Ziplist结构，并且Ziplist不断存储在内存中。更改其中一个元素时，它可能会影响后续元素。因此，QuickList首先使用删除的方案然后插入。
QuickList搜索元素主要用于索引，也就是说，通过链接列表中的元素的竞标找到相应的元素。基本思想是您首先找到与索引相对应的数据的QuickListNode节点，然后调用该节点ziplist接口函数ziplistget获取与索引相对应的数据。源代码中的处理函数为QuickListIndex。
IDX是需要找到的订户，结果被写入条目。返回0代表。1所发现的代表。在他们的境内，IDX可以是正面的或负面的，并且从背面找到了时代的时代。
遍历的逻辑相对简单。它仍然是链接列表 + Ziplist特征。区别在于，每个链接列表节点都有Ziplist元素的数量。因此，您可以快速找到目标链接列表节点，然后通过Ziplist的Ziplistget方法检查目标元素。
基于Ziplist中存在的问题，为了避免Ziplist列表过多问题，这是将大型拉链板分为一系列小型Ziplist的一种方法。
QuickList是由链接列表组成的结构，其中每个链接列表节点中都有一个Ziplist。它通过Ziplist进行了改进，完全使用了链接列表 + Ziplist特性
相关参考：