- 压缩列表（ziplist）是列表键和哈希键的底层实现之一。如果列表键只包含少量的列表项，每个列表项要么是小整数值，要么就是长度比较短的字符串，redis就会使用压缩列表来做列表键的底层实现。或者哈希键只包含少量的键值对，每个键值对的键和值要么是小整数值，要么就是长度比较短的字符串，redis就会使用压缩列表来做哈希键的底层实现。
压缩列表的构成
- 压缩列表是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值
zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend
详细说明：
| 属性 ：类型 ：长度 | 用途 |
|---|---|
| zlbytes ： uint32_t ： 4字节 | 整个压缩列表占用的内存字节数：对压缩列表进行内存重分配，或计算zlend的位置时使用。 |
| zltail ：uint32_t ：4字节 | 记录表尾节点距离列表起始地址有多少字节：通过这个偏移量，无须遍历整个压缩列表就可以确定表尾节点的地址 |
| zllen ：uint16_t ：2字节 | 记录压缩列表包含节点的数量：属性值小于uint_16_max(65535)时，该值就是压缩列表包含节点的数量；等于uint_16_max(65535)时，节点的真实数量需要遍历列表才能计算出来 |
| entryx ：列表节点 ：不定 | 列表包含的各个节点，节点长度由节点保存的内容决定 |
| zlend ：uint8_t ：1字节 | 特殊值0xff（255），用于标记压缩列表的末端 |
WechatIMG65.jpeg
示例：
- zlbytes 值为 0x50（十进制80），表示压缩列表总长为80个字节、
- zltail 值为 0x3c（十进制60），如果我们有一个指向压缩列表起始地址的指针p，只要指针p加上偏移量60，就可以计算出表尾节点entry3的地址。
- zllen 值为0x3（十进制3）表示压缩列表包含三个节点
7.2 压缩列表节点的构成
每个压缩列表节点可以保存一个字节数组或者一个整数值，字节数组可以是以下三种之一：
- 长度小于等于63（2^6 - 1）字节的字节数组
- 长度小于等于16383（2^14 - 1）字节的字节数组
- 长度小于等于4294967295（2^32 - 1）字节的字节数组
而整数值则可以是以下6种长度之一： - 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),之后的四个字节用于保存前一节点的长度。
由于节点的 previous_entry_length 属性记录了前一个的节点长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。压缩列表从表尾向表头遍历操作就是使用这一原理实现的。
encoding
该属性记录了节点的content属性所保存的数据类型及长度。
content
该属性保存节点的值，可以是一个字节数组或者整数，值的类型和长度由节点encoding属性决定。
7.3连锁更新
假如有个压缩列表，有多个连续的长度介于250字节~253字节之间的节点e1至eN，如果我们将一个长度大于等于254字节的新节点new 设置为压缩列表的表头节点，那么new将成为e1的前置节点；因为，e1的previous_entry_length长为1字节，无法保存new节点，所以程序需要对压缩列表执行空间分配，e1的previous_entry_length属性从原来的1节点扩展为5节点的长度。为了让e2的previous_entry_length属性可以记录下e1的长度，程序需要在次对 压缩列表执行空间分配，从原来的1字节扩展到5字节。从而引起e1对e2，e2对e3……直到eN为止，在特殊情况下多次空间扩展称为“连锁更新”（删除节点也会引起）。
7.4压缩列表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) |
网友评论