跳跃表和整数集合

跳跃表

• 跳跃表是一种有序的数据结构
• redis的有序集合使用跳跃表作为底层实现之一
• redis的跳跃表由zskiplistNode和zskiplist两个结构定义
  • zskiplistNode结构用于表示跳跃表节点
  • zskiplist结构则用于保存跳跃表节点的相关信息，比如节点数量，指向表头节点和表尾节点的指针等等

结构定义

• header:指向跳跃表的表头节点
• tail:指向跳跃表的表尾节点
• level: 记录目前跳跃表内，层数最大的那个节地层数【表头节点不算】
  • 说明一点，每次创建一个新的节点时，会随机生成一个1到32之间的层级
• length: 记录跳跃表的长度，也就是跳跃表节点的数量【表头不计算在内】
• level结构的两个属性:前进指针和跨度
• 后退指针：从表尾向表头遍历时使用，但是只能一个一个节点后退
• 成员对象：每个节点保存一个元素，说明一点，这个成员对象指向一个SDS字符串对象。

整数集合

• 整数集合是集合键的底层实现之一，当集合只包含整数值元素并且元素数量不多时，redis 才会使用整数集合作为集合键的底层实现
• 类型值范围
  • int16 【-32768, 32767】
  • int32 【-2147483648 ，2147483648 】
  • int64 【-922337203654775808，922337203654775808】

结构定义

• contents：底层实现是数组，数值由小到大的排列，该属性的int8_t 类型的声明，不取决该值，而真正的类型取决于encoding属性的值
• encoding: 记录着contents 数组真正的类型
• contents数组真正的大小为：length * 类型 = 多少位，例如：int16_t 类型，长度为3【 3 * 16 = 48位】

升级

• 当需要新增元素时，并且新元素的类型比整数集合元素现有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合中里面

• 步骤

  • 第一：根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
  • 第二：将底层数组现有所有元素都转成新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要维持底层数组的有序性不变
  • 第三：将新元素添加到底层数组里面

• 举例说明：目前整数集合有三个元素 1，2，3 ，现在需要将65535 这个元素加进去。

  • 首先根据我们类型的访问65535 这个值在int32 类型中，现在我们使用的int16 类型，所以需要对该整数集合进行升级
  • 因为每一个int32 整数集合需要占位32位空间，所以底层数组的大小将是 32 * 4 = 128 位

升级步骤图

最后将整数集合encoding 属性的值int16变为int32 ,并将length属性的值从3改为4

降级

• 整数集合不支持降级操作，一旦对数组进行升级后，编码就会一直保持升级后的状态
• 例如：整数集合中存在一个int64位的数据，那这个整数集合类型为int64，如果将为64位长度的元素删除了，整数集合仍然会编码位int64类型

redis为什么不支持降级？

因为来回升降级会引起性能问题，所以redis 采用的忽略降级的策略