Nivelle 开拓视野冲破艰险看见世界 身临其境贴近彼此感受生活

redis深入学习之压缩列表

2017-09-09

压缩列表

压缩列表是链表建哈希键的底层实现之一.

当一个列表建只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么redis就会使用压缩列表来做列表建的底层实现.

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

image

压缩列表节点构成

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

  • 长度小于等于63字节的字节数组
  • 长度小于等于16383字节的字节数组
  • 长度小于等于4294967295字节的字节数组

整数则可以是以下六种长度的其中一种:

  • 4位长,介于0到12之间的无符号整数
  • 1字节长的有符号整数
  • 3字节的有符号整数
  • int16_t类型整数
  • int32_t类型整数
  • int64_t类型整数
previous_entry_length

记录了压缩列表中前一个节点的长度.previous_entry_lengtg 属性的长度可以是1字节或5字节:

  • 如果前一个节点长度小于254字节,那么previous_entry_length属性长度为1字节:前一个节点的长度就保存在这个字节里面
  • 如果前一个节点的长度大于等于254字节,那么previous_entry_length 属性长度为5字节:其中属性的第一个字节会被设置为0xFE,而之后的四个字节则用于保存前一个节点的长度.

encoding

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

  • 一字节,两字节或者五字节长,值得最高位为00,01或者10的是字节数组编码:这种编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录;

  • 一字节长,值的最高位以11开头的是整数编码:这种编码表示节点的content属性保存着整数值,整数值的类型和长度由编码除去最高位之后的其他位记录.

content

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

  • 编码的最高两位00表示节点保存的是一个字节数组;
  • 编码的后六位001011记录了字节数组的长度11
  • content属性保存着节点的值”hello world”
连锁更新
  • 如果前一个节点的长度小于254字节,那么previous_entry_length属性需要用1字节长的空间来保存这个长度值
  • 如果前一个节点长度大于254字节,那么previous_entry_length属性需要用5字节长的空间老保存这个长度值

评论