- 压缩列表（ziplist）是列表键和哈希键的底层实现之一
- 当一个列表键，只包含列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，Redis就会使用压缩列表来做列表键的底层实现
- 当一个哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数，要么是长度短的字符串，那么Redis会使用压缩列表来做哈希键的地层实现
压缩列表的构成
- 压缩列表是为了节约内存开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含任意多个节点，每个节点保存一个字节数组或一个整数值
压缩列表的组成部分
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录整个压缩列表占用的内存字节数：在对压缩列表进行内存重分配，或者计算zlend的位置的时候使用 |
| zltail | uint32_t | 4字节 | 记录压缩列表的表尾节点距离压缩列表的起始地址有多少个字节：通过这个偏移量，程序无须遍历整个压缩列表就可以确定表尾节点的地址 |
| zllen | uint16_t | 2字节 | 记录了压缩列表包含的字节数量：当这个属性的值小于UINT16_MAX(65535)时，这个属性的值就是压缩列表包含节点的数量，当这个值等于UINT16_MAX时，节点的真实数量需要遍历整个压缩列表才能计算出来 |
| entryN | 列表节点 | 不定 | 压缩列表包含的各个节点，节点的长度由节点保存的内容决定 |
| zlend | uint8_t | 1字节 | 特殊值0xFF（255），用于标记压缩列表的末端 |
压缩列表节点的构成
- 压缩列表节点可以保存一个字节数组或者一个整数值，其中，字节数组可以是以下三种长度中的一种
- 长度小于等于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
- previous_entry_length属性是以字节为单位的，记录了压缩列表中前一个节点的长度，这个属性的长度可以是1字节或5字节
- 如果前一个节点的长度小于254字节，那么previous_entry_length属性就是1字节，前一个节点的长度就保存到这一个字节中
- 如果前一个节点的长度大于等于254字节，那么previous_entry_length属性就是5字节，其中属性第一个字节被设置为0xFE（254），表明这是一个5字节属性，而后面4个字节用于保存前一个节点的长度
当前节点的前一个节点长度为5字节
当前节点的前一个节点长度为10086字节
- 用这个属性可以通过指针计算前一个节点的地址，当前节点指针减去当前节点的previous_entry_length就可以计算出前一个节点的地址
- 可以从表尾向表头遍历，使用的就是这个属性
encoding
- 节点的encoding属性记录了节点的content属性所保存数据类型以及长度
- 一字节长，两字节或五字节长，值的最高位00或者01或者10的字节数组编码表示content保存字节数组，数组的长度表示由编码去除最高位之后的其他位记录
- 一字节长，值的最高位是以11开头的，表示content保存的是整数，整数的长度由编码去除最高两位之后的其他位记录
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 00bbbbbb | 1字节 | 长度小于等于63字节的字节数组 |
| 01bbbbbb xxxxxxxx | 2字节 | 长度小于等于16383字节的字节数组 |
| 10aaaaaa bbbbbbbb cccccccc dddddddd eeeeeeee | 5字节 | 长度小于等于4294967295字节的的字节数组 |
| 编码 | 编码长度 | content属性保存的值 |
|---|---|---|
| 11000000 | 1字节 | int16_t类型的整数 |
| 11010000 | 1字节 | int32_t类型的整数 |
| 11100000 | 1字节 | int64_t类型的整数 |
| 11110000 | 1字节 | 24位有符号整数 |
| 11111110 | 1字节 | 8位有符号整数 |
| 1111xxxx | 1字节 | 使用这一编码的节点没有相应的content属性，因为编码本身的xxxx4个位已经保存了一个介于0到12之间的值，所以无需content属性 |
content
- content负责保存节点的值，节点值可以是一个字节数组或整数，值的类型和长度由节点的encoding属性决定
连锁更新
- 如果e1到en的长度都是介于250到253字节之间，如果此刻在e1前面加入一个大于等于254字节的节点，那么此刻e1的previous_entry_length需要新增4个字节空间，e1的长度就介于254到257字节之间了，使用一个字节是没有办法保存的，所以需要对e1进行空间重分配，同理一直到en，都需要空间重分配，可能会引发连锁更新
- 删除节点也可能引发连锁更新，比如一个big节点，一个small节点，一个e1节点，他们都依次挨着，samll节点previous_entry_length是5字节的，而e1是1字节的，此刻删除small，那么e1就会进行空间重分配，可能后面的都需要进行空间重分配，会引发连锁更新
- 连锁更新需要对压缩列表执行N此空间重分配，每次空间重分配，最坏复杂度是O（N），所以连锁更新的最坏复杂度为O（N^2）
连锁更新复杂度高，但是真正造成性能问题几率很低
要引发连锁更新，需要列表中有好多个连续的，长度介于250到253字节之间的节点
即使出现了连锁更新，但只要更新的节点数量不多，就不会对性能造成影响
所以ziplistPush这些命令的平均复杂度为O（N）
压缩列表API
| 函数 | 作用 | 算法复杂度 |
|---|---|---|
| ziplistNew | 创建一个新的压缩列表 | O（1） |
| ziplistPush | 创建一个包含给定值的新节点，并将这个新节点添加到压缩列表的表头或表尾 | 平均O（N），最坏O（N^2） |
| ziplistInsert | 将包含给定值的新节点插入到给定节点之后 | 平均O（N），最坏O（N^2） |
| ziplistIndex | 返回压缩列表给定索引上的节点 | O（N） |
| ziplistFind | 在压缩列表中查找并返回包含了给定值的节点 | 因为节点的值可能是数组，所以在检查节点值和给定值是否相同O（N），查找整个列表的复杂度O（N^2） |
| ziplistNext | 返回给定节点的下一个节点 | O（1） |
| ziplistPrev | 返回给定节点的前一个节点 | O（1） |
| ziplistGet | 获取给定节点所保存的值 | O（1） |
| ziplistDelete | 从压缩列表删除给定的节点 | 平均O（N），最坏O（N^2） |
| ziplistDeleteRange | 删除压缩列表在给定索引上的连续多个节点 | 平均O（N），最坏O（N^2） |
| ziplistBlobLen | 返回压缩列表目前占用的内存字节数 | O（1） |
| ziplistLen | 返回压缩列表目前包含的节点数量 | 节点数量小于65535是O(1),大于等于65535是O（N） |
