Redis 入门-第四篇-数据结构与对象-跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其它节点的指针，从而达到快速访问节点的目的。Redis 使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，或者有序集合中的元素的成员（member）是比较长的字符串时，Reids 就会使用跳跃表来作为有序集合键的底层实现。

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

跳跃表的实现：

Redis 的跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义：

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

typedef struct zskiplist {
  struct zskiplistNode *header, *tail; // 表头结点和表尾节点的指针
  unsigned long length;                // 表中节点的数量（表头节点不计算在内）
  int level;                           // 表中最大层数（表头节点不计算在内）
}

1. 层：跳跃表节点的 level 数组可以包含多个元素，每个元素都包含一个指向其它节点的指针，程序可以通过这些层来加快访问其他节点的速度，一般来说，层的数量越多，访问其它节点的速度就越快。每次创建一个新跳跃表节点的时候，程序都根据幂次定律（越大的数出现的概率越小）随机生成一个介于 1 ~ 32 之间的值作为 level 数组的大小，这就是层的高。
2. 前进指针：每个层都有一个指向表尾方向的前进指针 (level[i].forward 属性)，用于从表头向表尾方向访问节点。
3. 跨度：(level[i].span) 用于记录两个节点之间的距离，跨度是用来计算节点的排位的，在查找某个节点的过程中，将沿途访问过的所有层的跨度加起来，得到的结果就是目标节点在跳跃表中的位置。
4. 后退指针：用于从表尾向表头方向访问节点。
5. 分值和成员：跳跃表中的节点都是按分值从小到大排列的，成员对象是一个指针，指向一个字符串对象，而字符串对象则保存着一个 SDS 值。

在同一个跳跃表中，各个节点保存的成员对象必须唯一，但是节点保存的分值可以相同，分值相同的节点将按成员对象在字典序中的大小来排序。