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

时间:2024-07-08 09:17:37

七、快速列表(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 的性能和功能。