「这是我参与11月更文挑战的第4天，活动详情查看：2021最后一次更文挑战」

上一篇讲了ziplist的实现，同时也说了ziplist的一些不足。

文章地址：压缩列表实现

今天说一下ziplist的进化版quicklist。

快速列表结构（quicklist）

quicklist是结合了双向链表和ziplsit各自的优点，一个quicklist就是一个链表，但是链表的节点却是ziplist。

quicklistNode结构体定义

因为quicklist是一个链表，所以每个quicklistNode中都包含了指向前序和后序节点的指针prev和next。

同时每一个quicklistNode又是一个ziplist，所以又执行ziplist的指针zl

typedef struct quicklistNode {
    struct quicklistNode *prev;  // 指向上一个quicklistNode节点
    struct quicklistNode *next;  // 指向下一个quicklistNode节点
    unsigned char *zl;           // 数据指针，指向ziplist结构
    unsigned int sz;             // 表示指向ziplist结构的总长度(字节大小)
    unsigned int count : 16;     // 表示ziplist中的元素个数
    unsigned int encoding : 2;   // 编码方式，1--ziplist，2--quicklistLZF
    unsigned int container : 2;  // 存放数据的方式，1--NONE，2--ziplist
    unsigned int recompress : 1; // 时间是否被压缩
    unsigned int attempted_compress : 1; // 测试相关
    unsigned int extra : 10; // 扩展字段，暂时没用
} quicklistNode;
复制代码

quicklist定义

quicklist作为一个链表结构，同双向链表一样，定义了头、尾指针，可以快速定位到quicklist的链表头和链表尾。

此外，还定义了ziplist中的总元素个数，quicklistNode节点的个数等。

typedef struct quicklist {
    quicklistNode *head;        // 指向quicklist的头部
    quicklistNode *tail;        // 指向quicklist的尾部
    unsigned long count;        // 所有ziplist中的总元素的个数
    unsigned int len;           // quicklistNode节点的个数
    ...
} quicklist;
复制代码

quicklist解决了什么问题

正因为 quicklist 采用了链表结构，所以当插入一个新的元素时，quicklist 首先就会检查插入位置的 ziplist 是否能容纳该元素。即单个 ziplist 是否不超过 8KB（默认值），或是单个 ziplist 里的元素个数是否满足要求。

只要这里面的一个条件能满足，quicklist 就可以在当前的 quicklistNode 中插入新元素，否则 quicklist 就会新建一个 quicklistNode，以此来保存新插入的元素。

相比ziplist来说，quicklist缓解了ziplist因插入数据导致的连锁更新问题。

为什么说是缓解呢？通过上面的quicklistNode节点的结构就可以看出来，数据存储的不再是单个值，而是整个ziplist结构。

quicklist通过链表，把原本数据量很大的ziplist结构，分解成多个小的ziplist，这样在插入数据的时候，即使发生了连锁更新，也只会在单个quicklistNode节点发生。避免全部的ziplist都产生连锁更新。

quicklist宏观上是一个双向链表，因此，它具有一个双向链表的有点，进行插入或删除操作时非常方便，虽然复杂度为O(n)，但是不需要内存的复制，提高了效率，而且访问两端元素复杂度为O(1)。

quicklist微观上每一个quicklistNode节点内存连续且顺序存储，可以通过二分查找以 log2(n) 的复杂度进行定位。

今天的quicklist就这些。