【说明】本文将介绍redis剩余的4种对象结构以及5种数据结构。

2、列表对象

【前言】

  列表对象的编码可以是ziplist(压缩列表)或者linkedlist(双端链表)，当列表对象包含的元素比较少时会会使用压缩列表，否则会使用双端链表
具体策略是，当列表对象同时满足以下两个条件时，将使用压缩列表编码：
  1、列表对象保存的所有字符串元素的长度都小于64个字节；
  2、列表对象保存的元素数量小于512个
如果上述两个条件的任何一个不能被满足，将使用双端链表编码
以上两个条件的上限值是可以通过配置文件中的list-max-ziplist-value、list-max-ziplist-entries来修改的
编码转换：
  如果压缩列表编码的列表对象，不再满足上述两个条件时，将会被转换为双端列表编码的格式

这种策略的优点是：
  1.因为压缩列表比双端链表更节省内存，并且在元素数量较少时，在内存中以连续块方式保存的压缩列表比起双端链表可以更快的被载入到缓存中
  2.随着列表对象包含的元素越来越多，使用压缩列表来保存元素的优势逐渐消失，对象就会将底层实现从压缩列表转向功能更强、也更适合保存大量元素的双端链表上面

【压缩列表--ziplist】

【结构】
  压缩列表(ziplist)是列表对象与哈希对象的底层数据结构
  压缩列表的节点可以保存一个字节数组或者一个整数值
  对于列表对象而言，当一个列表键只包含少量列表项，并且存储的整数、字符串都是比较短小的，将使用压缩列表
  对于哈希对象而言，当一个哈希键只包含少量键值对，并且键和值是小的整数或短的字符串时，将使用压缩列表

【压缩列表的结构】
压缩列表的整体数据结构图如下所示：

压缩列表编码的列表对象结构图如下所示：

压缩列表中各个属性的具体含义如下：
  zlbytes属性：记录压缩列表占用的总的内存字节数；在对压缩列表进行内存重分配或计算压缩列表末端位置(即zlend属性所在位置)时需要用到该属性
  zltail属性：记录压缩列表的最后一个列表节点的位置距离整个列表起始地址有多少字节，通过该属性，可以直接定位表尾节点的地址
  zllen属性：记录压缩列表的节点数量，当节点数量小于UNINT16_MAX(65535)时，该属性会记录节点数量的值，当节点数量大于65535时就不再存储，需要遍历整个压缩列表才能知道节点的总数量
  entryX属性：列表节点，用于存储实际的数值，每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成
    previous_entry_length属性：记录了前一个节点的长度
    encoding属性：实际要保存值的数据类型及长度
    content属性：实际在节点中保存的值，可以是一个字节数组或一个整数
  zlend属性：是一个特殊值OxFF(十进制255)，用于标记压缩列表的末端

包含三个节点的压缩列表结构示意图：

【列表节点中3个属性的详细说明】
1、previous_entry_length属性：
该属性记录了压缩列表中前一个节点的长度，单位是字节，长度可以是1字节或5字节，具体策略为：
  如果前一个节点的长度小于254字节，previous_entry_length属性将用1个字节的长度
  如果前一个节点的长度大于等于254字节，previous_entry_length属性将用5个字节的长度，第1个字节为固定的OxFE(十进制254)，之后的4个字节被用来保存前一个节点的长度

压缩列表从表位向表头遍历的原理：
  向压缩列表中存储数据的时候，最先存储的数据被放在列表尾部，新插入的数据会被放到旧数据的前面，读取压缩列表的顺序是由表尾到表头(读取最旧的数据到最新的数据)
  在读取数据的时候，会先读取zltail属性，通过该属性可以直接定位到压缩列表的表尾节点，然后通过previous_entry_length属性，依次找到上一个节点的数据，由后向前，可以依次读取出所有的数据

2、encoding属性
该属性记录了实际要保存值的数据类型及长度

3、content属性
该属性记录了保存节点的值，节点值可以是一个字节数组如”hello world”或者整数

【连锁更新】

上文说过：
  previous_entry_length属性：记录了前一个节点的长度（单位字节）
  如果前一个节点的长度小于254字节，previous_entry_length属性将用1个字节的长度
如果前一个节点的长度大于等于254字节，previous_entry_length属性将用5个字节的长度

如果碰巧发生这种情况：
  如果每一个节点的值都<254且>250，那么previous_entry_length属性的值都为1，但现在新插入一个值，该值的长度>=254，那么后面节点的previous_entry_length属性的值都将变为5。
  即牵一发而动全身，后面每个节点的大小都需要发生改变

除新增节点会导致连锁更新外，删除一个节点也有可能导致连锁更新，如下图所示：

总结：
  压缩列表是一种为节约内存而开发的顺序型数据结构
  压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值，可以被用于列表对象和哈希对象
  添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种几率并不高

【双端链表--linkedlist】

  当一个列表键包含了数量比较多的元素，或者列表中包含的元素都是比较长的字符串时，redis会使用链表作为列表键的底层实现。
  除了list列表对象、zset有序集合对象用到了链表之外，发布与订阅、慢查询、监视器等功能也用到了链表，redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区(output buffer)。

【链表结构】
链表结构由list+listnode两部分组成。
list结构：
  head：表头节点
  tail：表尾节点
  len：链表所包含的节点数量
  dup：节点值复制函数，用于复制链表节点所保存的值
  free：节点值释放函数，用户释放链表节点所保存的值
  match：节点值对比函数，用于对比链表节点所保存的值和另一个输入值是否相等
dup、free、match是用于实现多态链表所需的类型特定函数
链表节点(listNode)结构：
  prev 前置节点
  next 后置节点
  value 节点的值

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

linkedlist编码的列表对象，在存储上有以下特点：
linkedlist编码的列表对象，每个双端链表节点（node）都保存了一个字符串对象
中的字符串，即字符串对象嵌套在列表结构中，示意图如下所示：

上图中tree字符串对象的完整结构图如下所示：

3、哈希对象

哈希对象的编码可以是ziplist(压缩列表)或hashtable(字典)
当哈希对象可以同时满足以下两个条件时，哈希对象使用压缩列表编码：
  哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  哈希对象保存的键值对数量小于512个
当其中一个条件不能满足时，哈希对象使用hashtable(字典)编码的格式
  这两个条件的上限值可以通过配置文件中的hash-max-ziplist-value选项和hash-max-ziplist-entries选项来修改
编码转换：如果压缩列表编码的哈希对象，不再满足上述两个条件时，将被转换为字典编码的格式

压缩列表的详细结构上文已介绍过，这里不再赘述
压缩列表编码的哈希对象，在存储上有以下特点：
  保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后
  先添加到哈希对象的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向
结构示意图如下所示：

【字典】

【字典的特点】
  字典是以key-value方式存储数据的一种结构，字典中的每个键都是独一无二的，程序可以在字典中根据键查找、更新、删除与之关联的值，当字典中存储的数据过多或过少，都会通过rehash重新分配字典的大小和结构。

【字典的用途】
  1、redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查是构建在对字典的操作之上的；
  2、是哈希键的底层实现之一，当一个哈希键包含的键值对比较多，或者键值对中的元素都是比较长的字符串时，redis会使用字典作为哈希键的底层实现
  3、是集合底层的实现之一

【字典的结构】
字典主要由3部分结构共同组成：
  字典+哈希表+哈希节点
一个完整的字典结构如下图所示：

其中dict是字典结构，dictht是哈希表的结构，dictEntry*是哈希节点的结构，最右边是哈希节点保存的键值对的值，k0、k1是键，v0、v1是对应的值

下面分别详细介绍一下这三种结构：
【字典结构】
字典结构dict.h/dict有以下几个参数：

具体说明如下：
  ht属性是一个包含两个项的数组，数组中的每一个项都是一个dictht哈希表，一般情况下，字典只是用ht[0]哈希表，ht[1]哈希表只会在rehash时使用
  rehashidx属性，记录了rehash的进度，如果没有在rehash，则值为-1
  type和dicttype属性，保证了redis可以存储不同类型的键值对

【哈希表结构】
一个空的哈希表(没有任何键值对)整体结构图如下所示：

哈希表由dict.h/dictht结构定义，里面具体有table、size、used、sizemask几个属性：

具体说明如下：
  table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry(哈希表节点)结构的指针，每个dictEntry结构保存着一个键值对
  size属性记录了哈希表的大小，也即table数组的大小
  used属性记录了哈希表目前已有节点(键值对)的数量
  sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面

【哈希表节点结构】


因为dictentry结构中并没有属性指向链表表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置(复杂度O(1))，排在其它已有节点的前面

【rehash--重新散列】
  为保持哈希表中数据分配的合理性，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展和收缩
  对哈希表的扩展和收缩是通过执行rehash(重新散列)操作完成的，redis对字典的哈希表进行rehash的步骤如下：
1、为字典的ht[1]哈希表分配空间，分配策略为：
  如果要执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used2的2的n次幂(示例：如果used=3，size=3，32=6，第一个大于等于6且是2的n次幂的值是8，所以ht[1]的size大小为8)
  如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次幂(示例：如果used=3，但size=10，ht[1]的size值将为4，used是哈希表中实际存储的数据的节点数，size是哈希表大小即可以存储多少个数据节点)
2、将保存在ht[0]中的所有键值对rehash到ht[1]
3、释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，为下一次rehash做准备

【哈希表的扩展与收缩】
  当哈希表中的数据过于紧密或疏松时，会对哈希表进行扩展与收缩，具体策略如下：
  负载因子=哈希表已保存节点数量/哈希表大小
  load_factor = ht[0].used/ht[0].size
  当哈希表的负载因自小于0.1时，程序自动开始对哈希表执行收缩操作
  当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
    1.服务器目前没有在执行BGSAVE或BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
    2.服务器目前正在BGSAVE或BGREWRITEAOF命令，并且哈希表的负载因子大于等于5
  当正在执行BGSAVE或BGREWRITEAOF命令时，redis会创建子进程，会用到写时复制技术，需要占用部分内存，此时尽可能避免对哈希表进行扩展，避免消耗不必要的内存

【渐进式rehash】
  为了避免rehash对服务器性能造成影响，服务器不是一次将ht[0]里面所有的键值对全部rehash到ht[1]，而是分批次渐进式的rehash
  在渐进式rehash期间，字典会同时使用ht[0]、ht[1]两个哈希表，期间对字典的查、删、改都是在两个哈希表中进行的。如果要在字典里查找一个键，会先在ht[0]里面查找，如果没找到，会继续到ht[1]里进行查找。但是新增加的键值对一律会被保存到ht[1]中，所以ht[0]里的键值对只减不增

字典编码的哈希对象，在存储上有以下特点：
  字典中的每个键、值都是一个字符串对象

4、集合对象

集合对象可以用来存储不重复的数据。

集合对象的编码可以是intset(整数集合)或者hashtable(字典)

具体策略为：
当集合对象同时满足以下两个条件时，将使用intset编码：
  集合对象保存的所有元素都是整数值
  集合对象保存的元素数量不超过512个
不能满足这两个条件的集合对象需要使用hashtable编码
上述两个条件可以通过配置文件中的set-max-intset-entries选项来修改
【编码转换】当intset编码的集合对象不再满足上述两个条件时，将会转换为hashtable编码的格式

【整数集合】

整数集合(intset)是用来存储整数集合的结构，它可以保存int16_t、int32_t或int64_t的整数，并且保证数据不会重复。
【结构】

  contents数组里记录了具体的数据，数组中的数据按值的大小从小到大有序地排列
  length属性记录了数据的个数，即contents数组的长度
  enconding属性记录了数组中数据的类型，可以为intset_enc_int16、intset_enc_int32、intset_enc_int64，对应的类型分别是int16_t、int32_t、int64_t

升级

  当新添加的数据比整数集合现有的数据类型都要长时，需要先对整数集合进行升级，然后再添加新数据。
升级步骤：
  根据新数据的类型，扩展整数集合底层数组的空间大小
  将原有数据的类型均转换为新类型
  添加新数据

  因为每次向整数集合添加新元素都可能引起升级，而每次升级都需要对底层数组中已有的所有元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)。
  整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后对状态。

5、有序集合

  有序集合对编码可以是ziplist或者skiplist。
具体策略规则是：
当有序集合对象可以同时满足以下两个条件时，将使用ziplist编码：
  有序集合保存对元素数量小于128个
  有序集合保存的所有元素成员对长度都小于64字节
不能满足以上两个条件的有序集合对象都使用skiplist编码
以上两个条件的上限值可以通过配置文件中的zset-max-ziplist-entries和zset-max-ziplist-value选项来修改
【编码的转换】当ziplist编码的有序集合不再符合上述两个条件时，将被转换为skiplist编码的格式。

ziplist编码的有序集合的存储方式：
  ziplist编码以压缩列表结构作为底层实现，每个集合元素使用两个紧挨在一起对压缩列表节点来保存。第一个节点保存元素的成员(member)，第二个元素保存元素对分值(score)。压缩列表内对元素按分值大小进行拍下，分值较小对元素放在靠近表头对位置，结构示意图如下所示：

压缩列表结构之前已进行过详细说明，这里就不再赘述，下面将详细说明下skiplist编码。

Skiplist-字典+跳跃表

skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表，dict指针指向的是字典结构，zsl指针指向的是跳跃表结构，见下图。

字典结构之前已有过详细说明，这里不再赘述，下面先说一下跳跃表结构：

【跳跃表】

  如果一个有序集合包含的元素数量比较多，或者保存的字符串长度较长，redis将使用跳跃表作为有序集合键的底层实现。
  redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

【跳跃表结构】
  跳跃表由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度)，而zskiplistNode则用于表示跳跃表节点。

上图左侧是zskiplist结构，其包含以下属性：
  Header：指向跳跃表的表头节点
  Tail：指向跳跃表的表尾节点
  Level：记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
  Length：记录跳跃表的长度，即目前节点的数量

上图右侧是四个zskiplistNode结构，该结构有以下属性：
  层(level)：L1、L2、L3等字样表示各节点的层，连线上带有数字箭头的是前进指针，箭头上的数字表示跨度。前进节点可以挨个遍历，也可以一次跳过多个节点
  后退(backward)指针：节点中用BW字样标记的是后退指针。后退节点每次只能退至前一个节点。
  分值(score)：各个节点中的1.0、2.0和3.0是节点保存的分值，在跳跃表中，节点按各自所保存的分值从小到大排列
  成员对象(obj)：各个节点中的o1、o2和o3是节点所保存的成员对象。

分值和成员
  节点的分值(score属性)是一个double类型的浮点数，跳跃表中的所有节点都按分值从小到大来排序
  节点的成员对象(obj属性)是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值
  在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的，分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面(靠近表头的位置)

【进一步说明】

  zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。通过这个跳跃表，程序可以对有序集合进行范围操作，如zrank、zrange等命令就是基于跳跃表api来实现的。
  除此之外，zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O(1)复杂度查找给定成员的分值，zscore命令就是根据这一特性实现的，而很多其它有序集合命令都在实现的内部用到了这一特性。
  有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是，虽然zset结构同时使用跳跃表和字典来保存有序集合元素，但这两种数据结构都会通过指针来共享相同元素的成员和分值，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或分值，也不会因此浪费额外的内存。

【为什么有序集合需要同时使用跳跃表和字典来实现？】
  为了保存两种结构各自的优点，字典结构可以以O(1)复杂度查找成语的分值，但字典以无序但方式来保存集合元素；而跳跃表结构用范围查询时复杂度只要O(1).