[数据结构与算法]Redis常用数据结构和存储结构-List

3. List

存储类型

List用来存储有序的字符串，元素可以重复，一个列表对象最多可以存储2^32 - 1个元素。

存储结构

• 早期版本中，数据量较小时使用ziplist存储，达到临界值时转换成linkedlist
• 因为双向链表占用的内存比压缩列表要多， 所以当创建新的列表键时， 列表会优先考虑使用压缩列表， 并且在有需要的时候， 才从压缩列表实现转换到双向链表实现。
• 3.2版本之后，统一使用quicklist来存储。quicklist存储了一个双向链表，每个节点都是一个ziplist，所以是quicklist和ziplist的结合体

ziplist

ziplist的数据结构主要包括两层，ziplist和zipEntry。

ziplist包括zip header、zip entry、zip end三个模块。

zip entry由prevlen、encoding&length、value三部分组成。
prevlen主要是指前面zipEntry的长度，coding&length是指编码字段长度和实际- 存储value的长-
度，value是指真正的内容。 每个key/value存储结果中key用一个zipEntry存储，value用一个zipEntry存储。
每当有新的键值对加入到压缩列表时，程序会先将保存了键的压缩列表节点推入到压缩列表的表尾，然后再将保存了值的压缩列表节点推入到表尾。因此，保存了同一键值对的两个节点总是挨在一起。保存键的节点在前，保存值的节点在后。先添加到压缩列表的键值对放在表头方向，而后来添加的键值对放在表尾方向。

linkedlist

linkedlist是一个双向链表

quickedlist

quickList就是一个标准的双向链表的配置，有head 有tail;
每一个节点是一个quicklistNode，包含prev和next指针。
每一个quicklistNode 包含 一个ziplist，*zp 压缩链表里存储键值。
所以quicklist是对ziplist进行一次封装，使用小块的ziplist来既保证了少使用内存，也保证了性能。

quickedlist代码结构

/* quicklistNode is a 32 byte struct describing a ziplist for a quicklist.
 * We use bit fields keep the quicklistNode at 32 bytes.
 * count: 16 bits, max 65536 (max zl bytes is 65k, so max count actually < 32k).
 * encoding: 2 bits, RAW=1, LZF=2.
 * container: 2 bits, NONE=1, ZIPLIST=2.
 * recompress: 1 bit, bool, true if node is temporarry decompressed for usage.
 * attempted_compress: 1 bit, boolean, used for verifying during testing.
 * extra: 12 bits, free for future use; pads out the remainder of 32 bits */
typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 压缩前ziplist 压缩后压缩的数据
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

/* quicklistLZF is a 4+N byte struct holding 'sz' followed by 'compressed'.
 * 'sz' is byte length of 'compressed' field.
 * 'compressed' is LZF data with total (compressed) length 'sz'
 * NOTE: uncompressed length is stored in quicklistNode->sz.
 * When quicklistNode->zl is compressed, node->zl points to a quicklistLZF */
typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

/* quicklist is a 32 byte struct (on 64-bit systems) describing a quicklist.
 * 'count' is the number of total entries.
 * 'len' is the number of quicklist nodes.
 * 'compress' is: -1 if compression disabled, otherwise it's the number
 *                of quicklistNodes to leave uncompressed at ends of quicklist.
 * 'fill' is the user-requested (or default) fill factor. */
typedef struct quicklist {
    quicklistNode *head; //头结点
    quicklistNode *tail; //尾节点
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned int len;           /* number of quicklistNodes */
    int fill : 16;              /* fill factor for individual nodes *///负数代表级别，正数代表个数
    unsigned int compress : 16; /* depth of end nodes not to compress;0=off *///压缩级别
} quicklist;

操作

应用场景

• 队列/栈
• 消息列表