Redis quickList

在使用 ENCODING 查看 list 编码时，返回的不是 ziplist，而是 quicklist。

《Redis 设计与实现》是基于 redis2.9 来编写的。而quicklist结构是在redis 3.2版本中新加的数据结构，用在列表的底层实现。

quicklist结构在quicklist.c中的解释为A doubly linked list of ziplists意思为一个由ziplist组成的双向链表。

1、quicklist 构成

表头结构

typedef struct quicklist {
    //指向头部(最左边)quicklist节点的指针
    quicklistNode *head;

    //指向尾部(最右边)quicklist节点的指针
    quicklistNode *tail;

    //ziplist中的entry节点计数器
    /* total count of all entries in all ziplists */
    unsigned long count;        

    //quicklist的quicklistNode节点计数器
     /* number of quicklistNodes */
    unsigned int len;          

    //保存ziplist的大小，配置文件设定，占16bits
    /* fill factor for individual nodes */
    int fill : 16;            

    //保存压缩程度值，配置文件设定，占16bits，0表示不压缩
    /* depth of end nodes not to compress;0=off */
    unsigned int compress : 16; 
} quicklist;

节点结构：

typedef struct quicklistNode {
    struct quicklistNode *prev;     //前驱节点指针
    struct quicklistNode *next;     //后继节点指针

    //不设置压缩数据参数recompress时指向一个ziplist结构
    //设置压缩数据参数recompress指向quicklistLZF结构
    unsigned char *zl;

    //压缩列表ziplist的总长度
    unsigned int sz;                 

    //ziplist中包的节点数，占16 bits长度
    unsigned int count : 16;          

    //表示是否采用了LZF压缩算法压缩quicklist节点，
    //1表示压缩过，2表示没压缩，占2 bits长度
    unsigned int encoding : 2;        

    //表示一个quicklistNode节点是否采用ziplist结构保存数据，
    //2表示压缩了，1表示没压缩，默认是2，占2bits长度
    unsigned int container : 2;        

    //标记quicklist节点的ziplist之前是否被解压缩过，占1bit长度
    //如果recompress为1，则等待被再次压缩
    unsigned int recompress : 1; /* was this node previous compressed? */

    //测试时使用
    unsigned int attempted_compress : 1; /* node can't compress; too small */

    //额外扩展位，占10bits长度
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quicklistEntry:

// 表示quicklist节点中ziplist里的一个节点结构
typedef struct quicklistEntry {
    const quicklist *quicklist;  // 指向所在quicklist的指针
    quicklistNode *node;  // 指向当前节点的指针
    unsigned char *zi;  // 指向当前节点的ziplist
    unsigned char *value;  // 当前指向的ziplist中的节点的字符串值
    long long longval;  // 当前指向的ziplist中的节点的整型值
    unsigned int sz;  // 当前指向的ziplist中的节点的字节大小
    int offset;  // 当前指向的ziplist中的节点相对于ziplist的偏移量
} quicklistEntry;

2、quicklist 特点：

quicklist是由ziplist组成的双向链表，一个 quicklist 有若干个节点，每个节点中都是一个 ziplist，通过 ziplist 来保存数据，而一个 ziplist 有若干个 entry 节点来保存数据。

因此一个 quicklist 节点保存的是一片数据，不是一个数据。

• 进行插入和删除操作时非常方便，复杂度为 O(N)，但是不需要每次都进行内存复制，提高了效率，两端访问复杂度为 O(1)
• quicklist微观上是一片片entry节点，每一片entry节点内存连续且顺序存储，可以通过二分查找以 log2(n)log2(n) 的复杂度进行定位

PUSH操作

quicklist最重要的操作就是首尾插入节点，此操作由quicklistPush函数实现。PUSH操作不管是头部还是尾部压入都包含两个步骤：

• 如果插入节点中的ziplist大小没有超过限制（list-max-ziplist-size），那么直接调用ziplistPush函数压入
• 如果插入节点中的ziplist大小超过了限制，则新建一个quicklist节点（自然会创建一个新的ziplist），新的数据项会压入到新的ziplist，新的quicklist节点插入到原有的quicklist上