跳跃表

什么是跳跃表

跳跃表（skiplist）是一种随机化的数据， 由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出， 跳跃表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳跃表的实现要简单直观得多。

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

在大部分情况下，跳跃表的效率可以和平衡树相媲美，并且因为跳跃表的实现比平衡树要来得更为简单，所以有不少程序都使用跳跃表来代替平衡树。Redis使用跳跃表作为有序集合键的底层实现之一，如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员（member）是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。

在了解跳跃表之前，我们先了解一下有序链表。有序链表是所有元素以递增或递减方式有序排列的数据结构，其中每个节点都指向下个节点的next指针，最后一个节点的next指针指向NULL。

使用单有序链表，如果要查询31的元素，需要从第一个元素开始依次向后查询、比较才可以找到，找到顺序为1->8->11->12->26->31，共6次比较，时间复杂度为O(N)。有序链表的插入和删除操作都需要先找到合适的位置在修改next指针，修改操作基本不耗费时间，所以插入、删除、修改有序链表的耗时主要在查找元素上。

如果我们将有序链表的部分节点分层，每一层都是一个有序链表。在查找时优先从最高层开始向后查找，当到达某节点时，如果next节点值大于要查找的值或next指针指向NULL，则从当前节点下降一成继续向后查找，这样是否可以提升查询效率呢？

使用分层有序链表，比如我们查找值为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。采用该思想原理查找节点，在层数高及节点数量比较多时，可以跳过一些节点，查询效率会大大提升，这就是跳跃表的思想。

跳跃表性质

1、跳跃表由很多层结构组成，最底层的节点个数为跳跃表的长度(length)。

2、跳跃表有一个头节点(header)，头节点中有一个32层的结构，每层的结构包括指向本层下个节点的指针。

3、除头节点外，层数最多的节点的层高为跳跃表的高度(level)，头节点初始化为32层，头节点中比跳跃表level层高的结构next指针指向NULL。

4、每层都是一个有序链表，数据score递增

5、除头节点header外，最底层(Level 0)的链表包含所有元素，节点每层的元素值一样，即上层有序链表中出现的元素一定会在下层有序链表中出现。

6、跳跃表拥有一个tail指针，指向跳跃表最后一个节点，且每层最后一个节点都指向NULL，表示本层有序链表的结束。

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

跳跃表结构与节点

跳跃表结构

跳跃表的结构体zskiplist，定义如下：

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

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

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

} zskiplist;

该结构体属性如下：

header：指向跳跃表头节点。头节点时跳跃表的特殊节点，他的level是固定数组元素个数为32个，头节点不存储任何score和obj，level也不计入跳跃表的高度，头节点在初始化时，score值为0，ele值为NULL，32个元素的forward值都指向NULL，span为0.

tail：指向跳跃表尾节点。

length：跳跃表长度，表示第0层除头节点以外的所有节点总数。

level：跳跃表高度，除头节点外，其他节点层数最高的即为跳跃表高度。

注意表头节点和其他节点的构造是一样的：表头节点也有后退指针、分值和成员对象，不过表头节点的这些属性都不会被用到。

跳跃表节点

位于zskiplist结构的zskiplistNode结构定义及属性如下：：

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 完全够用了。

创建跳跃表

创建跳跃表的步骤：

1、创建跳跃表结构体对象zsl。

2、初始化跳跃表结构体对象的值：level=1，长度=0，tail指针指向NULL。

3、初始化跳跃表zsl的header头节点，循环初始化头节点ZSKIPLIST_MAXLEVEL的level动态柔性数组zskiplistNode元素。

// file: src/t_zset.c
/*
 * 创建一个层数为 level 的跳跃表节点，
 * 并将节点的成员对象设置为 obj ，分值设置为 score 。
 *
 * 返回值为新创建的跳跃表节点
 *
 * T = O(1)
 */
zskiplistNode *zslCreateNode(int level, double score, robj *obj) {
    // 分配空间    
    zskiplistNode *zn = zmalloc(sizeof(*zn) + level * sizeof(struct zskiplistLevel));

    // 设置属性
    zn->score = score;
    zn->obj = obj;    
    return zn;
}

/*
 * 创建并返回一个新的跳跃表
 *
 * T = O(1)
 */
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;

    // 分配空间
    zsl = zmalloc(sizeof(*zsl));

    // 设置高度和起始层数
    zsl->level = 1;
    zsl->length = 0;

    // 初始化表头节点
    // T = O(1)
    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL, 0, NULL);
    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
        zsl->header->level[j].forward = NULL;
        zsl->header->level[j].span = 0;
    }
    zsl->header->backward = NULL;

    // 设置表尾
    zsl->tail = NULL;

    return zsl;
}

跳跃表插入节点

插入节点的步骤：

1、遍历跳跃表，在各个层查找节点的插入位置

2、获取一个随机值作为新节点的层数，调整跳跃表高度

3、创建并插入新的节点

4、设置新节点的后退指针backward

// file: src/t_zset.c

/*
 * 创建一个成员为obj，分值为score的新节点，并将这个新节点插入到跳跃表zsl中，函数的返回值为新节点。
 */
zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    // 在各个层查找节点的插入位置
    // T_wrost = O(N^2), T_avg = O(N log N)
    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i--) {
        rank[i] = i == (zsl->level - 1) ? 0 : rank[i + 1];
        // T_wrost = O(N^2), T_avg = O(N log N)
        while (x->level[i].forward && (x->level[i].forward->score < score ||
               // 比对分值
               (x->level[i].forward->score == score &&
               // 比对成员如果score相同时，比较member，其实就是map的key排序
               compareStringObjects(x->level[i].forward->obj, obj) < 0))) 
		{
            
            rank[i] += x->level[i].span;  // 记录沿途跨越了多少个节点
            x = x->level[i].forward;      // 移动至下一指针
        }
        // 记录将要和新节点相连接的节点
        update[i] = x;
    }

    // 调整跳跃表高度
    level = zslRandomLevel();   // 获取一个随机值作为新节点的层数
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        // 更新表中节点最大层数
        zsl->level = level;
    }

    // 创建并插入新的节点
    x = zslCreateNode(level, score, obj);
    for (i = 0; i < level; i++) {
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        // 计算新节点跨越的节点数量
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }

    /* increment span for untouched levels */
    // 未接触的节点的 span 值也需要增一，这些节点直接从表头指向新节点
    // T = O(1)
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    // 设置新节点的后退指针backward 
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;

    zsl->length++;
    return x;
}

删除跳跃表节点

// file: src/t_zset.c

/* 
 * 内部删除函数，T = O(1)
 */
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) 
{
    int i;

    // 更新所有和被删除节点 x 有关的节点的指针，解除它们之间的关系
    // T = O(1)
    for (i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            update[i]->level[i].span += x->level[i].span - 1;
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            update[i]->level[i].span -= 1;
        }
    }

    // 更新被删除节点 x 的前进和后退指针
    if (x->level[0].forward) {
        x->level[0].forward->backward = x->backward;
    } else {
        zsl->tail = x->backward;
    }

    // 更新跳跃表最大层数（只在被删除节点是跳跃表中最高的节点时才执行）
    while (zsl->level > 1 && zsl->header->level[zsl->level - 1].forward == NULL) zsl->level--;

    // 跳跃表节点计数器减一
    zsl->length--;
}

删除跳跃表

/* 
 * 从跳跃表 zsl 中删除包含给定节点 score 并且带有指定对象 obj 的节点。
 * T_wrost = O(N^2), T_avg = O(N log N)
 */
int zslDelete(zskiplist *zsl, double score, robj *obj) 
{
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;

    // 遍历跳跃表，查找目标节点，并记录所有沿途节点
    // T_wrost = O(N^2), T_avg = O(N log N)
    x = zsl->header;
    for (i = zsl->level - 1; i >= 0; i--) {
        // 遍历跳跃表的复杂度为 T_wrost = O(N), T_avg = O(log N)
        while (x->level[i].forward && (x->level[i].forward->score < score ||
              // 比对分值
              (x->level[i].forward->score == score &&
              // 比对对象，T = O(N)
              compareStringObjects(x->level[i].forward->obj, obj) < 0)))

            // 沿着前进指针移动
            x = x->level[i].forward;

        // 记录沿途节点
        update[i] = x;
    }

    /* We may have multiple elements with the same score, what we need
     * is to find the element with both the right score and object.
     *
     * 检查找到的元素 x ，只有在它的分值和对象都相同时，才将它删除。
     */
    x = x->level[0].forward;
    // if (x && score == x->score && equalStringObjects(x->obj, obj)) {
    //     // T = O(1)
    //     zslDeleteNode(zsl, x, update);
    //     // T = O(1)
    //     zslFreeNode(x);
    //     return 1;
    // } else {
    //     return 0; /* not found */
    // }

    return 0; /* not found */
}

跳跃表API