【Redis】快速列表结构

1、背景

redis的quicklist（快速列表）是一个双向链表，其中每个节点都是一个ziplist（压缩列表）。这中结构结合了双向链表和压缩列表的优点，在内存使用和性能之间取得了平衡，接下来就来熟悉一下redis（6.2.18版本）的底层结构实现。

2、压缩列表

【1】底层结构

quicklist的底层结构如下：

typedef struct quicklist {quicklistNode *head; //指向头部节点quicklistNode *tail; //指向尾部节点unsigned long count; //所有ziplist中的条目总数unsigned long len; //quicklist节点数量int fill : QL_FILL_BITS; //单个ziplist的最大大小限制unsigned int compress : QL_COMP_BITS; //不压缩的节点深度unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist;typedef struct quicklistNode {struct quicklistNode *prev; //上一个节点指针struct quicklistNode *next; //下一个节点指针unsigned char *zl; //指向压缩列表的指针unsigned int sz; //ziplist的字节大小unsigned int count : 16; //ziplist中的条目数unsigned int encoding : 2;   /* RAW==1 or LZF==2 */unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */unsigned int recompress : 1; //是否被压缩过unsigned int attempted_compress : 1; /* node can't compress; too small */unsigned int extra : 10; //保留位
} quicklistNode;

向quicklist添加一个元素的时候，不会像普通的链表那样直接新建一个链表节点，而是会检查插入位置的压缩列表是否能够容纳该元素，如果能容纳就直接保存到quicklistNode结构里的压缩列表里，如果不能容纳，才会建一个新的quicklistNode结构。

【2】特性

quick的特性如下：

【3】优缺点