Redis 中跳表的实现原理是什么？

回答重点

跳表主要是通过多层链表来实现，底层链表保存所有元素，而每一层链表都是下一层的子集。

插入时，首先从最高层开始查找插入位置，然后随机决定新节点的层数，最后在相应的层中插入节点并更新指针。
删除时，同样从最高层开始查找要删除的节点，并在各层中更新指针，以保持跳表的结构。
查找时，从最高层开始，逐层向下，直到找到目标元素或确定元素不存在。查找效率高，时间复杂度为 O(logn)

扩展知识

跳表原理详细解析

跳表，一句话概括：就是一个多层索引的链表，每一层索引的元素在最底层的链表中可以找到的元素。如下图所示，这就是一个简单的跳表实现了，每个颜色代表一层，绿色的就是链表的最底层了。

接下来我们通过查询和添加元素来了解其功能流程：

1）查询元素：这里我们与传统的链表进行对比，来了解跳表查询的高效。

假设我们要查找 50 这个元素，如果通过传统链表的话（看最底层绿色的查询路线），需要查找 4 次，查找的时间复杂度为 O（n）。

但如果使用跳表的话，其只需要从最上面的 10 开始，首先跳到 40 ，发现目标元素比 40 大，然后对比后一个元素比 70 小。于是就前往下一层进行查找，然后 40 的下一个 50 刚好符合目标，就直接返回就可以了，这个过程的跳转次数是 3 次，即 10 -> 40 (顶层) -> 40 （第二层）-> 50 (第二层)，其流程如下图所示：

跳表的平均时间查询复杂度是 O（logn），最差的时间复杂度是O（n）。

2） 插入元素：我们插入一条 score 为 48 的数据

先需要定位到第一个比 score 大的数据。如图所示，一下子就可以定位到 50 了，这里和查询的过程（上文所示）是一样的。
在定位到对应节点之后，具体是在当前节点创建数据还是增加一个层级这个是随机的，这里假设设置为 2 层
定位层级后，再将每一层的链表节点进行补齐，就是在 40 与 50 之间插入一个新的链表节点 48，插入过程与链表插入是一样的。

最终实现的效果如下图所示：

Redis 中的跳表实现解析

Redis 的跳表相对于普通的跳表多了一个回退指针，且 score 可以重复。

我们先来看一下 Redis 中关于跳表实现的源码：

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后退指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

这里我们分析一下每个字段的含义

ele：这里用到了 Redis 字符串底层的一个实现 sds，其主要作用是用来存储数据。
score：节点的分数，double 即浮点型数据。
backward：我们可以看到其是 zskiplistNode 结构体指针类型，即代表指向前一个跳表节点
level：这个就是 zskiplistNode 的结构体数组了，数组的索引代表层级索引，这里注意与 hashtable 中的结构进行区分，那个使用的是联合体，一个是 forward ，其代表下一个跳转的跳表节点，注意一个点，其是跳转到同一层;span 主要作用代表距离下一个节点的步数。

到这里分析就差不多了，为了方便大家理解，这里放一个相关的图，下图的红色箭头就代表回退指针。

Redis 跳表的实现大致如下图所示了：

补充插入的随机层级

新插入的节点位于哪一层在 Redis 中是采用随机的概率函数来决定的。

以下源码来自 redis7.0

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

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    static const int threshold = ZSKIPLIST_P*RAND_MAX;
    int level = 1;
    while (random() < threshold)
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

通过调用 zslRandomLevel 方法来决定新插入的节点所在的层数（level）。可以看到 level 从 1 开始，通过 while 循环，当产生的随机数小于 RAND_MAX的最大值的 0.25 倍时 level + 1，即有 25 % 的概率累加 level，反之退出循环。

节点被分配到第 1 层的概率为 0.75
节点被分配到第 2 层的概率为 0.25
节点被分配到第 3 层的概率为 0.25 * 0.25
以此类推，节点被分配到第 n 层的概率为 0.25^(n-1)。

所以跳表每一个节点能否新加一层的概率是 25 % （最多的层数在 Redis 5.0 中是 64 层，Redis 7.0 中是 32 层）。

为什么 Redis 跳表实现多了个回退指针（前驱指针）

回退指针主要是为了提高跳表的操作效率和灵活性。

例如删除节点时，通过前驱指针可以在一次遍历中找到并记录所有关联的前驱节点，无需在变更指针时再次查找前驱节点。这种设计避免了重复查找过程，简化了操作逻辑，大幅提高了删除的执行效率。

尤其是在频繁插入和删除的场景中，回退指针减少了节点之间指针的更新复杂度，提升性能。