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)

总结

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