6、Redis系统-数据结构-07-QuickList

七、快速列表（QuickList）

快速列表（QuickList）是 Redis 中用于实现列表（List）类型的一种高效数据结构。它结合了双向链表和压缩列表的优点，既支持高效的顺序访问，又能有效节省内存。

1. 结构设计

快速列表的基本思想是将多个压缩列表（ziplist）节点连接成一个双向链表。每个快速列表节点包含一个压缩列表，快速列表节点通过双向链表连接在一起。这样，快速列表既能利用压缩列表的内存紧凑性，又能利用链表的高效插入和删除操作。

typedef struct quicklist {
    quicklistNode *head;      // 快速列表头节点
    quicklistNode *tail;      // 快速列表尾节点
    unsigned long count;      // 快速列表中的元素总数量
    unsigned long len;        // 快速列表中的节点数量
    int fill : QL_FILL_BITS;  // 节点的填充因子
    unsigned int compress : QL_COMP_BITS;  // 压缩深度
    quicklistBookmark bookmarks[];  // 书签，用于快速定位
} quicklist;

快速列表的结构

1. 快速列表（quicklist）：快速列表结构包含指向头节点和尾节点的指针、元素总数量、节点数量、节点填充因子和压缩深度等。
2. 快速列表节点（quicklistNode）：每个节点包含前后指针、压缩列表指针、压缩列表大小、节点中元素数量等。

typedef struct quicklistNode {
    struct quicklistNode *prev;   // 前一个节点
    struct quicklistNode *next;   // 后一个节点
    unsigned char *zl;            // 压缩列表指针
    unsigned int sz;              // 压缩列表大小
    unsigned int count : 16;      // 节点中元素数量
    unsigned int encoding : 2;    // 编码类型
    unsigned int container : 2;   // 容器类型
    unsigned int recompress : 1;  // 重新压缩标志
    unsigned int attempted_compress : 1;  // 尝试压缩标志
    unsigned int extra : 10;      // 额外空间
} quicklistNode;

节点的设计

• prev 和 next：分别指向前一个节点和后一个节点，实现双向链表结构。
• zl：指向实际存储数据的压缩列表。
• sz：压缩列表的大小。
• count：节点中包含的元素数量。

2. 快速列表的优点

1. 内存紧凑：快速列表通过使用压缩列表来存储数据，减少了内存碎片，提高了内存利用率。
2. 高效操作：快速列表支持在列表两端进行高效的插入和删除操作，适用于需要频繁操作的场景。
3. 灵活性：通过双向链表结构，快速列表可以在需要时扩展或压缩，适应不同大小的数据集。

3. 操作原理

插入操作

插入新元素时，首先找到合适的节点（通常是头节点或尾节点），然后将新元素插入到节点的压缩列表中。如果当前节点已满，则创建一个新的节点，并将元素插入到新节点中。这样可以保证插入操作的高效性。

• 在头部插入：新元素插入到头节点的压缩列表中，如果头节点满了，则创建一个新的头节点。
• 在尾部插入：新元素插入到尾节点的压缩列表中，如果尾节点满了，则创建一个新的尾节点。

删除操作

删除元素时，首先找到包含该元素的节点，然后在压缩列表中删除元素。如果节点变为空节点，则将节点从快速列表中移除。这样可以保证删除操作的高效性。

• 删除头部元素：从头节点的压缩列表中删除元素，如果头节点空了，则移除头节点。
• 删除尾部元素：从尾节点的压缩列表中删除元素，如果尾节点空了，则移除尾节点。

查找操作

查找元素时，通过遍历快速列表节点，查找包含目标元素的压缩列表，然后在压缩列表中查找目标元素。这样可以保证查找操作的高效性。

• 顺序查找：从头节点开始，依次遍历每个节点的压缩列表，直到找到目标元素。
• 逆序查找：从尾节点开始，依次遍历每个节点的压缩列表，直到找到目标元素。

4. 快速列表的优化策略

压缩和填充因子

快速列表的填充因子用于控制每个压缩列表节点的大小。合理设置填充因子可以平衡内存利用率和操作性能。填充因子越大，每个节点包含的元素越多，内存利用率越高，但插入和删除操作的性能可能会下降；填充因子越小，每个节点包含的元素越少，插入和删除操作的性能越高，但内存利用率可能会下降。

压缩深度

快速列表的压缩深度用于控制数据压缩的程度。合理设置压缩深度可以进一步节省内存。压缩深度越大，压缩列表节点之间的数据压缩程度越高，内存利用率越高，但解压缩操作的开销可能会增加；压缩深度越小，压缩列表节点之间的数据压缩程度越低，解压缩操作的开销较小，但内存利用率可能会下降。

5. 使用示例

以下是一些使用 Redis 快速列表的示例，展示了如何利用快速列表进行数据的存储和操作。

插入数据

LPUSH mylist "hello"
LPUSH mylist "world"
RPUSH mylist "foo"
RPUSH mylist "bar"

获取数据

LRANGE mylist 0 -1
# 1) "world"
# 2) "hello"
# 3) "foo"
# 4) "bar"

删除数据

LPOP mylist
# "world"

RPOP mylist
# "bar"

LRANGE mylist 0 -1
# 1) "hello"
# 2) "foo"

结论

通过上述解析，我们可以更好地理解快速列表的设计思想和实现原理，从而在实际开发中更好地利用快速列表提供的优势。在 Redis 中，快速列表通过结合双向链表和压缩列表的优点，实现了高效的存储和操作，适用于需要频繁插入、删除和查找的场景。了解快速列表的内部实现，可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。