redis 压缩链表

redis 压缩链表

概述

压缩链表是相对于普通链表而言的

当普通链表的数据越来越多, 链表查询性能会低效

当存储的数据较少时, 使用链表存储会浪费空间

压缩链表本质上是一个字符串

压缩链表内存储的数据只能是 整型, 字符串

压缩链表结构

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

• entryN

  • header 头部

    • 前置节点编码规则 (前置节点的长度, 从后向前遍历时用)

      如果前置节点长度小于 ZIP_BEGIN 字节(254), 则使用 1 个字节表示长度
      如果前置节点大于等于 ZIP_BEGIN 字节(254), 则使用 5 个字节表示长度
      a) 第 1 个字节为 ZIP_BEGIN, 表示这是一个 5 字节长度
      b) 之后的 4 个字节表示长度
      

    • 当前节点编码规则 (当前节点的长度)

      整数

      前 2 位为 1

      编码长度为 1 字节

      表示	说明	备注
      1100 0000	表示 2 字节长度	0xc0 位或 0<<4
      1101 0000	表示 4 字节长度	0xc0 位或 1<<4
      1110 0000	表示 8 字节长度	0xc0 位或 2<<4
      1111 0000	表示 3 字节长度	0xc0 位或 3<<4
      1111 1110	表示 1 字节长度	0xfe
      1111 xxxx (除去 0000, 1111)	表示 (xxxx – 1) 位长度
      1111 1111	压缩链表结束符

      字符串

      前 2 位不是 11

      前 2 位用来表示字符串所占用的字节

      编码长度为 1字节, 2字节, 5字节

      表示	说明	备注
      00pp pppp	1字节, 表示字符串长度小于等于 2^6 -1	前 2 位不用来表示长度
      01pp pppp qqqq qqqq	2字节, 表示字符串长度小于等于 2^14 – 1	前 2 位不用来表示长度
      10pp pppp qqqq qqqq …	5字节, 表示字符串长度大于等于 2^14	前 2 位不用来表示长度

  • body 数据部分

    // ziplist 节点信息的结构
    typedef struct zlentry {
        // prevrawlen ：前置节点的长度
        // prevrawlensize ：编码 prevrawlen 所需的字节大小
        unsigned int prevrawlensize, prevrawlen;
        // len ：当前节点值的长度
        // lensize ：编码 len 所需的字节大小
        unsigned int lensize, len;
        // 当前节点 header 的大小
        // 等于 prevrawlensize + lensize
        unsigned int headersize;
        // 当前节点值所使用的编码类型
        unsigned char encoding;
        // 指向当前节点的指针
        unsigned char *p;
    } zlentry;
    

    注意

    ziplist 对于长度的存储编码, 当要使用长度的时候对长度进行解码, 放于 entry 实体的 prevrawlen 与 len 均为实际的长度值, prevrawlensize 与 lensize 为对实际长度进行编码所占的字节数
    

ziplist 宏定义 (src/ziplist.c)

ziplist api (src/ziplist.c)