写点什么

redis 数据结构之压缩列表

作者:周杰伦本人
  • 2022 年 9 月 04 日
    贵州
  • 本文字数:1120 字

    阅读完需:约 4 分钟

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)

总结

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

发布于: 刚刚阅读数: 5
用户头像

还未添加个人签名 2020.02.29 加入

公众号《盼盼小课堂》,多平台优质博主

评论

发布
暂无评论
redis数据结构之压缩列表_9月月更_周杰伦本人_InfoQ写作社区