底层数据结构-ziplist

• 压缩列表，非常节约内存

  • 不必像数组那样，每个元素分配内存一样大
  • 增加了encoding字段，对不同元素分配刚刚好的大小

• 结构定义

  <zlbytes> <zltail> <zllen> <entry1> ...<entryN> <zlend>
  

  • 字段解释
    • zlbytes代表存储整个ziplist所占用的内存字节数（uint32_t类型）
    • zltail代表最后一个entry的偏移量（uint32_t类型）
    • zllen代表整个ziplist中entry的总数
      • （uint32_t类型）最大只能表示65534
      • 如果超过了，就一律为65535，实际总数需要遍历才能得到
    • zlend代表终止字节，值为0xFF
      • 这样entry首字节就不能是这个值（代码会保证）

  ##其中的entryN的定义
  <prevlen> <encoding> <entry-data>
  

  • 字段解释
    • prevlen代表前一个entry的大小
      • 前一个entry长度 < 254时，prevlen可用1个字节存储大小
      • 前一个entry长度 >= 254时，prevlen用5个字节
        • 第1字节固定为254
        • 后面4字节是小端无符号整型，用来存储大小
    • encoding代表当前entry的类型和长度
      • 如果是int，用11开头
        • ｜11000000｜跟2字节｜后16位表示int16
        • ｜11010000｜跟4字节｜后32位表示int32
        • ｜11100000｜跟8字节｜后64位表示int64
        • ｜11110000｜跟3字节｜后18位表示有符号整型
        • ｜1111xxxx｜总长1字节，后4位表示0-12的整数
        • ｜11111110｜跟1字节｜后8位表示有符号整型
      • 如果是string，用其他开头
        • ｜00pppppp｜后6位最多可表示长度63
        • ｜01pppppp｜qqqqqqqq｜后14位最多表示长度16383
        • ｜10000000｜ 跟4字节｜后32位最多表示长度2^32 - 1
    • entry-data用于存储真实数据
      • 但对于int，没有此字段
      • 会被合并到encoding来表示

• 缺点

  • 插入扩容时不预留内存空间
  • 移除节点时不保留原有空间
  • 这样导致每次写操作都会进行内存分配
  • 节点如果扩容并越过了254字节这个边界线，可能会导致链式传导，但极限也就5次