redis数据结构之『跳跃列表』

介绍

跳跃表在 Redis 中不如链表和字典等数据结构的应用广泛，只有两个地方用到。一是实现有序集合键，另一个是在集群节点中用作内部数据结构。

项目地址：https://github.com/lishq/redis-base-demo

• Redis 的 zset 是一个复合结构
• 需要hash存储value和score的关系
• 需要提供按照 score 来排序的功能
• 需要能够指定 score 的范围来获取 value 列表的功能，「跳跃列表」

数据结构

• Redis 的跳跃表共有 64 层
• 最底层双向链表，保证数据存储，有序排列
• 不同的 kv 层高可能不一样，层数越高的 kv 越少
• 每一个层元素的遍历都是从 kv header 出发

struct zslnode {
  string value;
  double score;
  zslnode*[] forwards;  // 多层连接指针
  zslnode* backward;  // 回溯指针
}

struct zsl {
  zslnode* header; // 跳跃列表头指针
  int maxLevel; // 跳跃列表当前的最高层
  map<string, zslnode*> ht; // hash 结构的所有键值对
}

查找过程

• 二分查找
• 逐层下降，搜索路径

随机层数

• 对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数。直观上期望的目标是 50% 的 Level1，25% 的 Level2。
• 跳跃列表会记录一下当前的最高层数maxLevel，遍历时从这个 maxLevel 开始遍历

插入过程

• 查找到位置，如果score相等判断value
• 创建节点，分配随机层数
• 将搜索路径上的节点和新节点通过前后指针串起来

删除过程

• 类似插入过程
• 同时还要注意更新一下最高层数maxLevel

排名计算

• 每一个 forward 指针都增加了 span 属性
• 将「搜索路径」上的经过的所有节点的跨度 span 值进行叠加就可以算出元素的最终 rank 值