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

知识点

• 跳跃表是有序集合（zset）的底层实现之一
• redis跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点。
• 每个跳跃表节点的层高都是1到32之间的随机数
• 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点但成员对象必须是唯一但。
• 跳跃表中的节点按照分值进行大小排序，当分值相同时，节点按照成员对象的字典序大小进行排序。

跳表的搜索

例子：查找元素 117

1.比较 21， 比 21 大，往后面找
2.比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
3.比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
4.比较 85， 比 85 大，从后面找
5.比较 117， 等于 117， 找到了节点。

//跳跃表
typedef struct zskiplist {
    // header 指针指向跳跃表头结点，一旦创建后固定不变，tail 指向尾结点（当表为空时值为 NULL）
    struct zskiplistNode *header, *tail;   
    // length 记录整个跳跃表的长度，便于在 O(1) 的时间内获取表长度
    unsigned long length;                 
    // level 代表跳跃表的最高层数，初始化为1；
    int level;                 
} zskiplist;
//跳跃表节点
typedef struct zskiplistNode {
   //节点对象    是个sds 字符串  对应zset的member
    robj *obj;            
    // 分值  对应zset的score
    double score;                      
    //指向跳跃表当前结点的前一个结点的指针
    struct zskiplistNode *backward;        
    //每个跳跃表结点有一个 level 数组，数组最大长度为 32，数组元素类型为 zskiplistLevel 。它记录了每个 level 下当前结点链接到的下一个结点的前进指针 forward ，以及跨度 span
    struct zskiplistLevel {                 
        struct zskiplistNode *forward;     
        unsigned int span;                  
    } level[];
} zskiplistNode;

每个结点在创建的时候，会随机一个 [1,32] 的数 lv，作为结点的层高，并且创建 lv 个 zskiplistLevel 结构。每个结构会有一个 forward 指针 和 span 跨度

1.创建跳跃表节点
跳跃表的创建调用 zslCreate 接口，默认层数 level 为 1， 跳跃表长度 length 为 0，tail 置NULL， zslCreateNode 为创建一个跳跃表结点的接口，这里用来创建头结点，函数实现在 t_zset.c 中：

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;
}
 
zskiplist *zslCreate(void) {
    int j;
    zskiplist *zsl;
    zsl = zmalloc(sizeof(*zsl));                               
    zsl->level = 1;                                         
    zsl->length = 0;
    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;
}

2.插入跳跃表结点
跳跃表的插入有点类似链表，首先要找到一个插入位置，生成一个结点，然后修改插入位置的指针进行插入操作。结点插入的 API 为 zslInsert，整个插入过程分为以下四部分：

• 寻找插入位置；
• 随机插入结点层数；
• 生成插入结点并插入；
• 额外信息更新；
• 具体实现在 t_zset.c 中：

zskiplistNode *zslInsert(zskiplist *zsl, double score, robj *obj) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
 
    //寻找插入位置 
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward &&
          (x->level[i].forward->score < score ||
            (x->level[i].forward->score == score &&
              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;
    }
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
 
    //信息更新 
    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;
}

3.删除跳跃表结点

int zslDelete(zskiplist *zsl, double score, robj *obj) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    int i;
    //寻找待删除结点
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward &&
            (x->level[i].forward->score < score ||
                (x->level[i].forward->score == score &&
                compareStringObjects(x->level[i].forward->obj,obj) < 0)))
            x = x->level[i].forward;
        update[i] = x;
    }
    x = x->level[0].forward;
 
    // 执行结点的删除 
    if (x && score == x->score && equalStringObjects(x->obj,obj)) {
        zslDeleteNode(zsl, x, update);
        zslFreeNode(x);
        return 1;
    }
 
 
    return 0;
}