5.4 源码阅读：Redis 跳表

Redis 的有序集合（Sorted Set / ZSET）是其实用性最高的数据结构之一。无论是游戏积分排行榜、带权重的任务调度队列，还是各类按时间戳排序的事件流，都能凭借有序集合在常数或对数时间内完成按分值检索、区间切片与排名统计。支撑这一系列高效特性的底层核心，正是一套经过工程深度裁剪与定制的跳表（skiplist）。

从算法理论走入工业级生产系统，Redis 对跳表做出了诸多富有洞察力的改动：引入跨度（span）以支持 $O (\log N)$ 的排名计算、采用单次内存分配消除指针跳跃、以及利用双重索引化解成员检索与区间排序的固有张力。

源码基于 Redis 8.x（t_zset.c 与 server.h）。跳表的完整实现集中在 t_zset.c 前部约 900 行代码中。

1. 为什么用跳表

1.1 核心思想

在经典数据结构中，若想兼顾排序存储与快速检索，最直接的选择往往是平衡二叉搜索树（如红黑树或 AVL 树）。然而平衡树为了维持严格的平衡条件，插入与删除时常常需要伴随复杂的节点变色与树旋转，范围查询也必须依赖树的中序遍历，在内存指针跳转与缓存局部性上面临挑战。

跳表则另辟蹊径，它以一条纯粹的有序链表为地基，在上方逐层搭建起多级由稀到密的“快速通道”。检索目标时，指针从最高层的稀疏索引出发向前探查；一旦发现下一节点的键值已超过目标，便原地下降一层继续前进，直至在最底层的全量链表中精准定位。由于各层节点的向上跃迁由伪随机数控制并呈几何分布递减，整个跳表的查找、插入与删除操作都能在期望时间 $O (\log N)$ 内完成，同时天然保留了底层链表对连续区间顺序扫描的优良局部性。

1.2 Redis 为什么选择跳表

Redis 作者 antirez 曾公开详述过为何选用跳表替代平衡二叉树来实现有序集合：

内存开销高度可调：跳表节点的高层指针数量由几何分布概率参数控制。通过调低高层跃迁的概率（Redis 取 $p = 0.25$ ），跳表的平均指针开销能够压制得比多数平衡树更轻盈。
范围遍历极其自然：有序集合的高频操作包括 ZRANGE、ZREVRANGE 等区间切片。在跳表中定位到区间起点后，后续的扫描完全退化为平直的双向链表遍历，对 CPU 缓存预取极其友好，无需处理复杂的树遍历回溯。
工程实现与调试简洁：相较于红黑树数十种繁琐的旋转与重着色分支，跳表的插入与删除在结构拓扑上始终只是纯粹的链表指针重挂，代码阅读与并发改造的心理门槛显著更低。

2. 数据结构

2.1 跳表节点

zskiplistNode 结构

typedef struct zskiplistNode {
    double score;                       // 分数，排序的依据
    struct zskiplistNode *backward;     // 后退指针，仅在第 0 层
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 前进指针
        unsigned long span;             // 跨度：到 forward 节点的距离（相邻节点为 1）
    } level[];                          // 柔性数组，长度 = 该节点的层数
    // sds ele 嵌入在 level[] 之后（单次分配）
} zskiplistNode;

每个节点由以下核心字段构成：

score：double 精度的分数值，作为排序的第一关键字。
ele：成员字符串（SDS），作为分数值相同情况下的第二排序关键字（按二进制字典序排序）。在现代 Redis 实现中，SDS 字符串直接以内联形式紧随结构体分配，避免额外的间接指针寻址。
backward：后退指针，专门设置在第 0 层，用于支持从链表尾部向头部反向遍历（如 ZREVRANGE）。
level[]：柔性数组成员。其实际长度对应节点分配的层数。每一层包含一个指向前驱节点的 forward 前进指针，以及一个记录跃迁距离的 span 跨度值。

span（跨度）是 Redis 对学术界跳表设计的关键工程创新。教科书跳表仅包含前进指针，只能判断“下一个节点是谁”。Redis 在各层的前进指针旁增加了 span，专门记录当前节点沿此层前进指针到达下一个节点时跨越了多少个最底层基础节点（相邻两节点间的跨度为 1）。沿着查找路径把沿途跨越的 span 逐项累加，就能直接算出目标节点在整个集合中的绝对名次（Rank），一举将 ZRANK 从全表扫描的 $O (N)$ 降至 $O (\log N)$ 。

为了降低内存碎片与寻址延迟，节点的内存分配在 zslCreateNode 中被打包为单次连续分配：

static zskiplistNode *zslCreateNode(zskiplist *zsl, int level,
                                     double score, sds ele) {
    size_t node_size = sizeof(zskiplistNode)
                     + level * sizeof(struct zskiplistLevel);
    size_t sds_buf_size = sds_hdr_len + ele_len + 1;
    size_t total_size = node_size + sds_buf_size;

    // 一次 malloc 分配 node + level[] + 嵌入的 sds
    zskiplistNode *zn = zmalloc_usable(total_size, &usable);

    zn->score = score;
    zn->backward = NULL;

    // 在 node 末尾就地构造 sds
    char *sds_buf = (char*)zn + node_size;
    sds embedded_sds = sdsnewplacement(sds_buf, sds_buf_size,
                                        sds_type, ele, ele_len);
    // 层数和 sds 偏移存入 level[0].span（第 0 层的 span 字段复用为元信息）
    zslSetNodeInfo(zn, level, sds_offset);
    return zn;
}

结构体本体、变长柔性数组 level[] 以及存储成员内容的 SDS 缓冲区全部挤入同一块连续的堆内存中。释放节点时也只需调用一次 zfree，极大减少了小对象高频创建释放造成的内存碎片。

2.2 跳表本体

zskiplist 结构

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;  // 头节点（哨兵）和尾节点
    unsigned long length;                  // 节点总数（不含 header）
    int level;                             // 当前最高层数
    size_t alloc_size;                     // 跟踪内存占用
} zskiplist;

header：固定拥有 ZSKIPLIST_MAXLEVEL（32 层）的哨兵节点。它不保存任何有效业务数据，仅作为所有高低层索引的前行起点，彻底规避了链表头部的空指针特判。
tail：指向跳表中排名最末的节点，提供常数时间 $O (1)$ 的末梢反向定位。
level：记录当前整个跳表中实际存在的最大节点层数。每次查找只需从这个实际最高层启动向下探查，无需盲目从第 32 层遍历空指针。

2.3 有序集合的双重索引

完整的有序集合数据类型并未单纯依赖跳表，而是采用了跳表与哈希表的双剑合璧：

typedef struct zset {
    dict *dict;       // ele -> score 的哈希表，O(1) 按成员查分数
    zskiplist *zsl;   // score -> ele 的跳表，支持排序和范围查询
} zset;

同一个成员元素在内存中只存在一份物理 SDS 字符串，字典和跳表共同引用它的地址。当执行 ZSCORE 时，系统直接走哈希表在 $O (1)$ 时间内拿到分值；当执行 ZRANGE 或 ZRANK 时，则交由跳表以 $O (\log N)$ 时间展开排序与跨度计算。两者各扬所长，在空间零冗余的前提下兼顾了两种截然不同的访问范式。

3. 随机层数

zslRandomLevel 的几何分布

#define ZSKIPLIST_MAXLEVEL 32
#define ZSKIPLIST_P 0.25

static 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;
}

每个节点初始化时都至少拥有第 1 层；此后每次通过抛掷硬币式的伪随机判定，以 $p = 0.25$ 的概率尝试向上晋升一层，直到掷出不满足条件或达到最大层数上限 32。这是一个经典的参数为 $p = 0.25$ 的几何分布：

100% 的节点拥有第 1 层；
25% 的节点能晋升到第 2 层；
6.25% 的节点能晋升到第 3 层；
依此类推，第 $k$ 层的期望节点数为 $N \times {0.25}^{k - 1}$ 。

在 $p = 0.25$ 的设定下，整个跳表平均每个节点消耗的指针数量仅为 $\frac{1}{1 - p} \approx 1.33$ 个，相比 $p = 0.5$ （平均 2 个指针）节省了大量内存。而 32 层的上限足以稳固支撑 $4^{32} = 2^{64}$ 规模的巨量元素，在实际物理内存容量内永无溢出之虞。

4. 插入

插入算法的核心不变量

跳表插入的核心在于维护两组辅助上下文：

update[i]：在第 $i$ 层中，新节点应当紧跟其后的那个前驱节点。
rank[i]：从哨兵头节点出发，沿着检索阶梯走到 update[i] 时沿途累加跨越的底层节点总数（即前驱节点在全局中的绝对名次）。

整个插入过程严密地分为三步：首先自顶向下沿阶梯寻查插入槽位，填满 update[] 与 rank[]；随后掷骰生成随机层数并完成节点内存分配；最后在各层逐级穿针引线挂接指针，并精确重算各层的 span 跨度。

zslInsert 负责协调高阶调用，而 zslInsertNode 承载了全部核心指针调度：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    int level = zslRandomLevel();
    zskiplistNode *node = zslCreateNode(zsl, level, score, ele);
    zslInsertNode(zsl, node);
    return node;
}

4.1 查找插入位置

static void zslInsertNode(zskiplist *zsl, zskiplistNode *node) {
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
    unsigned long rank[ZSKIPLIST_MAXLEVEL];
    zskiplistNode *x;
    int i, level;
    double score = node->score;
    sds ele = zslGetNodeElement(node);
    level = zslGetNodeInfo(node)->levels;

    // 从最高层开始，逐层下降，找到每层的前驱节点
    x = zsl->header;
    for (i = zsl->level-1; i >= 0; i--) {
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (zslCompareWithNode(score, ele, x->level[i].forward) > 0) {
            rank[i] += zslGetNodeSpanAtLevel(x, i);
            x = x->level[i].forward;
        }
        update[i] = x;
    }

查找路径呈现出典型的由左上至右下的“阶梯式扫描”。在每一层，指针尽可能向前探查：只要前方节点的分数小于目标分值（或分值相同时字符串字典序小于目标），就继续跨步前进，同时将前进指针上的 span 累加进 rank[i]；一旦前方节点已大于目标或到达链表尾端，便停下当前层的脚步，记录 update[i] = x，并垂直下降一层继续前进。

4.2 链接新节点

    // 如果新节点层数超过当前最高层，补充 update 和 rank
    if (level > zsl->level) {
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            zslSetNodeSpanAtLevel(update[i], i, zsl->length);
        }
        zsl->level = level;
    }

    // 逐层插入
    for (i = 0; i < level; i++) {
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;

        // 新节点的 span = 原 span - 已跨越的距离
        zslSetNodeSpanAtLevel(node, i,
            zslGetNodeSpanAtLevel(update[i], i) - (rank[0] - rank[i]));
        // 前驱的 span = 已跨越的距离 + 1
        zslSetNodeSpanAtLevel(update[i], i, (rank[0] - rank[i]) + 1);
    }

    // 未被新节点覆盖的高层，span 只需 +1
    for (i = level; i < zsl->level; i++) {
        zslIncrNodeSpanAtLevel(update[i], i, 1);
    }

跨度 span 的数学重算公式是理解跳表排名的关键所在。新节点插入在 update[i] 与其原本的后继节点之间，将原本由 update[i] 一跨到底的距离切分为了前后两段：

前半段：从 update[i] 到新节点，距离恰好是 (rank[0] - rank[i]) + 1（其中 +1 计入新节点自身）。
后半段：从新节点到原后继节点，跨度为原跨度减去前半段消耗的间距。
高层调整：对于超出新节点自身高度、但仍在跳表有效高度范围内的顶层，新节点的加入只是在它们的跨越区间内平添了一个底层实体，因此只需直接给前驱的 span 执行加 1。

4.3 更新后退指针与边界

    node->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (node->level[0].forward)
        node->level[0].forward->backward = node;
    else
        zsl->tail = node;

    zsl->length++;
}

后退指针仅在最底层的第 0 层进行维护，形成一条严格的双向链表结构。如果新节点恰好插入在表尾（其后继为空），则顺势将跳表的 tail 指针刷新为当前节点。至此，节点总计数 length 累加，新节点正式融入跳表。

5. 删除

删除算法的不变量

删除操作与插入在结构上呈现出严密的对偶性：同样是先沿阶梯定位各层的受影响前驱集合 update[]，随后逐层脱链并重新缝合指针。跨度 span 的更新也是插入的镜像逻辑——前驱原本跨越的距离与被删节点向后跨越的距离合并，同时减去被删节点自身占据的 1 个单位位置。

删除流程由定位前驱的 zslDelete 与实际解绑的 zslUnlinkNode 协同完成：

static void zslUnlinkNode(zskiplist *zsl, zskiplistNode *x,
                           zskiplistNode **update) {
    for (int i = 0; i < zsl->level; i++) {
        if (update[i]->level[i].forward == x) {
            // 这一层直接链接到 x，合并 span 并跳过 x
            zslIncrNodeSpanAtLevel(update[i], i,
                zslGetNodeSpanAtLevel(x, i) - 1);
            update[i]->level[i].forward = x->level[i].forward;
        } else {
            // 这一层没有链接到 x（x 的层数不够高），只需 span-1
            zslDecrNodeSpanAtLevel(update[i], i, 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--;
}

代码中的 if/else 严谨处理了节点高度不一的情况：若被删节点 x 只有 2 层，而跳表当前总高度为 5 层，那么在第 3 至 5 层中，update[i] 的前进指针实际上直接凌空跃过了 x。在这些高层，前进指针无需变动，只需将跨度减 1，以反映底层物理节点减少了一个实体。

完成各层脱链后，代码修复底层的 backward 指针与 tail 指针。如果刚刚被移除的节点恰好是跳表中独占最高层的孤本，循环还会自动递减 zsl->level，收缩跳表的有效高度。

而在日常业务的高频分值变动中，zslUpdateScore 包含了一项精巧的就地优化路径：如果修改后的分值仍然严格保持在当前节点的前驱与后继分值之间（相对拓扑位置未变），系统将直接原地覆写 node->score，彻底省去了摘链、重算跨度以及再次插入的整套对数开销。

6. 排名与范围查询

6.1 排名查询

zslGetRank 利用 span 累加实现 O(log N) 的排名计算：

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) {
    zskiplistNode *x;
    unsigned long rank = 0;

    x = zsl->header;
    for (int i = zsl->level-1; i >= 0; i--) {
        while (zslCompareWithNode(score, ele, x->level[i].forward) >= 0) {
            rank += zslGetNodeSpanAtLevel(x, i);
            x = x->level[i].forward;
        }
        if (x != zsl->header &&
            zslCompareWithNode(score, ele, x) == 0)
            return rank;
    }
    return 0;  // 未找到
}

查找路径与插入逻辑相同，采用自顶向下的阶梯式遍历。在每一层向前推进时，只要前方节点的分数小于等于目标（若分数相同则字典序小于等于目标），就向右前进并累加对应层的 span 跨度。到达目标节点时，累加值正是从哨兵头节点到该节点的绝对距离，也就是以 1 为起点的全局名次（1-based rank）。若遍历结束仍未匹配，则返回 0 表示元素不存在。

与之互为逆运算的 zslGetElementByRank 则反其道而行之：给定目标名次，它从最高层出发，沿途比较各层跨度与剩余名次，在对数时间内直接定位到指定排名的节点对象。

6.2 范围查询

zslNthInRange 负责在指定的分数范围内定位第 N 个元素。它的检索策略兼顾了范围边界判定与步进局部性：

先用 zslIsInRange 进行常数时间 $O (1)$ 的快速拒绝：仅需检查给定区间的端点与跳表的最小/最大节点，若毫无交集则直接返回 NULL；
从最高层开始沿阶梯搜索，快速收敛到落在该范围内的第一个边界节点；
如果调用方要求的偏移量 $N$ 较小（小于阈值 ZSKIPLIST_MAX_SEARCH = 10），代码直接沿最底层的第 0 层链表平稳步进，充分利用连续内存的缓存红利；
如果偏移量 $N$ 较大，则继续借助高层索引的大跨度指针跳跃穿透。

zskiplistNode *zslNthInRange(zskiplist *zsl, zrangespec *range,
                              long n, unsigned long *out_rank) {
    if (!zslIsInRange(zsl, range)) return NULL;

    // 在最高层找到范围边界
    x = zsl->header;
    i = zsl->level - 1;
    while (x->level[i].forward &&
           !zslValueGteMin(x->level[i].forward->score, range)) {
        edge_rank += zslGetNodeSpanAtLevel(x, i);
        x = x->level[i].forward;
    }
    // 记住此节点以备大偏移量时使用
    last_highest_level_node = x;

    // 继续在低层精确定位
    for (i = zsl->level - 2; i >= 0; i--) {
        while (x->level[i].forward &&
               !zslValueGteMin(x->level[i].forward->score, range)) {
            edge_rank += zslGetNodeSpanAtLevel(x, i);
            x = x->level[i].forward;
        }
    }

    // 小偏移：逐节点走
    if (n < ZSKIPLIST_MAX_SEARCH) {
        for (i = 0; i < n + 1; i++)
            x = x->level[0].forward;
    } else {
        // 大偏移：从高层节点跳跃
        x = zslGetElementByRankFromNode(last_highest_level_node,
                                         zsl->level - 1, rank_diff);
    }
    // ...
}

当 $n$ 为负数时，函数会先将游标定位到区间的右边界，然后沿着底层双向链表的 backward 指针逆向回溯，以此自然支撑 ZREVRANGEBYSCORE 等反向区间命令。

7. 从命令到跳表操作

有序集合的常用命令与跳表操作有着清晰的映射关系：

Redis 命令	操作	跳表函数
`ZADD key score member`	插入/更新分数	`zslInsert` 或 `zslUpdateScore`
`ZREM key member`	删除	`zslDelete`
`ZSCORE key member`	查分数	不走跳表，走 `dict` 哈希表
`ZRANK key member`	查排名	先用 `dict` 找到节点，再用 `zslGetRankByNode`
`ZRANGE key start stop`	按排名范围	`zslGetElementByRank` + 遍历
`ZRANGEBYSCORE key min max`	按分数范围	`zslNthInRange` + 遍历
`ZRANGEBYLEX key min max`	按字典序范围	`zslNthInLexRange` + 遍历
`ZCARD key`	元素总数	`zsl->length`，O(1)

跳表与哈希表协同构成了完整的双重索引体系：哈希表负责在常数时间 $O (1)$ 内按成员名称直接定位到节点（驱动 ZSCORE 查询与 ZREM 的快速寻址）；跳表则负责以 $O (\log N)$ 时间组织有序排列，支持排名统计与区间检索。二者共同持有同一个 SDS 成员字符串的指针，既保证了数据访问的双向极速，又彻底杜绝了重复存储的内存浪费。

8. 习题

8.1 巩固

#50522

⚡4⏳3∑

(1) [1.1] 正文给了 Redis 选择跳表的三条理由。平衡二叉搜索树（红黑树、AVL 树）的查找、插入、删除同样是 O(log N)。逐条说明这三条理由分别在讲什么代价，再补一条跳表不如平衡树的地方。不要泛泛而谈，每条落到一个具体操作上，例如 ZRANGE key 100 199 在两种结构里各要访问多少不连续的节点。

(2) [3.2] 按 ZSKIPLIST_P = 0.25、ZSKIPLIST_MAXLEVEL = 32 计算并填表，不查资料：

项	值
一个节点至少有 1 层的概率
恰好 2 层的概率
至少有 3 层的概率
每个节点的平均层数
存 100 万个元素时，第 10 层的期望节点数
32 层能覆盖的元素数量级

平均层数用 $\sum_{k \geq 1} P (L \geq k)$ 算，写出求和式。再回答：如果把 ZSKIPLIST_MAXLEVEL 从 32 降到 16，能覆盖的元素数量级变成多少（用 $4^{层数}$ 估）？元素数超过这个量级后，最高一层的期望节点数会变成多少，查找会先在哪一步退化？

(3) [4.3] 下面是一棵已经建好的跳表，括号里是节点的分数，H 是 header。三层从上到下记为第 3、2、1 层，箭头旁的数字是 span：

text

第 3 层:  H --4--> D(7)
第 2 层:  H --2--> B(3) --2--> D(7)
第 1 层:  H --1--> A(1) --1--> B(3) --1--> C(5) --1--> D(7)

（这里按教科书的布局，每层都记到下一个节点的距离。8.10 把最底层的 span 字段改存节点元信息，所以源码里读跨度用的是 zslGetNodeSpanAtLevel，它在最底层直接返回 1；下面的推演与这个改动不冲突。下文说的「第 3、2、1 层」对应循环里的 i = 2、1、0。）

表长 length 为 4。按 zslGetRank 的循环，逐步写出 zslGetRank(7) 与 zslGetRank(5) 的 rank 累加过程与返回值。再把 while 里的 >= 0 改成 > 0，重新推一遍：两次调用各返回什么？为什么改完之后，凡是分数与目标相等的节点都永远走不上去？ZRANK 对这种改动会表现出什么症状？

#50523

⚡4⏳3

在一台按 5.1 启动的本机实例上，用命令观察有序集合的两套索引与编码切换。逐条执行并记录输出：

zsh - redis-cli

console

$ ./src/redis-cli -p 24740 ZADD z 1 a 2 b 3 c
$ ./src/redis-cli -p 24740 OBJECT ENCODING z
$ ./src/redis-cli -p 24740 ZRANGE z 0 -1 WITHSCORES
$ ./src/redis-cli -p 24740 ZRANK z b
$ ./src/redis-cli -p 24740 DEBUG HTSTATS-KEY z
$ ./src/redis-cli -p 24740 CONFIG SET zset-max-listpack-entries 2
$ ./src/redis-cli -p 24740 ZADD z 4 d
$ ./src/redis-cli -p 24740 OBJECT ENCODING z
$ ./src/redis-cli -p 24740 DEBUG HTSTATS-KEY z

回答：

第一次 OBJECT ENCODING 与第二次分别是什么？第一次的 DEBUG HTSTATS-KEY z 返回的是 table size 还是报错？把报错的原文抄下来，说明它为什么能证明 listpack 编码的集合里根本没有哈希表。
第二次的编码切换由哪个配置项、在哪个函数里触发（只需指到函数名，t_zset.c 里的 zsetTypeMaybeConvert 即可）。第二次 DEBUG HTSTATS-KEY z 的输出里 table size、number of elements 各是多少？此时负载因子正好是 1，说明 zsetConvertAndExpand 是怎样给新的 dict 定大小的。再 ZADD z 5 e，DEBUG HTSTATS-KEY z 的输出变成几段，各段的 table size 与元素数是多少？这个「两段」的输出对应正文 2.3 节的哪个状态？
ZSCORE、ZRANK、ZRANGE 三个命令各走哪套索引？ZRANK 需要先定位节点再算排名，说明它用了哪个函数。
依次执行 ZADD z 2.5 b 与 ZADD z 100 b，每次之后 ZRANGE z 0 -1 WITHSCORES 的记录顺序，并说明节点是被删除后重新插入，还是原地改了分数。在源码里找到 zslUpdateScore 的快速路径条件（比前驱大、比后继小），说明第一次为什么走快速路径、第二次为什么走慢路径。再执行 ZADD z -100 b，这一次从原来的位置看两个条件各是否成立？

验收：四步输出、四个问题的回答。第 2 问的两段输出要贴 Hash table 0 与 Hash table 1 的原文；第 4 问要引用 zslUpdateScore 快速路径里前后两个比较表达式的含义，并指出它只比较邻居的分数、不比较成员名，所以分数相同时的处理要另找依据。

8.2 编程

#50524

⚡4⏳4

下面是一棵只存 double 分数与字符串成员的跳表骨架，缺 zsl_insert。把它补全，要求实现与正文一致的 update[]、rank[] 和 span 更新。

#include <stddef.h>

#define ZSL_MAXLEVEL 16
#define ZSL_P 0.25

typedef struct zsl_node zsl_node;
struct zsl_node {
    double score;
    char *ele;              /* 调用者负责释放；本题可以只存指针 */
    zsl_node *backward;
    struct zsl_level {
        zsl_node *forward;
        unsigned long span;
    } level[];              /* 长度为该节点的层数 */
};

typedef struct {
    zsl_node *header, *tail;
    unsigned long length;
    int level;
} zsl;

zsl *zsl_create(void);
void zsl_free(zsl *zsl);
zsl_node *zsl_insert(zsl *zsl, double score, const char *ele); /* 补全 */

要求：

zsl_create 建一个 ZSL_MAXLEVEL 层的 header，level 初始为 1，length 为 0。
zsl_insert 沿用正文的三步：逐层找 update[] 与 rank[]；层数超过当前最高层时给 update[i] 补 header、把它的 span 设为 length；逐层链接并按 span_new = span_old - (rank[0] - rank[i])、span_pred = (rank[0] - rank[i]) + 1 更新，未被覆盖的高层 span 加一。
维护 backward、tail、length。
排序规则：先比 score，分数相同按 strcmp。
写 unsigned long zsl_rank(const zsl *z, double score, const char *ele)，用与插入相同的阶梯路径累加 span，未找到返回 0；返回值为 1-based。
测试程序：按 (1,"a")、(3,"b")、(5,"c")、(7,"d") 依次插入，打印每层的节点序列与 span；再插入 (4,"e") 后重印。与下面对照：

text

插入 e 之后：
第 3 层  H --5--> D
第 2 层  H --2--> B --1--> E --2--> D
第 1 层  H --1--> A --1--> B --1--> E --1--> C --1--> D
length = 5

（验算：插入 E 时 rank[0] = 2、rank[1] = 2。E 的第 1 层插在 B 与 C 之间，span(E,0) = 1 - 0 = 1、span(B,0) = 0 + 1 = 1；第 2 层插在 B 与 D 之间，span(E,1) = 2 - 0 = 2、span(B,1) = 1；顶层没有覆盖到 E，header 的 span 加一，从 4 变成 5。）

（E 有 2 层，D 有 3 层，B 有 2 层，其余 1 层。A、B、C、D、E 的分数依次为 1、3、5、7、4。）

验收：插入过程中 update[]、rank[] 的实际数值（打印出来）、插入前后的各层序列、zsl_rank 的返回值——按分数从小到大 A、B、E、C、D 的排名应依次为 1、2、3、4、5。你的随机层数生成器若与上表的层数不同，就按自己的层数重新算一遍期望，并用 zsl_rank 与逐节点遍历的结果逐个对照。

#50525

⚡4⏳3

在上一题的实现上增加按排名查节点的能力，并做随机对照。

实现 zsl_node *zsl_by_rank(const zsl *z, unsigned long rank)，rank 从 1 开始，越界返回 NULL。做法与 zslGetRank 对称：从最高层开始，若 traversed + span <= rank 就前进并累加，每下降一层检查 traversed == rank。
实现 zsl_node *zsl_first_in_range(const zsl *z, double min, int minex)，返回第一个 score > min（minex 为 1）或 score >= min 的节点，找不到返回 NULL。只用前进指针，不许从 header 逐节点线性扫描——每层都要尽量向右走。
随机测试：插入 5000 个分数互不相同、范围在 [0, 100000) 的成员，另建一个有序数组作参考。对 500 个随机排名，zsl_by_rank 返回的成员必须与数组一致；对 500 个随机 min 与 minex 组合，zsl_first_in_range 的结果必须与在数组上二分的结果一致。
统计第 2 步里前进指针被跟随的总次数（每跳过一个节点计一次），与从 header 线性扫到同一位置的节点数比较，给出两个数字和比值。5000 个元素、p = 0.25 时，比值应当在一百倍以上。

验收：两组随机对照的失败个数（必须为 0）、第 4 步的两个数字与比值。

#50526

⚡5⏳4

实现删除，并把「span 的两种处理」写对。

写 int zsl_delete(zsl *z, double score, const char *ele)：先按插入的路径填 update[]，确认 x 存在后逐层解除链接。分两种情况：
- update[i]->level[i].forward == x：这一层直接指向 x，把 x->level[i].span - 1 加到前驱的 span 上，再改 forward；
- 否则这一层没有链接到 x，只需把前驱的 span 减一。
更新 backward 与 tail；若删掉的是最高层的节点，把 zsl->level 降到「header 最高一层还有 forward」的层数；length 减一。
写 int zsl_validate(const zsl *z)，检查三条不变式：
- 每层从 header 沿 forward 走，累加的 span 之和等于 length；
- 第 1 层从 header 到 tail 的节点数等于 length，backward 链与 forward 链互为逆序；
- 每个节点的 score 严格递增（分数互不相同时），且每个节点的层数不超过 zsl->level。
随机测试：插入 2000 个分数互不相同的成员，随机删除 1000 个，每删除 100 次调用一次 zsl_validate；每次删除后随机抽 20 个排名与参考数组对照。最后把剩下的 1000 个也全部删掉，检查 length 回到 0、tail 为 NULL、zsl->level 回到 1，zsl_validate 仍然通过。
故意把第 1 步的「否则」分支写成 span 不变（删掉那行减一），重跑测试，记录 zsl_validate 第一次失败时的操作序号与失败的不变式。说明这一条为什么只在「被删节点的层数低于表高层数」时才会暴露。

验收：zsl_validate 的检查函数、第 4 步通过时的输出、第 5 步的失败序号与不变式。

8.3 综合与挑战

#50527

⚡5⏳4

用数据回答「p 取 0.25 是不是好的权衡」。

把上一题的实现参数化：ZSL_P 分别取 0.125、0.25、0.5，ZSL_MAXLEVEL 固定为 32。每种取值插入 20 万个随机分数，统计：
- 每个节点的平均层数，与 $1 / (1 - p)$ 比较；
- 所有节点分配的总字节数，按 sizeof(结构体固定部分) + level * sizeof(struct zsl_level) 累加；
- 1000 次随机查找中前进指针被跟随的平均次数（在比较函数里计数）。
列一张三行的表：p、平均层数、总字节数、平均跳数。用数据说明 p 从 0.25 降到 0.125 省下了多少内存、查找多跳了几次；p 升到 0.5 时反过来多少。
结合正文引用的 antirez 的三条理由，说明在「内存敏感、查找次数远多于插入」的场景与「查找为主、内存充裕」的场景下各应选哪个 p，并给出你在这道题的实现里会定成多少。
额外观察：p 越小，zsl->level 涨得越慢。打印三种取值下 20 万个节点达到的最高层数，并解释它和 p 的关系。

验收：三行数据表、第 3 问的结论与理由、三种取值下的最高层数。所有数字都来自你自己的运行，不要照抄这里的估计。

#50528

⚡6⏳5

把范围查询的负偏移与开闭区间补齐，对照 redis-cli 验证语义。

在 50525、50526 的实现上写：

zsl_node *zsl_nth_in_range(zsl *z, double min, int minex, double max, int maxex,
                          long n, unsigned long *out_rank);

n 从 0 开始表示范围内第一个元素，负数表示从范围末尾倒数（-1 是最后一个）。out_rank 返回 1-based 的绝对排名。 2. 实现策略按正文 6.2 的四步：先用 zsl_is_in_range 只看头尾快速判定有没有交集；再从最高层往下找到范围左边界；|n| < 10 时沿第 1 层逐节点走，否则借高层节点跳跃定位。 3. 写一个对照程序：用真实的 redis-server（5.1 的启动方式），造 200 个分数为 i * 10、成员为 m<i> 的有序集合。对 100 组随机的 (min, max, minex, maxex, n)，一边用你的 zsl_nth_in_range，一边把同样的参数翻译成 ZRANGEBYSCORE key min max WITHSCORES LIMIT n 1（n 为负时用 ZREVRANGEBYSCORE key max min WITHSCORES LIMIT -n-1 1），比较成员名。开区间在 redis-cli 里写成 (10、(100 的形式。 4. 记录你的实现与 redis-cli 不一致的组数（目标为 0），并单独回答：n 为负数时为什么不能简单地「先找左边界再往回走 -n-1 步」？正文的实现在负偏移分支里先把 x 推到了范围右边界，这一点在你的代码里怎么体现？

验收：对照程序与 100 组比较结果、不一致组数、第 4 问的回答。如果某组不一致，贴出参数与两边的输出，说明是边界语义（开闭区间、越界）还是排名换算错了。

3.10 求值

4.3 选择语句

5.5 跳转语句

10.2 结构体

14.3 程序支持

15.1 声明

16.2 对象表示

18.2 标准库中的宏

5.4 源码阅读：Redis 跳表 ​

1. 为什么用跳表 ​

1.1 核心思想 ​

1.2 Redis 为什么选择跳表 ​

2. 数据结构 ​

2.1 跳表节点 ​

zskiplistNode 结构

2.2 跳表本体 ​

zskiplist 结构

2.3 有序集合的双重索引 ​

3. 随机层数 ​

zslRandomLevel 的几何分布

4. 插入 ​

插入算法的核心不变量

4.1 查找插入位置 ​

4.2 链接新节点 ​

4.3 更新后退指针与边界 ​

5. 删除 ​