链表

在Redis的早期版本中，存储list列表结构时，如果元素少则使用压缩列表ziplist，否则使用双向链表linkedlist

// 链表节点

struct listNode<T> {

    listNode *prev;

    listNode *next;

    T value;

} listNode；

​

// 链表

struct list {

    listNode *head; // 表头指针

    listNode *tail; // 表尾指针

    long len;       // 链表长度

} list;

对于链表，有以下特性：

• 双端：节点带有prev和next指针以获取前置、后置节点

• 无环：表头的prev和表尾的tail指向NULL

• 带表头表尾指针：获取表头表尾节点复杂度为O(1)

• 带链表长度计数器：获取节点数复杂度为O(1)

• 多态：使用void*来保存节点值，可保存不同类型值

快速列表

使用链表的附加空间相对太高，因为64bit系统中指针是8个字节，所以prev和next指针需要占据16个字节，且链表节点在内存中单独分配，会加剧内存的碎片化，影响内存管理效率。

考虑到链表的以上缺点，Redis后续版本对列表数据结构进行改造，使用quicklist代替了ziplist和linkedlist。

// 快速列表节点

struct quicklistNode {

    quicklistNode *prev;

    quicklistNode *next;

    ziplist *zl;         // 指向压缩列表

    int32 size;          // ziplist字节总数

    int16 count;         // ziplist中元素数量

    int2 encoding;       // 存储形式，表示原生字节数组还是LZF压缩存储

    ...

} quicklistNode；

​

// 快速列表

struct quicklist {

    quicklistNode *head;

    quicklistNode *next;

    long count;           // 元素总数

    int nodes;            // ziplist节点个数

    int compressDepth;    // LZF算法压缩深度

}

quicklist;

从代码可以看出，quicklist实际上是ziplist和linkedlist的混合体，它将linkedlist按段进行切分，每一段使用ziplist进行紧凑存储，多个ziplist之间使用双向指针进行串接。

quicklist内部默认单个ziplist长度为8k字节，超出这个字节数就会新起一个ziplist进行存储。

在quicklist内部，为进一步节约空间，还会使用LZF算法对ziplist进行压缩存储。

默认情况下，quicklist压缩深度为0即不压缩，实际压缩深度由配置中的list-compress-depth决定。

为支持快速pop/push，quicklist首尾两个ziplist不进行压缩，此时压缩深度为1，深度为2就表示首尾第一个和第二个ziplist都不进行压缩。