Redis中的快表（QuickList）是一种特殊的数据结构，用于存储一系列的连续节点，每个节点可以是一个整数或一个字节数组。快表是Redis中的底层数据结构之一，常用于存储有序集合（Sorted Set）等数据类型的底层实现。在本文中，我们将深入了解Redis中的快表，包括快表的结构和操作等。

1. 快表的结构

Redis中的快表（QuickList）是由多个节点（Node）组成的双向链表，每个节点都是一个ziplist（压缩列表）。快表中的每个节点包含了多个元素，每个元素可以是一个整数或一个字节数组。快表的结构如下图所示：

+---------+---------+---------+-------+
|  ziplist|  ziplist|  ziplist|  ...  |
+---------+---------+---------+-------+
|  prev   |  next   |  len    |  len  |
+---------+---------+---------+-------+
|  ...    |  ...    |  ...    |  ...  |
+---------+---------+---------+-------+

其中，ziplist是压缩列表，prev和next是指向前一个节点和后一个节点的指针，len是当前节点中元素的个数。

两端各有2个橙黄色的节点，是没有被压缩的。它们的数据指针zl指向真正的ziplist。中间的其它节点是被压缩过的，它们的数据指针zl指向被压缩后的ziplist结构，即一个quicklistLZF结构。
左侧头节点上的ziplist里有2项数据，右侧尾节点上的ziplist里有1项数据，中间其它节点上的ziplist里都有3项数据（包括压缩的节点内部）。这表示在表的两端执行过多次push和pop操作后的一个状态。
现在我们来大概计算一下quicklistNode结构中的count字段这16bit是否够用。

1.1 推导

我们已经知道，ziplist大小受到list-max-ziplist-size参数的限制。按照正值和负值有两种情况：

当这个参数取正值的时候，就是恰好表示一个quicklistNode结构中zl所指向的ziplist所包含的数据项的最大值。list-max-ziplist-size参数是由quicklist结构的fill字段来存储的，而fill字段是16bit，所以它所能表达的值能够用16bit来表示。
当这个参数取负值的时候，能够表示的ziplist最大长度是64 Kb。而ziplist中每一个数据项，最少需要2个字节来表示：1个字节的prevrawlen，1个字节的data（len字段和data合二为一；详见上一篇）。所以，ziplist中数据项的个数不会超过32 K，用16bit来表达足够了。

实际上，在目前的quicklist的实现中，ziplist的大小还会受到另外的限制，根本不会达到这里所分析的最大值。
在快表中，每个节点的大小是固定的。因此，当节点中的元素数量增加时，需要动态地添加新的节点来存储数据，这样可以保持快表的高效性。

2. 快表的操作

Redis中的快表支持以下常用的操作：

• 快表的创建

quicklist *ql = quicklistNew();

• 快表的添加

quicklistPushTail(ql, s, len);

其中，s是一个字节数组，len是字节数组的长度，表示在快表的尾部添加一个字节数组元素。

quicklistPushTail(ql, &value, sizeof(value));

其中，value是一个整数，表示在快表的尾部添加一个整数元素。

• 快表的删除

quicklistDelIndex(ql, node, index);

其中，node是指向要删除的节点的指针，index是节点中要删除元素的下标。

• 快表的遍历

for (quicklistNode *node = ql->head; node; node = node->next) {
   
   
    unsigned char *data = NULL;
    unsigned int sz;
    long long val;
    int ret = quicklistGet(node, &data, &sz, &val);
    if (ret == -1) {
   
   
        printf("data: %s, size: %d\n", data, sz);
    } else {
   
   
        printf("value: %lld\n", val);
    }
}

其中，node是指向当前节点的指针，data是节点中的字节数组元素，sz是字节数组元素的长度，val是节点中的整数元素。

• 快表的长度

unsigned long quicklistCount(const quicklist *ql);

以上是常用的快表操作，还有其他的操作可以参考Redis源代码中的quicklist.h和quicklist.c文件。

3. 快表的优缺点

3.1 优点：

• 快表的节点大小固定，可以有效地避免内存碎片的发生。
• 快表支持动态增加和删除节点，可以随着数据的增长而自动扩容或缩容，不需要预先分配空间。
• 快表的节点采用ziplist的紧凑存储方式，使得节点访问和遍历的效率较高。同时，快表支持从头和尾部两个方向同时遍历节点。

3.2 缺点：

• 快表的节点大小固定，如果节点中的元素数量较少，会造成一定的空间浪费。
• 快表中的元素只能是整数或字节数组，不支持其他数据类型的存储。
• 快表的插入和删除操作的效率较低，因为在插入或删除元素时，需要移动后面的元素，可能会导致大量的内存复制操作。如果需要频繁进行插入和删除操作，建议使用其他数据结构，例如链表。
• 当快表中的元素数量较大时，遍历整个快表的效率也可能较低，因为快表是由多个节点组成的链表，需要依次遍历每个节点才能访问所有元素。

  4. 总结

  快表适合存储一些数量较少但有序的元素，例如有序集合（Sorted Set）中的成员和分值。在实际应用中，需要根据具体的业务场景选择合适的底层数据结构。