第 5 章 跳跃表

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构。
之前在学习数据结构的时候有接触到跳跃表，看图：

跳表.png

跳表有点像二分法，链表的二分法，Redis 中的跳表使用双向链表实现

node of skiplist

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

level

每次创建一个新跳表节点时，程序都会根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于 1 和 32 之间的值作为 level 数组的大小，这个大小就是层的“高度”。

forward

遍历跳表中所有节点的方式：从 header 节点开始，再从当前节点的最高层向下，当遇到第一个跨度为 1 的层后，遍历下一个节点。伪代码如下：

void reverseSkiplistNode(zskiplistNode *header) {
  while(header != null) {
    printf(header.obj);
    int height = header.level.length;
    for (int i = height - 1; i > 0 ; i ++){
      if (header.level[i].span == 1) {
        header = header.level[i].forward;
        break;
      }
    }
  }
}

span

跨度是用来计算排位（rank）的：在查找某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳表中的排位。

score & obj

节点的分值是一个 double 类型的浮点数，跳表中的所有节点都按分值从小到大来排序。

节点的成员对象是一个指针，它指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

在同一个跳表中，各个节点保存的成员对象必须是唯一的，但是多个节点保存的分值却可以是相同的：分支相同的节点将按照成员对象在字典序中的大小来进行排序，成员对象较小的节点会排在前面，而成员对象较大的节点则会排在后面。看图：

有序集合.png

zskiplist

typedef struct zskiplist  {
  // 表头、尾节点
  structz skiplistNode *header, *tail;
  
  // 表中节点的数量
  unsigned long length;

  // 表中最大的层数
  int level;
} zskiplist;

level 属性用于在 O(1) 复杂度内获取跳表中最大的层数，注意表头节点的层高并不计算在内。