一、 简介

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均O（logN）、最坏O（N）复杂度的节点查找，还可以通过顺序性操作来批量处理节点。

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。

二、Redis 中的跳跃表 SkipList

image-20210804141243020.png

2.1、Redis 中zskiplistNode结构定义

  1. typedef struct zskiplistNode {
  2.     //层: level是一个数组，在创建跳跃表节点的时候，程序都根据幂次定律（power law，
  3.     //越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度”
  4.     struct zskiplistLevel {
  5.         //前进指针
  6.         struct zskiplistNode *forward;
  7.         //跨度： 用于记录两个节点之间的距离
  8.         unsigned int span;
  9.     } level[];
  10.     //后退指针
  11.     struct zskiplistNode *backward;
  12.     //分值: 在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：
  13.     //分值相同的节点将按照成员对象在字典序中的大小来进行排序
  14.     double score;
  15.     //成员对象
  16.     robj *obj;
  17. } zskiplistNode;

2.2、Redis 中 zskiplist 结构的定义

  1. typedef struct zskiplist {
  2.     //表头节点和表尾节点
  3.     structz skiplistNode *header, *tail;
  4.     //表中节点的数量
  5.     unsigned long length;
  6.     //表中层数最大的节点的层数
  7.     int level;
  8. } zskiplist;

2.3、跳跃表的查找过程

image-20210804145430502.png

  • 1、从跳跃表的头节点开始遍历
  • 2、如果当前节点的key与 查询的key 相等，那么返回当前节点
  • 3、如果当前节点的key 小于 查询的key ，那么继续沿着当前层级查找
  • 4、如果当前节点的key 大于 查询的key，那么当前层级没有查找的key ，需要往下一层级查找
  • 5、没有找到，则返回null

2.4、跳跃表的删除过程

image-20210804152328847.png

  • 删除操作主要是找到目标节点的前置节点，然后删除目标节点的关联
  • 1、从头节点出发
  • 2、如果当前节点 的 右节点为空，则往下一层级查找需要删除的目标节点
  • 3、如果当前节点的右节点 key 小于 删除节点 key ，则沿着当前层级遍历
  • 4、如果当前节点的右节点 key 等于 删除节点 key ，则 删除目标节点的关联，node.right = node.right.right
  • 5、如果当前节点的右节点 key 大于 删除节点 key ，则往下一个层级遍历

2.5、跳跃表的插入过程

image-20210804155702786.png

image-20210804155727630.png

  • 插入的过程中，需要考虑每一层的待插入左节点的记录
  • 1、从头节点出发
  • 2、找到待插入的左节点，插入待插入节点到链表中
  • 3、插入完这一层，需要考虑上一层是否插入，首先判断当前索引层级，如果大于最大值那么就停止(比如已经到最高索引层了)。否则设置一个随机数1/2的概率向上插入一层索引(因为理想状态下的就是每2个向上建一个索引节点)。
  • 4、重复步骤3，直到概率退出或者索引层数大于最大索引层。

总结

  • 跳跃表是有序集合的底层实现之一。
  • 每个跳跃表节点的层高都是1至32之间的随机数。
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
  • 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。

参考