redis数据结构之压缩列表

将相本无种，男儿当自强。这篇文章主要讲述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将这种在特殊情况下产生的连续多次空间扩展操作称之为连锁更新
【redis数据结构之压缩列表】在添加新节点和删除节点都可能引发连锁更新。
连锁更新最坏情况下需要对压缩列表进行N次空间重分配操作，每次空间重分配的最坏复杂度为O(N)，所以连锁更新的最坏复杂度为O(N的平方)，平均复杂度为O(N)
总结
压缩列表是为了节约内存而开发的顺序型数据结构，它是列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或整数值，添加新节点或删除节点可能引发连锁更新操作，这种操作出现几率不高。