redis数据结构之压缩列表

压缩列表是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数，要么就是长度比较短的字符串，redis就会使用压缩列表来做列表键的底层实现

当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。

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

ziplist 数据结构：压缩列表各个组成部分

压缩列表各个组成部分详细说明：

压缩列表节点的构成：

每个压缩列表节点可以保存一个字节数组或者一个整数值，其中字节数组可以是以下三种长度的其中一种

长度小于等于63字节的字节数组

长度小于等于16383字节的字节数组

长度小于等于4294967295字节的字节数组

数值则可以是以下六种长度的其中一种：

• 1:  4位长介于0至12之间的无符号整数
• 2：1字节长的有符号整数
• 3: 3字节长的有符号整数
• 4：int16类型整数
• 5：int32类型整数
• 6 : int64类型整数

压缩列表的数据结构：

压缩列表是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)

总结：

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