压缩列表是一种为节约内存而开发的顺序性数据结构,被用作列表键和哈希键的底层实现之一.

压缩列表的结构

• zlbytes | zltail | zllen | entry .. | zlend
• zlbytes(4字节): 压缩列表占用的内存字节数:对压缩列表进行内存重分配,或者计算zlend的位置时使用
• zltail(4字节) : 表尾节点距离压缩列表起始地址有多少字节:通过这个偏移量可以直接确定表尾节点的地址
• zllen(2字节): 压缩列表包含的节点数量:当这个值小于65535(UINT16_MAX)时为准确值,等于65535时需要遍历重新计算得出
• entry(不定): 压缩列表的节点,结构之后给出
• zlend(1字节): 特殊值,标记压缩列表的末端.类似c语言中string的结尾\0

节点entry的结构

• previous_entry_length | encoding | content
• previous_entry_length(1字节或5字节): 前一个节点的长度,前一节点长度小于254时长度为1字节,大于等于254时长度为5字节
• encoding(1字节,2字节或5字节): 记录节点content保存的数据类型以及长度
• content(一个干活的屌丝,一切都由encoding拿捏)

连锁更新(效率最坏的情况)

• 发生的情况介绍

  插入数据之前所有的节点长度都介于250~253之间,在表头的位置插入长度大于等于254的新节点.这样就会导致之后所有节点的previous_entry_length需要从1字节扩容到5字节,从而导致连锁更新.

• 最坏情况下空间重分配的次数为O(n^2)

• 发生概率较低(连续250~253才会诱发)

• 被更新的节点数量不多,就不会对性能造成影响

总结

• 压缩列表严格定义了每个区域的长度,previous_entry_length记录了节点之间的距离,encoding中用位表示了数据类型和长度,这样的结构适合指针跳跃和数据解析,保持高性能

• 精心设计的一些约定(主要针对变长的previous_entry_length和encoding如何确定长度):

  previous_entry_length: 读取的第一个字节为0xFE(254)表示5位

  encoding: 前两位表示了encoding的长度(00: 1字节字符, 01: 2字节字符, 10: 5字节字符, 11: 1字节整数)