前言

跳跃表是一种随机化的数据，以有序的方式在层次化的链表中保存数据。

说白了，它本质上还是链表，只是由一层变为多层，由于又有有序的，这样，就是类似二分一样的思想，可以降低遍历链表的次数，时间复杂度会降下来。

查找元素，链表是O(n), 使用了跳跃表，是O(Log(n)) 。

跳跃表(skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均0 (1ogN)、最坏O(N) 复杂度的节点查找，还可以通过顺序性操作来批量处理节点。
在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

有序链表

有序链表，所有的元素以递增或者递减的方式有序的排列的数据结构，其中每个节点都有一个属性next，此属性指向下个节点，保存的是下个节点的指针，最后一个节点的next指针指向NULL。

例如，上述有序列表，我们要查找31这个元素，则需要找到1->8->11->12->26->31

一共6次比较，时间复杂度是O(n), 有序列表的插入和删除，都需要先找到目标元素，删除、修改和、插入都很快，基本不耗时，是常量，主要的时间消耗就是用来遍历比对链表中的元素。

如果我们将上述链表分层，每一层都是一个有序链表，在查找时候，从最上层开始，如果某个节点的值已经大于了要查找的值，我们就开始从下一层继续寻找。

使用分层有序链表，比如我们查找值为31的节点时，查找步骤如下：

1. 从最高层第2层开始查找，1节点比31值要小，继续向后比较。
2. 11节点比31节点要小，继续向后比较，这时会发现第2层11节点的next指针是指向NULL，所以在11节点就开始需要下降一层到第1层并继续向后查找节点进行比较。
3. 在下降到第1层中，11节点的值比31要小，继续向后比较，第1层11节点的next指针指向26，26比31要小，继续向后比较，第1层26节点的next指针指向61，61比31要大，需要下降一层继续向后比较。
4. 最后下降到了第0层，第0层的26节点的next指针指向31，31为我们要找的节点，节点被找到。

综上所述，通过将有序集合的部分节点分层，从最上层节点依次开始向后查找，如果本层的next节点大于我们要找的值或者next节点指向NULL，则从本节点开始，降低一层继续向后查找，如果找到则返回节点，否则返回NULL。采用该思想原理查找节点，在层数高及节点数量比较多时，可以跳过一些节点，查询效率会大大提升，这就是跳跃表的思想。

跳跃表的性质

• 跳跃表由很多层结构组成，最底层的节点个数为跳跃表的长度(length)。
• 跳跃表有一个头节点(header)，头节点中有一个32层的结构，每层的结构包括指向本层下个节点的指针。
• 除头节点外，层数最多的节点的层高为跳跃表的高度(level)，头节点初始化为32层，头节点中比跳跃表level层高的结构next指针指向NULL。
• 每层都是一个有序链表，数据score递增
• 除头节点header外，最底层(Level 0)的链表包含所有元素，节点每层的元素值一样，即上层有序链表中出现的元素一定会在下层有序链表中出现。
• 跳跃表拥有一个tail指针，指向跳跃表最后一个节点，且每层最后一个节点都指向NULL，表示本层有序链表的结束。

总体而言，跳跃表最底层Level 0是一个有序链表，链表中每个节点维护了多个指向其他节点的指针。跳跃表进行查找、插入、删除操作时可以跳过一些节点，快速找下操作需要的节点。

跳跃表结构

/*
 * 跳跃表链表结构
 */
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;

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

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

} zskiplist;

跳跃表节点

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

• score：是一个double类型的浮点数，用户存储有序链表节点的分值，跳跃表中的所有节点都按分值从小到大来排序。
• obj：为节点的成员对象，指向一个字符串对象，而字符串对象则保存着一个SDS值。
• backward：后退指针，用于从从表尾向表头遍历跳跃表访问节点时使用。指向跳跃表当前节点的最底层节点的前一个节点，头节点和第一个节点的backward指向NULL。
• 层(level)：为动态柔性数组，数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。每个节点层高不同对应的数组大小也不同，每次创建一个新跳跃表节点的时候，根据幂次定律 (power law，值越大出现的概率越小） 随机生成一个1～32的值，一般来说，层的数量越多，访问其他节点的速度就越快。

这level数组中的每项元素包含以下两个元素：

• forward：指向本层下一个节点，每个层都有一个指向表尾方向的前进指针 (level[i]->forward属性），用于从表头向表尾方向访问节点，尾节点的forward指向NULL。
• span：层的跨度 (level[i]->span属性） 用于记录两个节点之间的距离，即forward指向的节点于本节点之间的元素个数，span值越大，说明跳过的节点个数越多。

跳跃表的高度

对于每一个新插入的节点，都需要调用一个随机算法给它分配一个合理的层数。

// file: src/t_zset.c

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

/* Returns a random level for the new skiplist node we are going to create.
 * 返回一个随机值，用作新跳跃表节点的层数。
 * 返回值介乎 1 和 ZSKIPLIST_MAXLEVEL 之间（包含 ZSKIPLIST_MAXLEVEL），
 * 根据随机算法所使用的幂次定律，越大的值生成的几率越小。
 *
 * T = O(N)
 */
int zslRandomLevel(void) {
    int level = 1;

    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) level += 1;

    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

redis通过zslRandomLevel函数随机生成一个1～32的值，作为新建节点的高度，值越大出现的概率越低，节点高度确定后不会再修改，从上述生成节点高度代码可以看出，level的初始值为1，通过while循环，每次生成一个随机值，取这个值的低16位作为x，当x小于0.25倍的0xFFFF时，level值加1；否则return退出循环，最终返回level和ZSKIPLIST_MAXLEVEL这两者中的最小值。

Redis 跳跃表默认允许最大的层数是 32，被源码中 ZSKIPLIST_MAXLEVEL 定义，当 Level[0] 有 264 个元素时，才能达到 32 层，所以定义 32 完全够用了。