redis 数据结构之压缩列表

redis 数据结构之压缩列表

压缩列表是列表 list 和 hash 数据结构的底层实现之一。

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

创建一个空的 ziplist

/* * 新创建一个空 ziplist *  * 复杂度：O(1) * * 返回值：新创建的 ziplist */unsigned char *ziplistNew(void) {    // 分配 2 个 32 bit，一个 16 bit，以及一个 8 bit    // 分别用于 <zlbytes><zltail><zllen> 和 <zlend>    unsigned int bytes = ZIPLIST_HEADER_SIZE+1;    unsigned char *zl = zmalloc(bytes);
    // 设置长度    ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
    // 设置表尾偏移量    ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
    // 设置列表项数量    ZIPLIST_LENGTH(zl) = 0;
    // 设置表尾标识    zl[bytes-1] = ZIP_END;
    return zl;}

压缩列表包含任意多个压缩列表节点，每个节点可以保存一个字节数组或者一个整数值。

压缩列表组成部分：

• zlbytes：记录整个压缩列表占用的内存字节数

• zltail：记录压缩列表表尾节点距离压缩列表的起始地址的字节数

• entryX：列表节点

• zlend：用于标记压缩列表的末端

压缩列表节点的构成：

• preivous_entry_length：记录压缩列表中前一个节点的长度

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

• content：负责保存节点的值，值的类型和长度由节点的 encoding 属性决定。

当我们知道一个指向某个节点起始地址的指针，那么通过这个指针以及这个节点的 preivous_entry_length 属性，我们可以一直向前一个节点回溯，最终到达压缩列表的表头节点。

连锁更新

每个节点的 preivous_entry_length 属性记录前一个节点的长度

如果前一个节点长度小于 254 字节，preivous_entry_length 属性需要用 1 字节长的空间来保存这个长度值

如果前一个节点长度大于等于 254 字节，preivous_entry_length 属性需要用 5 字节长的空间来保存这个长度值

如果前一个节点长度变大，这个节点的 preivous_entry_length 就要扩展，这个节点的扩展引起下一个节点的扩展，这就是连锁更新

redis 将这种在特殊情况下产生的连续多次空间扩展操作称之为连锁更新

在添加新节点和删除节点都可能引发连锁更新。

连锁更新最坏情况下需要对压缩列表进行 N 次空间重分配操作，每次空间重分配的最坏复杂度为 O(N)，所以连锁更新的最坏复杂度为 O(N 的平方)，平均复杂度为 O(N)

总结

压缩列表是为了节约内存而开发的顺序型数据结构，它是列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值，添加新节点或删除节点可能引发连锁更新操作，这种操作出现几率不高。