Redis看这一篇就够了（二）

Redis数据结构

在介绍数据对象与数据结构的转换关系之前，先来了解下Redis的几种数据结构：动态字符串、字典、链表、整数集合、压缩列表、跳跃表+字典。

动态字符串SDS

SDS的数据结构如下，包含三部分属性，len、free以及buf数组，用来描述一个SDS的结构体：

struct sdshdr {
    unsigned int len;  //记录buf数组中已使用字节数量，也即SDS所保存字符串长度
    unsigned int free;  //记录buf数组中未使用字节数量
    char buf[];    //字节数组，用于保存字符串
};

动态字符串结构

示例如下图所示：

• free属性的值为5，表示这个SDS分配了5字节的未使用空间
• len属性的值为5，表示这个SDS保存了一个五字节长的字符串，需要注意的是长度不包含末尾的补0
• buf属性是一个char类型的数组，数组的前五个字节分别保存了’R’、‘e’、‘d’、‘i’、‘s’五个字符，而最后一个字节则保存了空字符’\0’

保留了C语言补0的习惯是为了方便复用C语言的一些函数。

动态字符串优点

SDS的优势如下：

• 常数复杂度获取字符串长度，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O（1）
• 杜绝缓冲区溢出，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小
• 减少修改字符串时带来的内存重分配次数，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联 ：在SDS中，buf数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录
• 空间预分配策略，如果对SDS进行修改之后，SDS的长度（也即是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同，如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。也就是说1M以下倍增，1M以上只增加1M，防止存储过大对象，通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数
• 惰性空间释放策略，惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。SDS也提供了相应的API，在有需要时，我们可以真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费通过惰性空间释放策略，Redis可以减少执行字符串缩短操作所需的内存重分配次数
• 二进制安全，SDS的API都是二进制安全的（binary-safe），所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样，例如，使用SDS来保存包含空字符格式的数据格式就没有任何问题，因为SDS使用len属性的值而不是空字符来判断字符串是否结束Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据

总而言之，动态字符串用额外的free和len空间来弥补了很多C语言性能上的问题。

链表

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度，但是由于C语言没有链表的数据结构，所以Redis的链表是自己定义的结构。

链表结构

链表单节点的数据结构如下，包含三部分属性prev、next以及value，用来描述一个链表单节点的结构体：

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

示例如下图所示：

同时Redis为了方便的操作链表，提供了一个list结构来持有链表，也就是我们的链表结构，如下所示

list结构为链表提供了表头指针head、表尾指针tail，以及链表长度计数器len，而dup、free和match成员则是用于实现多态链表所需的类型特定函数：

• dup函数用于复制链表节点所保存的值
• free函数用于释放链表节点所保存的值
• match函数则用于对比链表节点所保存的值和另一个输入值是否相等

用代码来描述如下所示：

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列表数据对象、发布与订阅、慢查询、监视器等

字典

字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构，字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对

• Redis数据库就是一个字典模型，key和value组成
• 同时hash对象的底层实现之一也包括字典

总而言之，字典有较为广泛的用途，但是同链表一样，C语言没有字典这种数据结构，所以Redis自己实现了这种结构。

字典结构

字典是由哈希表加上一系列属性方法组成，而哈希表又是由哈希表节点加上一系列哈希表结构组成的：

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对，但是有链式结构：

typedef struct dictEntry {
    // 键
    void *key;
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

各个属性部分如下：

• key属性保存着键值对中的键
• v属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个uint64_t整数，又或者是一个int64_t整数。
• next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题

也就是说在相同键上的多个哈希表节点存在链式关系，有链表实现。

哈希表

哈希表结构定义如下，包括哈希表数组，哈希表大小【已用+未用】的变量，哈希表大小的掩码值，哈希表已有节点数量

typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    unsigned long sizemask;
    // 该哈希表已有节点的数量
    unsigned long used;
} dictht;

各个属性部分如下：

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

其中table是我们这个结构的核心。

字典

字典又是由哈希表和一系列属性和函数组成的，为了满足Redis快而增加的一些空间占用属性：

typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引，当 rehash 不再进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

各个属性含义如下：

• type属性和privdata属性是针对不同类型的键值对，而创建多态字典而设置的：type属性是一个指向dictType结构的指针，每个dictType结构保存了一组用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同类型的特定函数。而privadata属性则保存了需要传给那些类型特定函数的可选参数。
• ht属性是一个包含了两个项的数组，数组中每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，而ht[1]哈希表只对ht[0]哈希表进行rehash时使用。
• rehashidx属性，与rehash相关，它积累了rehash目前的进度，如果没有进行rehash，则它的值为-1

关于rehash算法在接下来的内容重点看，其中ht属性是较为核心的属性。

哈希算法

当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面：

• 使用字典设置的哈希函数，计算键 key 的哈希值hash = dict->type->hashFunction(key);
• 使用哈希表的 sizemask 属性和哈希值，计算出索引值，index = hash & dict->ht[x].sizemask，根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]，

举个例子，假设hash计算结果为8，且掩码为3，则相与的结果为0，所以被放到ht[0]哈希表的字典索引0的位置

解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题：

另外因为dictEntry节点组成的链表没有指向链表表尾的指针，为了考虑速度，程序总是将新节点添加到链表的表头位置（这样添加节点的时间复杂度为O(1)）

rehash

随着操作的不断进行，哈希表保存的键值对会逐渐增多或减少，为了让**哈希表负载因子【哈希表已保存节点数量/哈希表的size，可以理解为used/size】**维持在一个合理范围之内，当哈希表保存的键值对太多或太少时，程序要对哈希表的大小进行相应的扩展或收缩。

Redis对字典的哈希表执行rehash的步骤如下：

1. 为字典的ht[1]哈希表分配空间，这个空间大小取决于要执行的操作

• 如果执行扩展操作，则ht[1]的大小为第一个大于等于等于ht[0].used*2的2^n；
• 如果执行收缩操作，则ht[1]的大小为第一个大于等于ht[0].used的2^n；当哈希表负载因子小于0.1时，程序自动开始对哈希表执行收缩操作
  

2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]的指定位置上。
   
   
3. 当ht[0]包含的所有键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
   
   

以上就是rehash的全流程。当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

• 1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
• 2）服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

BGSAVE或BGREWRITEAOF操作是Redis的持久化操作，在执行BGSAVE命令或BGREWRITEAOF命令的过程中，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）【只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程】技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

渐进式rehash

Redis中的rehash动作并不是一次性、集中式完成的，而是分多次、渐进式的完成的。这样做的目的是，如果服务器中包含很多键值对，要一次性的将这些键值对全部rehash到ht[1]的话，庞大的计算量可能导致服务器在一段时间内停止服务。渐进式Rehash操作

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。在字典中维持一个索引计数器变量rehashidx，并将它置为0，表示rehash工作开始。
   
   
2. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]中，当rehash工作完成之后，程序将rehashidx属性的值+1。
   
   
3. 随着字典操作的不断进行，最终在某个时间点上，ht[0]的所有键值对都被rehash到ht[1]上，这时将rehashidx属性设为-1，表示rehash完成。
   
   渐进式rehash的好处在于其采取分而治之的方式，将rehash键值对所需要的计算工作均摊到字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量：
   

• 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1]里面进行查找，诸如此类。
• 在渐进式rehash执行期间，新添加到字典的键值对一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表

这样又是一个以空间换取时间的案例。参考《Redis的设计与实现》

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现

整数集合结构

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素

//每个intset结构表示一个整数集合
typedef struct intset{
    //编码方式
    uint32_t encoding;
    //集合中包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

各个属性的含义如下：

• contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项
• length属性记录了整数集合包含的元素数量，也即是contents数组的长度
• encoding属性记录了contents数组中元素的真实类型，虽然intset结构将contents属性声明为int8_t类型的数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值，类型对应关系

• 如果encoding属性的值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组，数组里的每个项都是一个int16_t类型的整数值（最小值为-32768，最大值为32767）
• 如果encoding属性的值为INTSET_ENC_INT32，那么contents就是一个int32_t类型的数组，数组里的每个项都是一个int32_t类型的整数值（最小值为-2147483648，最大值为2147483647）
• 如果encoding属性的值为INTSET_ENC_INT64，那么contents就是一个int64_t类型的数组，数组里的每个项都是一个int64_t类型的整数值（最小值为-9223372036854775808，最大值为9223372036854775807）

例如如下结构就描述了一个整数数组：

因为每个集合元素都是int64_t类型的整数值，所以contents数组的大小等于sizeof（int64_t）x 4=64x4=256位，根据整数集合的升级规则，当向一个底层为int16_t数组的整数集合添加一个int64_t类型的整数值时，整数集合已有的所有元素都会被转换成int64_t类型，所以contents数组保存的四个整数值都是int64_t类型的

整数集合升级

每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面。升级整数集合并添加新元素主要分三步来进行：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变
3. 将新元素添加到底层数组里面

图解如下，图片来源

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素【正整数和负整数】

• 在新元素小于所有现有元素的情况下，新元素会被放置在底层数组的最开头（索引0）
• 在新元素大于所有现有元素的情况下，新元素会被放置在底层数组的最末尾（索引length-1）

这样升级就完成了，整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存：

• 提升灵活性：因为C语言是静态类型语言，为了避免类型错误，我们通常不会将两种不同类型的值放在同一个数据结构里面，因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将int16_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误
• 要让一个数组可以同时保存int16_t、int32_t、int64_t三种类型的值，最简单的做法就是直接使用int64_t类型的数组作为整数集合的底层实现。不过这样一来，即使添加到整数集合里面的都是int16_t类型或者int32_t类型的值，数组都需要使用int64_t类型的空间去保存它们，从而出现浪费内存的情况。而整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存,也就是动态变化

有了这两个特性可以安全灵活又不担心内存大量使用的去玩儿了，整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态，即使我们把65535干掉了，其它元素都小。数组类型还是int32。

跳跃表

跳跃表是一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。Redis使用跳跃表作为ZSET的底层实现之一。如果一个ZSET包含的元素数量比较多,又或者ZSET中元素的成员是比较长的字符串时, Redis就会使用跳跃表来作为有序集合健的底层实现。

• 跳跃表在链表的基础上增加了多级索引以提升查找的效率，是一个空间换时间的方案，必然会带来一个问题——索引是占内存的。原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值值和几个指针，并不需要存储对象，因此当节点本身比较大或者元素数量比较多的时候，其优势必然会被放大，而缺点则可以忽略

跳跃表支持**平均O（logN）、最坏O（N）**复杂度的节点查找，还可以通过顺序性操作来批量处理节点，Redis的跳跃表由zskiplistNode和skiplist两个结构定义,其中 zskiplistNode结构用于表示跳跃表节点,而 zskiplist结构则用于保存跳跃表节点的相关信息,比如节点的数量,以及指向表头节点和表尾节点的指针等等

跳跃表结构

跳跃表由跳跃表节点加一些附加属性组合而成。

跳跃表节点

跳跃表节点的数据结构定义如下

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    robj *obj;  /*成员对象*/
    double score;   /*分值*/
    struct zskiplistNode *backward; /*后退指针*/
    struct zskiplistLevel { /*层*/
        struct zskiplistNode *forward;  /*前进指针*/
        unsigned int span;  /*跨度*/
    } level[];
} zskiplistNode;

各个属性的含义如下：

• 层（level）：节点中用L1、L2、L3等字样标记节点的各个层，L1代表第一层，L2代表第二层，以此类推。每个层都带有两个属性：前进指针和跨度。前进指针用于访问位于表尾方向的其他节点，而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中，连线上带有数字的箭头就代表前进指针，而那个数字就是跨度。当程序从表头向表尾进行遍历时，访问会沿着层的前进指针进行。一般来说，层的数量越多，访问其他节点的速度就越快，每次创建一个新跳跃表节点的时候，程序都根据**幂次定律（power law，越大的数出现的概率越小）**随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”
  
  
• 后退（backward）指针：节点中用BW字样标记节点的后退指针，它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用，因为每个节点只有一个后退指针，所以每次只能后退至前一个节点
  
• 分值（score）：各个节点中的1.0、2.0和3.0是节点所保存的分值。分值是一个double类型的浮点数，在跳跃表中，节点按各自所保存的分值从小到大排列，有序的。节，跳跃表中的所有节点都按分值从小到大来排序
  
• 成员对象（obj）：各个节点中的o1、o2和o3是节点所保存的成员对象，节点的成员对象（obj属性）是一个指针，它指向一个字符串对象，而字符串对象则保存着一个SDS值
  

那么跳跃表是如何迭代寻找分值对象呢？使用前进指针就能实现

• 1）迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点
• 2）在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。
• 3）在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。
• 4）当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历

那么如何计算目标节点在跳跃表中的排位呢？在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是，实际上就是节点的顺序值。

需要注意：在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分值相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面（靠近表头的方向），而成员对象较大的节点则会排在后面（靠近表尾的方向）

跳跃表

跳跃表结构的构建代码如下：

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;    //header指向跳跃表的表头节点，tail指向跳跃表的表尾节点
    unsigned long length;   //记录跳跃表的长度，也即是，跳跃表目前包含节点的数量(表头节点不计算在内)
    int level;  //记录目前跳跃表内，层数最大的那个节点的层数(表头节点的层数不计算在内)
} zskiplist;

skiplist结构包含以下属性：

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

核心部分就是header了，之后挂了一串跳跃表节点，可以看到Redis的数据结构，无论是链表还是哈希表，都是采用链表的方式实现的。而链表的插入和删除动作都是O（1），单纯指“插入”这个操作，而不包含找到插入的位置。链表插入只要修改元素的地址。而数组需要将后面所有元素都修改位置，如果连续空间不够还要查找空间，并将整个数组重新存储。所以对比“插入”操作，链表是O(1)，数组是O(n)

压缩列表

压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或者一个整数值

压缩列表结构

压缩列表包括压缩列表节点和一系列的属性组合而成。

压缩列表节点

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度的其中一种：

• 长度小于等于63（2^6–1）字节的字节数组
• 长度小于等于16383（2^14–1）字节的字节数组
• 长度小于等于4294967295（2^32–1）字节的字节数组；

而整数值则可以是以下六种长度的其中一种：

• 4位长，介于0至12之间的无符号整数；
• 1字节长的有符号整数；
• 3字节长的有符号整数；
• int16_t类型整数；
• int32_t类型整数；
• int64_t类型整数

每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成

• 节点的previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。长度可以是1字节或者5字节

• 如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节：前一节点的长度就保存在这一个字节里面
• 如果前一节点的长度大于等于254字节，那么previous_entry_length属性的长度为5字节：其中属性的第一字节会被设置为0xFE（十进制值254），而之后的四个字节则用于保存前一节点的长度
  

• 节点的encoding属性记录了节点的content属性所保存数据的类型以及长度：

• 一字节、两字节或者五字节长，值的最高位为00、01或者10的是字节数组编码：这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录
• 一字节长，值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型由编码除去最高两位之后的其他位记录
  

• 节点的content属性负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定