[数据结构与算法]Redis数据结构

命令学习可以使用 在线redis环境。

数据类型

Redis 比较常见的数据结构有 string、list、hash、set、sorted set 等，但是 Redis 还有比较高级的3种数据结构：HyperLogLog、Geo、BloomFilter。

String（字符串）

String 是 Redis 最简单最常用的数据结构，也是 Memcached 唯一的数据结构。在平时的开发中，String 可以说是使用最频繁的了。

底层实现：

• 如果一个字符串对象保存的是整数值， 并且这个整数值可以用 long 类型来表示， 那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面（将 void* 转换成 long ）， 并将字符串对象的编码设置为 int 。
• 如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度大于 39 字节， 那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串值， 并将对象的编码设置为 raw。
• 如果字符串对象保存的是一个字符串值， 并且这个字符串值的长度小于等于 39 字节， 那么字符串对象将使用 embstr 编码的方式来保存这个字符串值。

应用场景：

• 缓存功能：string 最常用的就是缓存功能，会将一些更新不频繁但是查询频繁的数据缓存起来，以此来减轻 DB 的压力。
• 计数器：可以用来计数，通过 incr 操作，如统计网站的访问量、文章访问量等。

List（列表）

基本概念:

list 是有序可重复列表，和 Java 的 LinkedList 比较像，可以通过索引查询；插入删除速度快。

底层实现：

Redis 3.2之前：

• 列表对象的编码可以是压缩列表 ziplist 或者 双向循环链表 linkedlist 。
• 列表对象保存的所有字符串元素的长度都小于 64 字节并且保存的元素数量小于 512 个，使用 ziplist 编码；否则使用 linkedlist；

Redis 3.2之后：
使用quicklist，它是一个双向链表，而且是一个基于ziplist的双向链表，quicklist的每个节点都是一个ziplist，结合了双向链表和ziplist的优点。

使用场景:

• 消息队列：Redis 的 list 是有序的列表结构，可以实现阻塞队列，使用左进右出的方式。Lpush 用来生产 从左侧插入数据，Brpop 用来消费，用来从右侧 阻塞的消费数据。
• 数据的分页展示： lrange 命令需要两个索引来获取数据，这个就可以用来实现分页，可以在代码中计算两个索引值，然后来 redis 中取数据。
• 可以用来实现粉丝列表以及最新消息排行等功能。

Hash（散列）

基本概念：

Redis 散列可以存储多个键值对之间的映射。和字符串一样，散列存储的值既可以是字符串又可以是数值，并且用户同样可以对散列存储的数字值执行自增或自减操作。这个和 Java 的 HashMap 很像，每个 HashMap 有自己的名字，同时可以存储多个 k/v 对。

底层实现:

• 哈希对象的编码可以是 ziplist 或者 hashtable 。
• 哈希对象保存的所有键值对的键和值的字符串长度都小于 64 字节并且保存的键值对数量小于 512 个，使用ziplist 编码；否则使用 hashtable；

应用场景：

• Hash 更适合存储结构化的数据，比如 Java 中的对象；其实 Java 中的对象也可以用 string 进行存储，只需要将 对象 序列化成 json 串就可以，但是如果这个对象的某个属性更新比较频繁的话，那么每次就需要重新将整个对象序列化存储，这样消耗开销比较大。可如果用 hash 来存储 对象的每个属性，那么每次只需要更新要更新的属性就可以。
• 购物车场景：可以以用户的 id 为 key ，商品的 id 为存储的 field ，商品数量为键值对的value，这样就构成了购物车的三个要素。

Set（集合）

基本概念：

Redis 的 set 和 list 都可以存储多个字符串，他们之间的不同之处在于，list是有序可重复，而set是无序不可重复。

底层实现：

• 集合对象的编码可以是 intset 或者 hashtable 。
• 如果集合对象保存的所有元素都是整数值并且保存的元素数量不超过 512 个，则使用 intset 编码；否则使用 hashtable；

应用场景：

• 标签：可以将博客网站每个人的标签用 set 集合存储，然后还按每个标签 将用户进行归并。
• 存储好友/粉丝：set 具有去重功能；还可以利用set并集功能得到共同好友之类的功能。

命令：

> sadd family mother          # 尝试将 mother 添加进 family 集合中
(integer)1       # 返回 1 表示添加成功，0 表示元素已经存在集合中
> sadd family father
(integer)1
> sadd family father
(intger)0
> smembers family             # 获取集合中所有的元素
1)"mother"
2)"father"
> sismember family father     # 判断 father 是否在 family 集合中 
(integer)1      # 1 存在；0 不存在
> sismber family son
(integer)0
> srem family son             # 移除 family 集合中元素 son
(integer)1     # 1 表示存在并且移除成功;0 表示存在该元素
> srem family som
(integer)0
> sadd family1 mother
(integer)1
> smembers family 
1)"mother"
2)"father"
> smember family1
1)"mother"
> sinter family family1     # 获取 family 和 family1 的交集
1)"mother"
> sadd family1 son
(integer)1
> sunion family family1     # 获取 family 和 family1 的并集
1)"mother"
2)"father"
> sdiff family family1      # 获取 family 和 family1 的差集（就是family有但是family1没有的元素）
1)"father"

zset（有序集合）

基本概念：

有序集合和散列一样，都用于存储键值对：其中有序集合的每个键称为成员（member），都是独一无二的，而有序集合的每个值称为分值（score），都必须是浮点数。可以根据分数进行排序，有序集合是Redis里面唯一既可以根据成员访问元素（这一点和散列一样），又可以根据分值以及分值的排列顺序来访问元素的结构。和Redis的其他结构一样，用户可以对有序集合执行添加、移除和获取等操作。

底层实现：

• 有序集合的编码可以是 ziplist 或者 skiplist
• 如果有序集合保存的元素数量小于 128 个并且保存的所有元素成员的长度都小于 64 字节，用 ziplist 编码；否则使用skiplist；
• 当ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的 ziplist 节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。
• 当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。

应用场景：

• 排行榜：有序集合最常用的场景。如新闻网站对热点新闻排序，比如根据点击量、点赞量等。
• 带权重的消息队列：重要的消息 score 大一些，普通消息 score 小一些，可以实现优先级高的任务先执行。

命令：

> zadd class 100 member1 # 将member1元素及其score值100加入到 有序集合 class中
(integer)1
> zadd class 90 member2 80 member3 # 批量添加
(integer)2
> zrange class 0 -1 withscores  # 获取有序集合中的值与score，并按 score 排序
1)"member3" 
2)"80"
3)"member2"
4)"90"
5)"member1"
6)"100"
> zrem class member1   # 删除 class 中 的member1
(integer)1

HyperLogLog

基本概念：

Redis 在 2.8.9 版本添加了 HyperLogLog 结构。

Redis HyperLogLog 是用来做基数统计的算法，HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基 数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。

但是，因为 HyperLogLog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 HyperLogLog 不能像集合那样，返回输入的各个元素。

应用场景：

可以用来统计网站的登陆人数以及其他指标

命令：

> pfadd user_login_20210523 tom #  user_login_20210523是key；tom 是登录的用户
(integer)1
> pfadd user_login_20210523 tom jack lilei 的用户
(integer)1
> pfcount user_login_20210523  # 获取 key 对应值的数量，同一个用户多次登录只统计一次
(integer) 3  
> pfadd user_login_20210522 sira 
(integer)1
> pfcount user_login_20210523 user_login_20210522 # 统计22号和23号一共有多少登陆的用户
(integer)4
> pfmerge user_login_20210522_23 user_login_20210522 user_login_20210523 # 将2个键内容合并
"OK"
> pfcount user_login_20210522_23
(integer)4

GEO

基本概念：

在 Redis 3.2 版本中新增了一种叫 geo 的数据结构，它主要用来存储地理位置信息，并对存储的信息进行操作。

应用场景：

用于存储地理信息以及对地理信息作操作的场景。

BloomFilter（布隆过滤器）

基本概念：

一种数据结构，是由一串很长的二进制向量组成，可以将其看成一个二进制数
组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。他的主要作用是：判断一个元素是否在某个集合中。
比如说，我想判断20亿的号码中是否存在某个号码，如果直接插DB，那么数据量太大时间会很慢；如果将20亿数据放到 缓存 中，缓存也装不下。这个时候用 布隆过滤器 最合适了.

数据结构

redis内部整体的存储结构是一个大字典，内部是数组实现的hash，key冲突通过挂链表去实现，每个dictEntry为一个key/value对象，value为定义的redisObject，即对象。

对象 redisObject

/*
 * Redis 对象
 */
typedef struct redisObject {
    // 类型 4bits
    unsigned type:4;
    // 编码方式 4bits
    unsigned encoding:4;
    // LRU 时间（相对于 server.lruclock） 24bits
    unsigned lru:22;
    // 引用计数 Redis里面的数据可以通过引用计数进行共享 32bits
    int refcount;
    // 指向对象的值 64-bit
    void *ptr;
} robj;

*ptr指向具体的数据结构的地址；type表示该对象的类型，即 String,List,Hash,Set,Zset 中的一个，但为了提高存储效率与程序执行效率，每种对象的底层数据结构实现都可能不止一种，encoding 表示对象底层所使用的编码。

redis对象底层的八种数据结构：

 REDIS_ENCODING_INT（long 类型的整数）
 REDIS_ENCODING_EMBSTR embstr （编码的简单动态字符串）
 REDIS_ENCODING_RAW （简单动态字符串）
 REDIS_ENCODING_HT （字典）
 REDIS_ENCODING_LINKEDLIST （双端链表）
 REDIS_ENCODING_ZIPLIST （压缩列表）
 REDIS_ENCODING_INTSET （整数集合）
 REDIS_ENCODING_SKIPLIST （跳跃表和字典）

对象类型与底层数据结构之间的关系：

简单动态字符串 SDS

SDS(simple dynamic string)

与C字符串对比

相比于C字符串的好处

减少内存重分配

为减少内存重分配次数，Redis SDS 实现了空间预分配和惰性空间释放两种策略。

空间预分配：

1. 如果sds修改后，sds长度（len的值）小于1mb，那么会分配与len相同大小的未使用空间，此时len与free值相同。例如，修改之后字符串长度为100字节，那么会给分配100字节的未使用空间。最终sds空间实际为 100 + 100 + 1(保存空字符’\0’)；
2. 如果大于等于1mb，每次给分配1mb未使用空间

惰性空间释放：
对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 free 属性将这些字节的数量记录下来，等待后续使用（sds也提供api，我们可以手动触发字符串缩短）；

链表

Redis 中的链表是双向循环链表

typedef struct listNode {

    // 前驱节点
    struct listNode *prev;

    // 后继节点
    struct listNode *next;

    // 值
    void *value;

} listNode;

typedef struct list {

    // 表头指针
    listNode *head;

    // 表尾指针
    listNode *tail;

    // 节点数量
    unsigned long len;

    // 复制函数
    void *(*dup)(void *ptr);
    // 释放函数
    void (*free)(void *ptr);
    // 比对函数
    int (*match)(void *ptr, void *key);
} list;

Redis 的链表实现的特性可以总结如下：

• 双端： 链表节点带有 prev 和 next 指针， 获取某个节点的前置节点和后置节点的复杂度都是 O(1) 。
• 无环： 表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL ， 对链表的访问以 NULL 为终点。
• 带表头指针和表尾指针： 通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1) 。
• 带链表长度计数器： 程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1) 。
• 多态： 链表节点使用 void* 指针来保存节点值， 并且可以通过 list 结构的 dup 、 free 、 match 三个属性为节点值设置类型特定函数， 所以链表可以用于保存各种不同类型的值。

总结：

• 链表被广泛用于实现 Redis 的各种功能， 比如列表键， 发布与订阅， 慢查询， 监视器， 等等。
• 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
• 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

字典 dict

Redis 的字典以及本身的数据库都是使用字典（dict）作为底层实现。

字典底层是使用哈希表（hashtable）作为底层实现。

dict 内部的数据结构：

typedef struct dict {
    dictType *type;
    // 私有数据
    void *privdata;
    // 2个哈希表
    dictht ht[2];
    // rehashing not in progress if rehashidx == -1 
    long rehashidx; 
    // number of iterators currently running
    int iterators;
} dict;

typedef struct dictht {
    // 指针数组，这个hash的桶
    dictEntry **table;
    // 元素个数
    unsigned long size;
    // 掩码，用于计算索引值。等于 size-1
    unsigned long sizemask;
    // 已有节点的数量
    unsigned long used;
} dictht;

dictEntry是用来真正存储key->value的地方
typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        // 指向具体redisObject
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

每个dict中都用两个hashtable。一般情况下只使用ht[0]，ht[1]只会在对ht[0] rehash时使用。

在dict扩容缩容的时候，需要分配新的hashtable，然后进行渐近式搬迁，这时候两个hashtable分别存储旧的hashtable和新的hashtable。搬迁结束后，旧hashtable删除，新的取而代之。

哈希算法

采用 Murmurhash 算法计算键的哈希值，优点在于即使键是有规律的，输出的值仍然有随机分布性；此外计算速度也很快。

计算出 hash 值后，通过与 sizemask 进行&操作获取在数组中的索引。

解决键冲突

采用链地址法解决键冲突，类似 JDK 1.7。

渐进式rehash

扩容和缩容都会通过rehash来实现。所谓渐进式rehash是指我们的大字典的扩容是比较消耗时间的，需要重新申请新的数组，然后将旧字典所有链表的元素重新挂接到新的数组下面，是一个O(n)的操作。但是因为我们的redis是单线程的，无法承受这样的耗时过程，所以采用了渐进式rehash小步搬迁，虽然慢一点，但是可以搬迁完毕。

步骤

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个hash表
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始
3. 在rehash进行期间，每次对字典执行添加，删除，查找或者更新操作时，程序除了执行特定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后，程序将rehashidx属性的值增1
4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成
5. 将ht[0]释放，然后将ht[1]设置成ht[0]，最后为ht[1]分配一个空白哈希表

rehash触发条件

扩容

我们的扩容一般会在Hash表中的元素个数等于第一维数组的长度的时候，就会开始扩容。扩容的大小是原数组的两倍。不过在redis在做bgsave（RDB持久化操作的过程）时，为了减少内存页的过多分离（Copy On Write），redis不会去扩容。

但是如果hash表的元素个数已经到达了第一维数组长度的5倍的时候，就会强制扩容，不管你是否在持久化。

缩容

当我们的hash表元素逐渐删除的越来越少的时候。redis就会对hash表进行缩容来减少第一维数组长度的空间占用。缩容的条件是元素个数低于数组长度的10%，并且缩容不考虑是否在做redis持久化。

不用考虑bgsave主要是因为我们的缩容的内存都是已经使用过的，缩容的时候可以直接置空，而且由于申请的内存比较小，同时会释放掉一些已经使用的内存，不会增大系统的压力。

跟JDK的HashMap的区别

• 数据结构上，采用了两个数组保存数据，发生hash冲突时，只采用了链地址法解决hash冲突，并没有跟jdk1.8一样当链表超过8时优化成红黑树，因此插入元素时跟jdk1.7的hashmap一样采用的是头插法。
• 在发生扩容时，跟jdk的hashmap一次性、集中式进行扩容不一样，采取的是渐进式的rehash，每次操作只会操作当前的元素，在当前数组中移除或者存放到新的数组中，直到老数组的元素彻底变成空表。
• 当负载因子小于0.1时，会自动进行缩容。jdk的hashmap出于性能考虑，不提供缩容的操作。
• redis使用MurmurHash来计算哈希表的键的hash值，而jdk的hashmap使用key.hashcode()的高十六位跟低十六位做与运算获得键的hash值。

跳表 skiplist

调表支持平均O(logN)，最坏O(N)复杂度的节点查找，还可以通过顺序性操作批量处理节点。

大部分情况下，跳表效率可以跟平衡树媲美。

Redis使用跳表作为zset的底层实现之一。当zset包含元素数量多，或者元素成员是比较长的字符串时，就会使用跳表。

/*

• 跳跃表
  */
  typedef struct zskiplist {
  // 头节点，尾节点
  struct zskiplistNode *header, *tail;
  // 节点数量
  unsigned long length;
  // 目前表内节点的最大层数
  int level;
  } zskiplist;

/*

• 跳跃表节点
  */
  typedef struct zskiplistNode {
  // member 对象
  robj *obj;
  // 分值
  double score;
  // 后退指针
  struct zskiplistNode *backward;
  // 层
  struct zskiplistLevel {
  // 前进指针
  struct zskiplistNode *forward;
  // 这个层跨越的节点数量
  unsigned int span;
  } level[];
  } zskiplistNode;

zskiplist结构：

• header:指向跳跃表的表头节点，通过这个指针程序定位表头节点的时间复杂度就为O(1)；
• tail:指向跳跃表的表尾节点,通过这个指针程序定位表尾节点的时间复杂度就为O(1)；
• level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)，通过这个属性可以再O(1)的时间复杂度内获取层高最好的节点的层数；
• length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)，通过这个属性，程序可以再O(1)的时间复杂度内返回跳跃表的长度。

zskiplistNode结构：

• 层(level):

节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。

每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离(跨度越大、距离越远)。在上图中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。

每次创建一个新跳跃表节点的时候,程序都根据幂次定律(powerlaw,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。

• 后退(backward)指针：
  节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。与前进指针所不同的是每个节点只有一个后退指针，因此每次只能后退一个节点。

• 分值(score):
  各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中,节点按各自所保存的分值从小到大排列。

• 成员对象(oj):
  各个节点中的o1、o2和o3是节点所保存的成员对象。在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)。

一些操作的时间复杂度

• 查询：O(logN)
• 插入：O(logN)
• 删除：O(logN)

为什么没有用红黑树替代跳表

• 在Redis中会有大量的范围查询的功能需求，红黑树在范围查找这方面的效率不如跳跃表，所以在范围查询方面使用跳跃表更优
• 红黑树的数据结构更为复杂，红黑树的插入和删除操作可能会引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速
• 一般来说，红黑树每个节点包含2个指针，而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。

整数集合 intset

Redis 的集合相当于Java中的 HashSet，它内部的键值对是无序、唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL。集合Set类型底层编码包括 hashtable 和 intset。

intset是一个有序集合，查找元素的复杂度为O(logN)（采用二分法）。但插入时不一定为O(logN)，因为有可能涉及到升级操作。比如当集合里全是int16_t型的整数，这时要插入一个int32_t，那么为了维持集合中数据类型的一致，那么所有的数据都会被转换成int32_t类型，涉及到内存的重新分配，这时插入的复杂度就为O(N)了。intset不支持降级操作。

typedef struct intset {
    uint32_t encoding;
    // length就是数组的实际长度
    uint32_t length;
    // contents 数组是实际保存元素的地方，数组中的元素有以下两个特性：
    // 1.没有重复元素
    // 2.元素在数组中从小到大排列
    int8_t contents[];
} intset;

// encoding 的值可以是以下三个常量的其中一个
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

压缩列表 ziplist

ziplist 是 List 和 Hash 类型的底层实现之一。

ziplist 可以看做是一种压缩的双向链表，它的好处是更能节省内存空间，因为它所存储的内容都是在连续的内存区域当中的。

当列表对象元素不大，每个元素也不大的时候，就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性，插入的复杂度是O(N)，即每次插入都会重新进行realloc。redisObject对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次，它们在内存中是一块连续的区域。

1、zlbytes：用于记录整个压缩列表占用的内存字节数
　
2、zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节
　
3、zllen：记录了压缩列表包含的节点数量。

4、entryX：压缩列表包含的各个节点

5、zlend：用于标记压缩列表的末端

为什么数据量大时不用ziplist？

因为ziplist是一段连续的内存，插入的时间复杂度为O(n)，而且每当插入新的元素需要 realloc 做内存扩展；而且如果超出ziplist内存大小，还会做重新分配的内存空间，并将内容复制到新的地址。如果数量大的话，重新分配内存和拷贝内存会消耗大量时间。所以不适合大型字符串，也不适合存储量多的元素。

快速列表 quickList

快速列表是ziplist和linkedlist的混合体，是将linkedlist按段切分，每一段用ziplist来紧凑存储，多个ziplist之间使用双向指针链接。

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;

• prev: 指向链表前一个节点的指针。
• next: 指向链表后一个节点的指针。
• zl: 数据指针。如果当前节点的数据没有压缩，那么它指向一个ziplist结构；否则，它指向一个quicklistLZF结构。
• sz: 表示zl指向的ziplist的总大小（包括zlbytes, zltail, zllen, zlend和各个数据项）。需要注意的是：如果ziplist被压缩了，那么这个sz的值仍然是压缩前的ziplist大小。
• count: 表示ziplist里面包含的数据项个数。这个字段只有16bit。稍后我们会一起计算一下这16bit是否够用。
• encoding: 表示ziplist是否压缩了（以及用了哪个压缩算法）。目前只有两种取值：2表示被压缩了（而且用的是LZF压缩算法），1表示没有压缩。
• container: 是一个预留字段。本来设计是用来表明一个quicklist节点下面是直接存数据，还是使用ziplist存数据，或者用其它的结构来存数据（用作一个数据容器，所以叫container）。但是，在目前的实现中，这个值是一个固定的值2，表示使用ziplist作为数据容器。
• recompress: 当我们使用类似lindex这样的命令查看了某一项本来压缩的数据时，需要把数据暂时解压，这时就设置recompress=1做一个标记，等有机会再把数据重新压缩。
• attempted_compress: 这个值只对Redis的自动化测试程序有用。我们不用管它。
• extra: 其它扩展字段。目前Redis的实现里也没用上。

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

quicklistLZF结构表示一个被压缩过的ziplist。其中：

• sz: 表示压缩后的ziplist大小。
• compressed: 是个柔性数组（flexible array member），存放压缩后的ziplist字节数组。

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

• head: 指向头节点（左侧第一个节点）的指针。
• tail: 指向尾节点（右侧第一个节点）的指针。
• count: 所有ziplist数据项的个数总和。
• len: quicklist节点的个数。
• fill: 16bit，ziplist大小设置，存放list-max-ziplist-size参数的值。
• compress: 16bit，节点压缩深度设置，存放list-compress-depth参数的值。

为什么不直接使用linkedlist？

linkedlist的附加空间相对太高，prev和next指针就要占去16个字节，而且每一个结点都是单独分配，会加剧内存的碎片化，影响内存管理效率。

参考

• https://mp.weixin.qq.com/s/7ct-mvSIaT3o4-tsMaKRWA
• http://redisbook.com/