redis 五种数据结构-list

list 链表 所以增加和删除的时间复杂度是O(1) 查找的时间复杂度是O(n)

list 常用命令有 lpush、rpush、lpop、rpop

list的实现原理

redis 3.2 之前是ziplist(压缩列表)和linkedlist(双端链表)

再选择存储结构的时候 会优先选择ziplist 当不满足条件时才会使用linkedlist

当同时满足以下两个条件的时候会使用ziplist，首先 list中的所有元素大小都小于64字节，list中的元素总量少于512个

ziplist 的结构

struct ziplist<T> {
	int32 zlbytes; // 整个压缩列表占用字节数
	int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
	int16 zllength; // 元素个数
	T[] entries; // 元素内容列表，挨个挨个紧凑存储
	int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

/* 
空白 ziplist 示例图

area        |<---- ziplist header ---->|<-- end -->|

size          4 bytes   4 bytes 2 bytes  1 byte
            +---------+--------+-------+-----------+
component   | zlbytes | zltail | zllen | zlend     |
            |         |        |       |           |
value       |  1011   |  1010  |   0   | 1111 1111 |
            +---------+--------+-------+-----------+
                                       ^
                                       |
                               ZIPLIST_ENTRY_HEAD
                                       &
address                        ZIPLIST_ENTRY_TAIL
                                       &
                               ZIPLIST_ENTRY_END

非空 ziplist 示例图

area        |<---- ziplist header ---->|<----------- entries ------------->|<-end->|

size          4 bytes  4 bytes  2 bytes    ?        ?        ?        ?     1 byte
            +---------+--------+-------+--------+--------+--------+--------+-------+
component   | zlbytes | zltail | zllen | entry1 | entry2 |  ...   | entryN | zlend |
            +---------+--------+-------+--------+--------+--------+--------+-------+
                                       ^                          ^        ^
address                                |                          |        |
                                ZIPLIST_ENTRY_HEAD                |   ZIPLIST_ENTRY_END
                                                                  |
                                                        ZIPLIST_ENTRY_TAIL
*/

entry的结构

struct entry {
	int<var> prevlen; // 前一个 entry 的字节长度
	int<var> encoding; // 元素类型编码方式和长度
	optional byte[] content; // 元素内容
}

prevlen 是一个变长的字段 当字符创长度小于254时 是1个字节，如果达到254 就使用5个字节表示，其中第一个字节固定为0xFE(十进制254) 后面4个字节用于表示长度

encodeing 包含content的编码方式和长度

linkedlist 双端链表的结构

/*
 * 双端链表节点
 */
typedef struct listNode {

    // 前置节点
    struct listNode *prev;

    // 后置节点
    struct listNode *next;

    // 节点的值
    void *value;

} listNode;

ziplist 是紧凑存储 所以每次增加元素都需要扩容，如果过大会消耗比较大，同时linkedlist 由于前后节点指针的存在 比较占用内存

redis 3.2 使用的是quicklist

quicklist 是linkedlist和ziplist的结合体， 将linkedlist分段存储，每一段使用ziplist存储，ziplist之间使用双向指针连接起来

quickListNode 结构

typedef struct quicklistNode {
    struct quicklistNode *prev; //上一个node节点
    struct quicklistNode *next; //下一个node
    unsigned char *zl;            //保存的数据 如果ziplist没有被压缩 指向一个ziplist结构  如果被压缩指向一个quicklistLZF 结构
    unsigned int sz;             /* ziplist size in bytes */  ziplist 的总大小
    unsigned int count : 16;     /* count of items in ziplist */  ziplist中的数据项个数
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */  表示ziplist是否被压缩以及使用哪种压缩算法   2 使用LZF压缩   1 没有压缩
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quickLZF 结构

typedef struct quicklistLZF {
    unsigned int sz; /* LZF size in bytes*/
    char compressed[];
} quicklistLZF;

quciklist 结构

typedef struct quicklist {
    quicklistNode *head;    指向头结点的指针
    quicklistNode *tail;    指向尾节点的指针
    unsigned long count;        /* total count of all entries in all ziplists */   所有ziplist数据项的总和
    unsigned long len;          /* number of quicklistNodes */ 
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */  ziplist大小设置，存放list-max-ziplist-size参数的值   
           -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。
           -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。
           -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。
           -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。（默认值）
           -1: 每个quicklist节点上的ziplist大小不能超过4 Kb
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ 节点压缩深度设置，存放list-compress-depth参数的值  
         0: 是个特殊值，表示都不压缩。这是Redis的默认值。
         1: 表示quicklist两端各有1个节点不压缩，中间的节点压缩。
         2: 表示quicklist两端各有2个节点不压缩，中间的节点压缩
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;