跳跃表

跳跃表是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

在大多数情况下，跳跃表的效率可以和平衡树相媲美，并且跳跃表的实现比平衡树简单，所以不少程序都是用跳跃表代替平衡树。

1. 跳跃表的实现

Redis的跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义，其中zskiplistNode表示跳跃表节点，zskiplist保存跳跃表节点的相关信息，如节点的数量，指向表头节点和表尾节点的指针等。

一个跳跃表

1.1 跳跃表节点

跳跃表节点实现由redis.h/zskiplistNode结构定义。

type struct zskiplistNode{
    // 层
    struct zskiplistLevel{
        // 前进指针
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;
    } level[];

    // 后退指针
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成员对象
    robj *obj;
} zskiplistNode;

1. 层

   跳跃表节点的level数组包含的每个元素都包含一个指向其他节点的指针。程序可以通过这些层来加快访问其他节点的速度。

   创建一个新跳跃节点时，程序都根据幂次定律（越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小。

   如下面是带有不同层高的节点。

   带有不同层高的节点

   前进指针：每个层都有一个指向表尾方向的前进指针(level[i].forward)，用于从表头向表尾方向访问节点。

   跨度：

   • level[i].span，用于记录两个节点之间的距离。两个节点之间的跨度越大，它们相距就越远；指向NULL的所有前进指针的跨度都为0，因为它们没有连向任何节点。
   • 跨度实际上是用来计算排位的：在计算某个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。遍历操作使用前进指针就可以完成，不需要跨度。

   如下面是计算节点的排位的举例，虚线标记在跳跃表中查找分值为3.0、成员对象为O3的节点时，沿途经历的层：查找的过程只经过了一个层，层的跨度为3，所以目标节点在跳跃表中的排位为3。

   计算节点的排位

   后退指针：用于从表尾向表头访问节点，每个节点只有一个后退指针，每次只能后退到前一个节点。

   分值和成员：

   • 分值score，是一个double，跳跃表中所有节点都按分值从小到大排序。
   • 成员对象obj，指向一个字符串对象，字符串对象保存着一个SDS值。

   分值相同的节点会按照成员对象在字典序中的大小来进行排序，成员对象较小的节点排在前面。

1.2 跳跃表

使用zskiplist结构可以快速处理跳跃表。

typedef struct zskiplist{

    // 表头节点和表尾节点
    structz skiplistNode *header, *tail;

    // 表中节点的数量
    unsigned long length;

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

level属性用于在O(1)内获取跳跃表中层高最大的那个节点的层数量，表头节点的层高并不计算在内。

表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值、成员对象，不过表头节点的这些属性不会被用到，在上面第一张图中就省略了这些内容。

2. 跳跃表API

函数	作用	时间复杂度
zslCreate	创建一个新的跳跃表	O(1)
zslFree	释放给定跳跃表，以及表中包含的所有节点	O(N)，N为跳跃表的长度
zslInsert	将包含给定成员和分值的新节点添加到跳跃表中	平均O(logN)，最坏O(N)，N为跳跃表长度
zslDelete	删除跳跃表中包含给定成员和分值的节点	平均O(logN)，最坏O(N)，N为跳跃表长度
zslGetRank	返回包含给定成员和分值的节点在跳跃表中的排位	平均O(logN)，最坏O(N)，N为跳跃表长度
zslGetElementByRank	返回跳跃表在给定排位上的节点	平均O(logN)，最坏O(N)，N为跳跃表长度
zslIsInRange	给定一个分值范围（range），如0-15，如果跳跃表中至少有一个节点的分值在这个范围内，那么返回1，否则返回0。	通过跳跃表的表头节点和表尾节点，这个检测可以用O(1)完成。
zslFirstInRange	给定一个分值范围，返回跳跃表中第一个符合这个范围的节点	平均O(logN)，最坏O(N)，N为跳跃表长度
zslLastInRange	给定一个分值范围，返回跳跃表中最后一个符合这个范围的节点	平均O(logN)，最坏O(N)，N为跳跃表长度
zslDeleteRangeByScore	给定一个分值范围，删除跳跃表中所有在这个范围之内的节点	O(N)，N为被删除的节点数量
zslDeleteRangeByRank	给定一个排位范围，删除跳跃表中所有在这个范围之内的节点	O(N)，N为被删除的节点数量