• 前言
• 1. 跳跃表
  • 1.1 跳跃表与其节点的定义
  • 1.2 跳跃表的API
• 2. 整数集合
  • 2.1 整数集合的实现
  • 2.2 整数集合的类型升级
  • 2.3 整数集合的API
• 3. 压缩列表
• 3.1 压缩列表的结构
  • 3.2 压缩列表节点的定义
  • 3.3 连锁更新
  • 3.4 压缩列表的API
• 最后

前言

参考资料：《Redis设计与实现 第二版》；

本篇笔记按照书里的脉络，将知识点分为四个部分。其中第一部分数据结构与对象分为上中下篇，上篇包括：SDS、链表和字典；中篇包括跳跃表、整数集合和压缩列表；下篇为对象；

上篇的链接：

1. 跳跃表

• 跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点；
• 跳跃表的效率可以媲美平衡树，实现比平衡树简单；
• 跳跃表在Redis里只有两个应用：有序集合键的底层实现、集群节点中用作内部数据结构；

1.1 跳跃表与其节点的定义

• 跳跃表的定义，在redis.h/zskiplist结构里：

  typedef struct zskiplist {
      //表头节点和表尾节点
      structz skiplistNode *header, *tail;
      //表中节点的数量（不包括表头指针）
      unsigned long length;
      //表中层数最大的节点的层数（不包括表头指针）
      int level;
  } zskiplist;
  

• 跳跃表节点的定义，在redis.h/zskiplistNode结构里：

  typedef struct zskiplistNode{
      //后退指针
      struct zskiplistNode *backwars;
      //分值
      double score;
      //成员对象
      robj *obj;
      //层
      struct zskiplistLevel{
          //前进指针
          struct zskiplistNode *forward;
          //跨度
          unsigned int apan;
      } level[];
  } askiplistNode;
  

  • 节点中使用L1、L2、L3等来标记节点的各个层，每个层有前进指针和跨度；
    • 带数字的箭头为前进指针，数字为跨度；
    • 一般来说，层数越多访问其他节点速度越快；
    • 创建新跳跃表节点时，随机生成介于1和32之间的数作为level数组的大小；
    • 跨度与遍历无关，与排位rank有关。查找某个节点时，将沿途层相加，得到排位；
  • 带BW字样的为后退指针；
  • 1.0、2.0、3.0为分值，分值从小到大排列；
    • 当分值相同时，成员对象在字典中排序小的靠近表头节点；
  • o1、o2、o3等是成员对象，成员对象必须唯一；
  • 表头节点也有后退指针、分值和成员对象，不会用到所以图中没有显示；
  • 下图中level为5是因为o3对象有5层，为该跳跃表中最大层；
    

1.2 跳跃表的API

2. 整数集合

• 整数集合 intset，其特点是从小到大保存整数且不会重复；
• 整数集合在Redis里的应用：集合键的底层实现；

2.1 整数集合的实现

• 整数集合的定义，在intset.h/intset结构中：

  typedef struct intset{
      //编码方式
      uint32_t encoding;
      //集合包含的元素数量
      uint32_t length;
      //保存元素的数组
      int8_t contents[];
  } intset;
  

  • contents声明为 int8_t 类型的数组，但数组的真正类型取决于encoding属性的值；

  encoding值	contents值	范围
  INTSET_ENC_INT16	int16_t	-32768~32768
  INTSET_ENC_INT32	int32_t	-2147483648~2147483647
  INTSET_ENC_INT64	int64_t	-9223372036854775808~9223372036854775807

2.2 整数集合的类型升级

• 当新增的元素类型比整数集合现有元素的类型长时，需要升级；
• 步骤：
  • 根据新元素类型，扩展整数集合底层数组空间大小，并为新元素分配空间；
  • 将底层数组现有元素转换成新元素相同的类型，在维持集合有序性质不变情况下将转换后的元素放置到正确位置上；
  • 将新元素添加到底层数组里；
• 因为添加新元素可能会引起升级，每次升级需要对所有元素进行类型转换，因此时间复杂度为O(N)；
• 因为引起升级操作的新元素比现有元素长，所以新元素要么添加到数组开头，要么数组末尾；
• 好处：
  • 灵活性：C语言通常不会将不同类型值放在同一个数据结构里，Redis的升级使其可以；
  • 节约内存；
• 整数集合不允许降级操作；

2.3 整数集合的API

3. 压缩列表

• 压缩列表 ziplist，其特点是管理小整数值和短字符串；
• 压缩列表在Redis里的应用：列表键与哈希键的底层实现之一；
• 压缩列表的Redis为节省内存而开发的，是由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构；

3.1 压缩列表的结构

• 压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构；
  
  

3.2 压缩列表节点的定义

• 节点的定义在ziplist.c/zlentry结构里：

  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;
  

  • 可以用当前节点地址减去prevrawlen的值获得前置节点的首地址，可以由此实现从尾到头的遍历；
  • *p指向一个content，保存节点的值，值的类型和长度由encoding决定；
  • encoding的属性（下划线表示留空，abcdx代表实际二进制数据）：

3.3 连锁更新

• 首先，压缩列表节点有个prevrawlen属性，用于记录前一个节点的长度，前一个节点的长度变化会影响prevrawlen属性的长度取值（使用1个字节存储前一个节点的长度还是5个）；
• 假设所有结点（e1, e2......eN）长度介于250_{253字节之间，在表头新增长度大于等于254字节的new节点，因为e1的`prevrawlen`属性仅1字节，无法保存大于254的数字（new的长度），因此需要扩展为5字节长，此时e1的长度介于254}257字节之间。这样，new引发e1的扩展，e1引发e2的扩展，形成连锁更新；
• 删除节点也可能引发连锁更新；
• 连锁更新的最坏时间复杂度为 O(N²)；
• 在实际中，连锁更新造成的性能问题几率很低；

3.4 压缩列表的API

• 最坏时间复杂度为O(N²)是因为可能引发连锁更新；

最后

新人制作，如有错误，欢迎指出，感激不尽！ 欢迎关注公众号，会分享一些更日常的东西！ 如需转载，请标注出处！