Redis 数据结构 跳表(skiplist)

跳表是一种数据结构，不过奇怪的是大学时数据结构的课本上没有介绍过这种数据结构，但最近几年在实际工作时又经常接触到。
跳表可以支持快速地插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树（Red-black tree）。

(1) 跳表

(1.1) 跳表介绍

我理解跳表是加了索引的链表。

对于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。

那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会更快一些呢？

(1.2) 跳表的时间复杂度

算法的执行效率可以通过时间复杂度来度量。

在一个单链表中查询某个数据的时间复杂度是 O(n)。那在一个具有多级索引的跳表中，查询某个数据的时间复杂度是多少呢？

每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2k)。 有点类似二叉树

在这种情况下，跳表比较类似二叉树，这么抽象来看地话，跳表中查询任意数据的时间复杂度是 O(logN)。

(1.3) 跳表的空间复杂度

比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。那到底需要消耗多少额外的存储空间呢？

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。
类似二叉树，跳表的空间复杂度是 O(N)。

用数学公式证明

假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。如果我们把每层索引的结点数写出来，就是一个等比数列。

这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。

(1.4) 跳表插入节点

链表插入节点时，找到前驱节点，插入节点即可。
跳表插入节点时也是类似，只不过改了最下面那层链表后，还需要把索引也更新。相当于多更新几个节点而已。

(1.5) 跳表删除节点


链表删除节点时，找到前驱节点和后继节点，断开当前节点的链接，让前驱指向后继节点即可。
跳表删除节点也是类似，只不过同时需要把索引上的也删除了。

(1.6) 跳表查找节点

链表查找节点需要遍历。
跳表是加了索引的链表，类似二叉树，查找时先用索引查找，再一步一步往下，有点类似二叉树遍历。

(2) 自己实现一个跳表

我理解的是，跳表是加了索引的链表，所以跳表的很多操作可以抽象成链表操作的优化版。
比如 链表查询需要遍历，时间复杂度是0(N)，跳表查询可以利用索引，时间复杂度O(logN)
链表插入数据需要遍历，然后插入，时间复杂度O(N) 跳表查询，然后插入，时间复杂度O(logN)

(2.1) 跳表和跳表节点定义

public class Skiplist {

    // 头结点
    private SkipListNode head = null;

    // 当前层级
    private int currMaxLevel = 0;

    // 最高层数
    private static final int MAX_LEVEL = 32;

    // 
    private static final double SKIPLIST_P = 0.25;

}

/**
 * 跳表节点
 */
class SkipListNode {
    // 跳表节点的值
    public int val;
    
    // 下一个节点  每层指向的下一个节点不一样
    // 类似链表的next节点 只不过有多层
    public SkipListNode[] nexts;

    public SkipListNode() {
    }

    public SkipListNode(int val, int level) {
        this.val = val;
        this.nexts = new SkipListNode[level];
    }

}

(2.2) 新建跳表

public Skiplist() {
    // 头结点很重要
    this.head = new SkipListNode(-1, MAX_LEVEL);
    this.currMaxLevel = 0;
}

(2.3) 跳表新增节点

跳表新增元素抽象成链表新增节点，只不过链表只需要增加一个，而跳表需要在多层新增，抽象成多个单链表新增节点。

/**
 * 添加前只找到要添加节点的每层前驱
 * 每层插入节点，更新节点next，更新前驱节点的next
 */
 public void add(int num) {
    // 插入时需要更新多层
    SkipListNode[] updateLevelNodes = new SkipListNode[MAX_LEVEL];
    Arrays.fill(updateLevelNodes, head);

    // 第一次指向的是头结点
    SkipListNode curr = this.head;
    // 每一层需要更新的节点
    for (int i = currMaxLevel - 1; i >= 0; i--) {
        // 第一次指向的是头结点
        //curr = updateLevelNodes[i]; // 每次从头找会退化成单链表查找，时间复杂度比较高O(n)，可以根据上层的结果来找，这样才是log(n)
        // 遍历当前层级链表
        while (curr.nexts[i] != null && curr.nexts[i].val < num) {
            // 指向当前层级(链表)的下一个节点
            curr = curr.nexts[i];
        }
        // curr.val < num
        // curr节点是num的前驱节点
        updateLevelNodes[i] = curr;
    }

    // 节点 要插入的层数
    int randomLevel = getRandomLevel();
    //System.out.println("randomLevel="+randomLevel);
    SkipListNode newNode = new SkipListNode(num, randomLevel);

    // 更新当前最高层数
    currMaxLevel = Math.max(randomLevel, currMaxLevel);

    // 按层插入链表节点
    // 前一个节点的指向 和 newNode的指向
    for (int i = 0; i < randomLevel; i++) {

        // 更新新增节点的后向指针
        newNode.nexts[i] = updateLevelNodes[i].nexts[i];

        // 更新前驱节点的后向指针
        updateLevelNodes[i].nexts[i] = newNode;
    }

}

(2.4) 跳表删除节点

删除节点也和链表删除节点类似
链表删除节点是遍历后删除一个节点
跳表删除节点是 多层/多个 链表删除节点，遍历的时候可以利用跳表查询加快速度

/**
 * 1. 查找节点每层的前驱节点
 * 2. 删除每层前驱节点，更新前驱节点的next
 * 3. 更新maxlevel
 */
public boolean erase(int num) {
    SkipListNode[] updateLevelNodes = new SkipListNode[MAX_LEVEL];
    Arrays.fill(updateLevelNodes, head);

    // 第一次指向的是头结点
    SkipListNode curr = this.head;
    // 按层查找前驱节点
    for (int i = currMaxLevel - 1; i >= 0; i--) {
        // 查找前驱节点
        while (curr.nexts[i] != null && curr.nexts[i].val < num) {
            // 指向当前层下一个节点
            curr = curr.nexts[i];
        }
        // 前驱节点
        updateLevelNodes[i] = curr;
    }

    // 第0层
    curr = curr.nexts[0];
    // 判断是否存在节点
    if (curr == null || curr.val != num) {
        return false;
    }

    // 按层删除节点
    for (int i = 0; i < currMaxLevel; i++) {
        // 要删除节点的前驱节点
        SkipListNode prev = updateLevelNodes[i];

        // 删除节点
        if (prev.nexts[i] != null && prev.nexts[i].val == num) {
            SkipListNode deleteNode = prev.nexts[i];
            // 删除节点
            prev.nexts[i] = deleteNode.nexts[i];
        }
    }

    // 更新maxlevel
    while (currMaxLevel > 1 && head.nexts[currMaxLevel - 1] == null) {
        currMaxLevel--;
    }
    return true;
}

(2.5) 跳表查询元素

/**
 *
 * <pre>
 *     传统的单链表查找元素时，需要从链表头开始从前向后遍历，查找的时间复杂度为O(n)。
 *     跳表随着层数的增加，查询的效率接近二分查找的O(logn)   假如我们有1000万条数据，减少一半就是500万条数据。
 *     在空间复杂度上，假如我们每层都是原来的1/2，上层元素的结点和为：n/2 + n/4 + n/8 +...，会无限接近n，所以空间复杂度为O(n)。
 *
 *     参考：https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-capital-worker-3vqk/
 *
 * </pre>
 * @param target
 * @return
 */
public boolean search(int target) {
    SkipListNode curr = this.head;
    // 从最高层开始搜 直到第0层
    for (int i = currMaxLevel - 1; i >= 0; i--) {
        // 遍历当前层级链表
        // curr从head开始 head的next[]是maxLevel 32层，可以直接遍历
        while (curr.nexts[i] != null && curr.nexts[i].val < target) {
            // 指向当前层级 下一个节点
            curr = curr.nexts[i];
        }
    }
    // 第0层
    curr = curr.nexts[0];
    if (curr == null || curr.val != target) {
        return false;
    }

    return true;
}

(2.6) 总

/**
 * <pre>
 *    1206. 设计跳表  https://leetcode.cn/problems/design-skiplist/
 *
 *    参考  https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-capital-worker-3vqk/
 * </pre>
 *
 * @author weikeqin
 */
public class Skiplist {

    // 头结点
    private SkipListNode head = null;

    // 当前层级
    private int currMaxLevel = 0;

    // 最高层数
    private static final int MAX_LEVEL = 32;

    // 
    private static final double SKIPLIST_P = 0.25;


    /**
     * <pre>
     *     链表+链表数组
     *     链表头 链表尾用哑结点表示
     *
     *     1、搜索
     *         从最高层开始搜索
     *         比下一个节点的值大则用下一层的节点搜索
     *         直到level=0 并且下一个元素>=target
     *         > target 返回false
     *         = target 返回true
     *
     *    2、新增
     *        1.通过跳表搜索，找到对应节点的位置，并且在搜索时设置每一层的前驱节点
     *        2.生产随机层高
     *        3.更新最高层高
     *        4.每一层插入链表节点，并更新前驱节点的后继 和 插入节点的后继
     *
     *    3、删除
     *        1.通过跳表搜索，找到对应节点位置， 并保存每层的prev
     *        2.删除对应节点 (每一层删除节点)，并更新前驱节点的后继
     *        3.更新最高层高
     *
     * </pre>
     */
    public Skiplist() {
        // 头结点很重要
        this.head = new SkipListNode(-1, MAX_LEVEL);
        this.currMaxLevel = 0;
    }

    /**
     *
     * <pre>
     *     传统的单链表查找元素时，需要从链表头开始从前向后遍历，查找的时间复杂度为O(n)。
     *     跳表随着层数的增加，查询的效率接近二分查找的O(logn)   假如我们有1000万条数据，减少一半就是500万条数据。
     *     在空间复杂度上，假如我们每层都是原来的1/2，上层元素的结点和为：n/2 + n/4 + n/8 +...，会无限接近n，所以空间复杂度为O(n)。
     *
     *     参考：https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-capital-worker-3vqk/
     *
     * </pre>
     * @param target
     * @return
     */
    public boolean search(int target) {
        SkipListNode curr = this.head;
        // 从最高层开始搜 直到第0层
        for (int i = currMaxLevel - 1; i >= 0; i--) {
            // 遍历当前层级链表
            // curr从head开始 head的next[]是maxLevel 32层，可以直接遍历
            while (curr.nexts[i] != null && curr.nexts[i].val < target) {
                // 指向当前层级 下一个节点
                curr = curr.nexts[i];
            }
        }
        // 第0层
        curr = curr.nexts[0];
        if (curr == null || curr.val != target) {
            return false;
        }

        return true;
    }

    /**
     * 添加前只找到要添加节点的每层前驱
     * 每层插入节点，更新节点next，更新前驱节点的next
     */
    public void add(int num) {
        // 插入时需要更新多层
        SkipListNode[] updateLevelNodes = new SkipListNode[MAX_LEVEL];
        Arrays.fill(updateLevelNodes, head);

        // 第一次指向的是头结点
        SkipListNode curr = this.head;
        // 每一层需要更新的节点
        for (int i = currMaxLevel - 1; i >= 0; i--) {
            // 第一次指向的是头结点
            //curr = updateLevelNodes[i]; // 每次从头找会退化成单链表查找，时间复杂度比较高O(n)，可以根据上层的结果来找，这样才是log(n)
            // 遍历当前层级链表
            while (curr.nexts[i] != null && curr.nexts[i].val < num) {
                // 指向当前层级下一个节点
                curr = curr.nexts[i];
            }
            // curr.val < num
            // curr节点是num的前驱节点
            updateLevelNodes[i] = curr;
        }

        // 插入节点 要插入的层数
        int randomLevel = getRandomLevel();
        //System.out.println("randomLevel="+randomLevel);
        SkipListNode newNode = new SkipListNode(num, randomLevel);

        // 更新当前最高层数
        currMaxLevel = Math.max(randomLevel, currMaxLevel);

        // 按层插入链表节点
        // 前一个节点的指向 和 newNode的指向
        for (int i = 0; i < randomLevel; i++) {

            // 更新新增节点的后向指针
            newNode.nexts[i] = updateLevelNodes[i].nexts[i];

            // 更新前驱节点的后向指针
            updateLevelNodes[i].nexts[i] = newNode;
        }

    }

    /**
     * 1. 查找节点每层的前驱节点
     * 2. 删除每层前驱节点，更新前驱节点的next
     * 3. 更新maxlevel
     */
    public boolean erase(int num) {
        SkipListNode[] updateLevelNodes = new SkipListNode[MAX_LEVEL];
        Arrays.fill(updateLevelNodes, head);

        // 第一次指向的是头结点
        SkipListNode curr = this.head;
        // 按层查找前驱节点
        for (int i = currMaxLevel - 1; i >= 0; i--) {
            // 查找前驱节点
            while (curr.nexts[i] != null && curr.nexts[i].val < num) {
                // 指向当前层下一个节点
                curr = curr.nexts[i];
            }
            // 前驱节点
            updateLevelNodes[i] = curr;
        }

        // 第0层
        curr = curr.nexts[0];
        // 判断是否存在节点
        if (curr == null || curr.val != num) {
            return false;
        }

        // 按层删除节点
        for (int i = 0; i < currMaxLevel; i++) {
            // 要删除节点的前驱节点
            SkipListNode prev = updateLevelNodes[i];

            // 删除节点
            if (prev.nexts[i] != null && prev.nexts[i].val == num) {
                SkipListNode deleteNode = prev.nexts[i];
                // 删除节点
                prev.nexts[i] = deleteNode.nexts[i];
            }
        }

        // 更新maxlevel
        while (currMaxLevel > 1 && head.nexts[currMaxLevel - 1] == null) {
            currMaxLevel--;
        }
        return true;
    }

    /**
     *
     * <pre>
     *        理想情况是类似二叉树 搜索时类似二分查找 O(logN)
     *        该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且
     *        1/2 的概率返回 2
     *        1/4 的概率返回 3
     *        1/8 的概率返回 4 以此类推
     *
     *
     *     在每次新插入元素的时候，一定要插入第一层，有1/2的概率插入第二层、1/4的概率插入第三层、1/8的概率插入第四层。
     *     当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几层中。
     *
     * 链接：https://leetcode.cn/problems/design-skiplist/solution/she-ji-tiao-biao-by-capital-worker-3vqk/
     *
     * </pre>
     * @return
     */
    public int getRandomLevel() {
        int level = 1;
        while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

}

/**
 * 链表节点
 */
class SkipListNode {
    // 链表节点的值
    public int val;
    
    // 下一个节点  每层指向的下一个节点不一样
    // 类似链表的next节点 只不过有多层
    public SkipListNode[] nexts;

    public SkipListNode() {
    }

    public SkipListNode(int val, int level) {
        this.val = val;
        this.nexts = new SkipListNode[level];
    }

}


/**
 * Your Skiplist object will be instantiated and called as such:
 * Skiplist obj = new Skiplist();
 * boolean param_1 = obj.search(target);
 * obj.add(num);
 * boolean param_3 = obj.erase(num);
 */

(3) Redis里的跳表设计与实现

(3.1) 跳表数据结构

// file: server.h

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // 跳表的头结点 尾结点指针
    unsigned long length; // 长度
    int level; // 层级
} zskiplist;

/*
 * 跳表节点 (可以当做链表节点)
 * ZSETs 使用了一个特殊版本的跳表
 */
typedef struct zskiplistNode {
    sds ele; // 元素/节点的值
    double score; // 节点分数/权重
    struct zskiplistNode *backward; // 后向指针 类似双向链表的prev (指向前一个节点) (从后往前倒序查找时使用)
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前向指针 类似于链表的next
        unsigned long span;
    } level[]; // 节点的level数组，保存每层的前向指针和跨度 // 类似链表的next节点，只不过跳表有多层，每层都有next指针，所以是个数组
} zskiplistNode;

Redis里的 Sorted Set中既要保存节点的值，也要保存元素的权重，相当于多保存了几个字段
所以对应到跳表结点的结构定义中，就对应了SDS类型的变量ele，以及double类型的变量score。

为了便于从跳表的尾结点进行倒序查找，每个跳表结点中还保存了一个后向指针(*backward)，指向该结点的前一个结点。

(3.2) Redis跳表实现

函数	作用	复杂度
zslCreateNode	创建并返回一个新的跳跃表节点	最坏 O(1)
zslFreeNode	释放给定的跳跃表节点	最坏 O(1)
zslCreate	创建并初始化一个新的跳跃表	最坏 O(1)
zslFree	释放给定的跳跃表	最坏 O(N)
zslInsert	将一个包含给定 score 和 member 的新节点添加到跳跃表中	最坏 O(N) 平均 O(logN)
zslDeleteNode	删除给定的跳跃表节点	最坏 O(N)
zslDelete	删除匹配给定 member 和 score 的元素	最坏 O(N) 平均 O(logN)
zslFirstInRange	找到跳跃表中第一个符合给定范围的元素	最坏 O(N) 平均 O(logN)
zslLastInRange	找到跳跃表中最后一个符合给定范围的元素	最坏 O(N) 平均 O(logN)
zslDeleteRangeByScore	删除 score 值在给定范围内的所有节点	最坏 O(N2)
zslDeleteRangeByRank	删除给定排序范围内的所有节点	最坏 O(N2)
zslGetRank	返回目标元素在有序集中的排位	最坏 O(N) 平均 O(logN)
zslGetElementByRank	根据给定排位，返回该排位上的元素节点	最坏 O(N) 平均 O(logN)

(3.2.1) 新建跳表

// file: t_zset.c

/* 创建一个新跳表 */
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;
}

// file: server.h

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

新建跳表节点

/*
 * 创建具有指定级别的跳表节点。
 * SDS 字符串“ele”在调用后由节点引用。
 */
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
    // 为跳表节点分配内存
    // 长度 = 跳表节点结构体(zskiplistNode)长度 + 跳表节点层级结构体(zskiplistLevel) * 层数
    zskiplistNode *zn =
        zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
    // 设置分数/权重    
    zn->score = score;
    // 设置节点值
    zn->ele = ele;
    return zn;
}

(3.2.2) 跳表插入节点

/* Insert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'ele'. */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    // 要更新的跳表节点 
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;

    // 参数校验 
    serverAssert(!isnan(score));
    // 类似于遍历链表时的curr  当前指向头结点
    // 为什么不命名成curr  说好的代码规范呢？ 
    x = zsl->header;
    // 从最高层开始遍历
    for (i = zsl->level-1; i >= 0; i--) {
        /* rank逻辑看不明白可以先跳过，看到后面代码就明白了
         * 存储rank数据 越过到达插入位置 
         * store rank that is crossed to reach the insert position */
        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 &&
                    sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            //  ?
            rank[i] += x->level[i].span;
            // 指向当前层级(链表)的下一个节点
            x = x->level[i].forward;
        }
        // x是score的前驱节点  删除的时候需要用到
        update[i] = x;
    }

    /* 
     * 我们假设元素不在里面，因为我们允许重复的分数，重新插入相同的元素应该永远不会发生，
     * 因为 zslInsert() 的调用者应该在哈希表中测试元素是否已经在里面。
     */
    // 节点要插入的层数 
    level = zslRandomLevel();

    // 对比我的代码实现，我是一次性分配了32个层级，不存在这个问题，但是忽然发现自己的代码实现有点费内存 😭 ヾ(◍°∇°◍)ﾉﾞ 

    // 如果获得的随机层级 > 跳表目前的层级
    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
    x = zslCreateNode(level,score,ele);
    // 按层插入节点
    for (i = 0; i < level; i++) {
        // 类似 双向链表插入新节点

        // x = newNode  // level[i].forward = next // update[i] = prev
        // 简化为 newNode.next = prev.next 
        //       prev.next = newNode 

        // 更新 新节点x的前向指针(next) 为 前驱节点的前向指针(下一个节点)   
        x->level[i].forward = update[i]->level[i].forward;
        // 前驱节点的前项指针(next) 为 新节点x 
        update[i]->level[i].forward = x;

        /* update span covered by update[i] as x is inserted here */
        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 */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }

    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    // newNode.prev == null ?
    if (x->level[0].forward)
        x->level[0].forward->backward = x; // 设置前驱节点为 新节点x
    else
        zsl->tail = x; // 设置 链表尾结点为 新节点x
    zsl->length++;
    return x;
}

(3.2.3) 跳表删除节点

/* Internal function used by zslDelete, zslDeleteRangeByScore and
 * zslDeleteRangeByRank. */
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
    int i;
    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;
        }
    }
    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--;
}

/* Free the specified skiplist node. The referenced SDS string representation
 * of the element is freed too, unless node->ele is set to NULL before calling
 * this function. */
void zslFreeNode(zskiplistNode *node) {
    sdsfree(node->ele);
    zfree(node);
}

(3.2.4) 跳表查询-zslFirstInRange

/* Find the first node that is contained in the specified range.
 * Returns NULL when no element is contained in the range. */
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range) {
    zskiplistNode *x;
    int i;

    /* If everything is out of range, return early. */
    if (!zslIsInRange(zsl,range)) return NULL;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* Go forward while *OUT* of range. */
        while (x->level[i].forward &&
            !zslValueGteMin(x->level[i].forward->score,range))
                x = x->level[i].forward;
    }

    /* This is an inner range, so the next node cannot be NULL. */
    x = x->level[0].forward;
    serverAssert(x != NULL);

    /* Check if score <= max. */
    if (!zslValueLteMax(x->score,range)) return NULL;
    return x;
}

/* Find the last node that is contained in the specified range.
 * Returns NULL when no element is contained in the range. */
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range) {
    zskiplistNode *x;
    int i;

    /* If everything is out of range, return early. */
    if (!zslIsInRange(zsl,range)) return NULL;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        /* Go forward while *IN* range. */
        while (x->level[i].forward &&
            zslValueLteMax(x->level[i].forward->score,range))
                x = x->level[i].forward;
    }

    /* This is an inner range, so this node cannot be NULL. */
    serverAssert(x != NULL);

    /* Check if score >= min. */
    if (!zslValueGteMin(x->score,range)) return NULL;
    return x;
}

(3.2.5) -zslDeleteRangeByScore

/* Delete all the elements with score between min and max from the skiplist.
 * Min and max are inclusive, so a score >= min || score <= max is deleted.
 * Note that this function takes the reference to the hash table view of the
 * sorted set, in order to remove the elements from the hash table too. */
unsigned long zslDeleteRangeByScore(zskiplist *zsl, zrangespec *range, dict *dict) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    unsigned long removed = 0;
    int i;

    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        while (x->level[i].forward && (range->minex ?
            x->level[i].forward->score <= range->min :
            x->level[i].forward->score < range->min))
                x = x->level[i].forward;
        update[i] = x;
    }

    /* Current node is the last with score < or <= min. */
    x = x->level[0].forward;

    /* Delete nodes while in range. */
    while (x &&
           (range->maxex ? x->score < range->max : x->score <= range->max))
    {
        zskiplistNode *next = x->level[0].forward;
        zslDeleteNode(zsl,x,update);
        dictDelete(dict,x->ele);
        zslFreeNode(x); /* Here is where x->ele is actually released. */
        removed++;
        x = next;
    }
    return removed;
}

(3.2.6) 删除跳表

/* Free a whole skiplist. */
void zslFree(zskiplist *zsl) {
    zskiplistNode *node = zsl->header->level[0].forward, *next;

    zfree(zsl->header);
    while(node) {
        next = node->level[0].forward;
        zslFreeNode(node);
        node = next;
    }
    zfree(zsl);
}

参考资料

[1] Redis设计与实现-跳跃表
[2] Redis源码剖析与实战 - 05 | 有序集合为何能同时支持点查询和范围查询？
[3] 数据结构与算法之美 - 17 | 跳表：为什么Redis一定要用跳表来实现有序集合？
[4] Skip List–跳表