Redis数据结构（二）列表健底层实现—链表、压缩列表

列表健底层有两种实现，一种是链表，另一种为压缩列表（ziplist）。当列表对象可以同时满足以下两种情况的时候，列表对象将使用压缩列表实现

1. 列表对象保存的所有字符串元素的长度都小于64字节
2. 列表对象保存的元素数据库小雨512个

当不能同时满足这两个条件时就会使用链表实现。 下面我们具体聊聊这两种数据结构

（一）链表

  链表做为常用的数据结构，很多高级的编程语言里面都内置了该数据结构比如说java、python等。但是由于Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。
  链表节点的数据结构定义如下：

typedef struct listNode {// 前置节点    struct listNode *prev;    // 后置节点    struct listNode *next;    // 节点的值    void *value;} listNode;

如上面所示，链表节点采用prev与next指针组成了双端链表。而采用viod *这种无类型指针来保存节点的值，所以链表可以用于保存各种不同类型的数据。
当然，Redis也构建了自己的list结构，且封装了一些比较好用的函数，

• dup函数用于复制链表节点保存的值；
• free用于释放链表节点所保存的值；
• match函数用于对比链表节点所保存的值是否相等；

typedef struct list {// 表头节点    listNode *head;    // 表尾节点    listNode *tail;    // 节点复制函数    void *(*dup)(void *ptr);    // 节点释放函数    void (*free)(void *ptr);    // 节点值对比函数    int (*match)(void *ptr, void *key);    // 链表所包含的节点数量    unsigned long len;} list;

如上面所示，list结构为链表提供了表头指针head、表尾指针tail，以及链表长度的计数器len。

链表的特性如下：

• 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点复杂度都是0(1)
• 无环结构：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
• 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为0(1)。
• 带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，所以我们使用list获取节点数量的复杂度为0(1)。
• 多态：链表节点使用void*指针来保存节点值，且提供了几个封装好的函数。所以链表可以用与保存各种不同类型的值

（二）压缩链表

定义：
  列表是Redis为了节约内存而研发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。在Redis中压缩列表被用于列表健和哈希键的底层实现之一。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作。
  压缩列表结构图组成如下：

• zlbyte: 记录了整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配，或者计算zlend的位置时使用
• zltail: 记录了压缩列表表尾节点距离压缩列表的起始地址有多少字节。通过这个偏移量，就可以直接计算出表尾节点的位置。
• zllen: 记录了压缩列表包含的节点数量，当这个属性的值小于65535的时候，这个属性的值就是压缩列表包含的节点数量，等于的时候就需要重新遍历整个压缩列表才能得出。
• zlend: 特殊的值0xFF，用于标记压缩列表的末端。
• entry*: 压缩列表的节点，节点的长度由节点自己保存

压缩列表节点的构成：

我们来分别瞅瞅这几种类型：

• previous_entry_length
  这个部分以字节为单位以十进制的形式保存，记录压缩列表节点的长度。属性长度可以是1字节、5字节。逻辑如下：
  1⃣️当前一个节点的长度小于254字节，那么就是一个字节表示
  2⃣️如果前一个字节的长度大于等于254字节，那么previous_entry_length的属性的长度就为5字节，其中第一字节会被设置为0xFE(十进制254)，后面的四个字节就用于保存前一节点的长度

  当然这样存，在特定的情况下会出现非常消耗性能的连锁更新问题：
  如果在一个压缩列表中，有多个连续的，长度介于250字节到253字节之间的节点。如图所示
  
  当我们在entry1节点前加入一个前置节点entry0,大小为258字节。如图所示
  
  由于entry1保存前置节点的previous_entry_length仅有1字节，无法存储，需要扩展到5字节存储，但是这样就会使entry1的字节长度变化到253+5=258字节长度，这样，entry2的previous_entry_length又无法存储entry1的字节长度，又需要扩展到5字节存储，这样以此类推，程序需要不断的执行空间重分配操作。
  当然发生这种情况的机率很低，首先得列表里恰好要有多个连续的，长度介于250-253字节之间的节点，其次只要被更新的节点数量不多，就不会对性能造成影响

• encoding
  该属性记录了节点数据的类型及长度。这个就有点意思了，该属性可能有1、2或者4字节，而最高位如果是00、01、10则代表存储的为字节数组，如果是11则代表的是整数。具体如下

• content
  故名思义，就是实际保存值的属性