7.0 压缩列表 zipList
压缩列表是列表键与哈希键底层实现之一。
构成
属性 | 类型 | 长度 | 用途 |
---|---|---|---|
zlbytes |
uint32_t |
4 字节 |
记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配, 或者计算 zlend 的位置时使用。 |
zltail |
uint32_t |
4 字节 |
记录压缩列表表尾节点距离压缩列表的起始地址有多少字节: 通过这个偏移量,程序无须遍历整个压缩列表就可以确定表尾节点的地址。 |
zllen |
uint16_t |
2 字节 |
记录了压缩列表包含的节点数量: 当这个属性的值小于 UINT16_MAX (65535 )时, 这个属性的值就是压缩列表包含节点的数量; 当这个值等于 UINT16_MAX 时, 节点的真实数量需要遍历整个压缩列表才能计算得出。 |
entryX |
列表节点 | 不定 | 压缩列表包含的各个节点,节点的长度由节点保存的内容决定。 |
zlend |
uint8_t |
1 字节 |
特殊值 0xFF (十进制 255 ),用于标记压缩列表的末端。 |
节点构成
previous_entry_length
previous_entry_length
属性的长度可以是 1
字节或者 5
字节:
- 如果前一节点的长度小于
254
字节, 那么previous_entry_length
属性的长度为1
字节: 前一节点的长度就保存在这一个字节里面。 - 如果前一节点的长度大于等于
254
字节, 那么previous_entry_length
属性的长度为5
字节: 其中属性的第一字节会被设置为0xFE
(十进制值254
), 而之后的四个字节则用于保存前一节点的长度。
0xFE ==> 254
0x05 == >5
压缩列表的从表尾向表头遍历操作就是使用这一原理实现的: 只要我们拥有了一个指向某个节点起始地址的指针, 那么通过这个指针以及这个节点的 previous_entry_length
属性, 程序就可以一直向前一个节点回溯, 最终到达压缩列表的表头节点。
encoding
记录了节点的 content
属性所保存数据的类型以及长度
Content
节点的 content
属性负责保存节点的值, 节点值可以是一个字节数组或者整数, 值的类型和长度由节点的 encoding
属性决定。
连锁更新
每个节点的 previous_entry_length
属性都记录了前一个节点的长度
因为连锁更新在最坏情况下需要对压缩列表执行 N
次空间重分配操作, 而每次空间重分配的最坏复杂度为 O(N) , 所以连锁更新的最坏复杂度为 O(N^2) 。
尽管连锁更新的复杂度较高, 但它真正造成性能问题的几率是很低的:
- 首先, 压缩列表里要恰好有多个连续的、长度介于
250
字节至253
字节之间的节点, 连锁更新才有可能被引发, 在实际中, 这种情况并不多见; - 其次, 即使出现连锁更新, 但只要被更新的节点数量不多, 就不会对性能造成任何影响: 比如说, 对三五个节点进行连锁更新是绝对不会影响性能的;
压缩列表 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) 。 |
- 压缩列表是一种为节约内存而开发的顺序型数据结构。
- 压缩列表被用作列表键和哈希键的底层实现之一。
- 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
- 添加新节点到压缩列表, 或者从压缩列表中删除节点, 可能会引发连锁更新操作, 但这种操作出现的几率并不高。