Redis数据结构学习-压缩列表(六)

2020-04-28  本文已影响0人  牛牛_735d

压缩列表是列表键和hash键的底层实现之一, 当一个键只包含少量列表项、且每个列表项要么是小整数值、要么是长度比较短的字符串、那么redis就会使用压缩列表作为底层实现

压缩列表的组成

压缩列表是Redis为了节约内存开发的, 是一系列特殊编码的连续内存块组成的顺序型数据结构,

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

压缩列表.png

zltytes: 压缩列表的总长度

zltail: 表示表头和表尾节点的位置偏移量

zllen: 表示压缩列表包含的节点数

压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值, 字节数组可以是下边任意一种:

  1. 长度小于等于63(26-1)字节的字节数组
  2. 长度小于等于16383 (214-1)字节的字节数组
  3. 长度小于等于 4294964295 (232-1)字节的字节数组

而整数值则可以是下边六种长度的一种:

  1. 4位, 介于 0~12 之间的无符号整数
  2. 1字节长的有符号整数
  3. 3字节长的有符号整数
  4. int16_t 类型的整数
  5. int32_t 类型的整数
  6. int64_t 类型的整数

每个压缩列表节点由 previous_entry_length、encoding、content 三个部分组成

压缩列表节点.png
previous_entry_length

节点的previous_entry_length 属性以字节为单位, 记录压缩列表前一个节点的长度, 可以是1字节 或者 5字节, 若前一个节点的长度＜254字节, 则 previous_entry_length 的长度为1字节, 前一个节点的长度保存在这里; 若前一节点的长度≥254字节, 则privous_entry_length 的属性为 5字节, 其中第一字节的值为 0xFE(254)

因为节点的previous_entry_length 属性记录了前一个节点的长度, 所以程序可以通过指针运算、根据当前节点的起始地址计算前一个节点的起始地址, 压缩列表的 从表尾向表头遍历 操作是使用这一原理实现的. 完整过程如下:

从尾部向头部变量压缩列表.png
encoding

节点的 encoding 属性记录了content 属性所保存的数据类型及长度,

  1. 一字节、两字节、五字节 长, 值的最高位为: 00、01 或 10 的是 字节数组编码, 这种编码表示节点的 content属性 保存着的是 字节数组, 数组长度由 编码除去最高两位之后的其它位记录
  2. 一字节长, 值的最高位以11开头的是整数编码, 这种编码表示节点的 content属性 保存的是 整数值, 整数值的类型和长度由编码除去高两位之后的其它位记录
压缩列表字节数组.png 压缩列表整型值.png
content 属性

节点的content属性 负责保存节点的值, 节点的值可以是一个字节数组或者整数、值的类型和长度由 encoding属性 来决定.

压缩列表保存字符数组示例.png 压缩列表保存整型值示例.png

连锁更新

每个节点的previous_entry_length 属性记录了前一个节点的长度, 若<254字节, 需要1字节空间保存, 若≥254字节, 需要5字节空间保存, 假设现有1压缩列表, e1 ~ eN 节点的长度都在 250~253字节之间, 此时, 若需要插入一个长度≥254字节的节点new到表头, 那么new节点将成为e1的前置节点, 因为e1的previous_entry_length属性仅1字节, 无法保存new节点的属性, 需要重新对压缩列表执行空间分配, 扩展e1节点的previous_entry_length属性, 那么麻烦事儿来了..., e1原本的长度介于250~253之间, e2.privous_entry_length可以使用1字节, 现在e1的长度为 250+4 ~ 253+4, e2就需要5字节来记录e1的长度, ...., 依次引起连锁更新, 程序需要不断扩展空间, 类似的、删除节点也可能早上连锁更新

最坏情况下、需要对压缩列表执行N次空间重分配工作, 每次空间重分配的最坏复杂度为 O(N), 所以连锁更新的最坏复杂度为 O(N²), 复杂度非常高, 但真正造成性能问题的概率很小:

所以: ziplistPush的平均时间复杂度仅为 O(N), 可以放心的使用

重点回顾

上一篇 下一篇

猜你喜欢

热点阅读