企业官网建设流程全解析

如果你在线上维护过用户积分榜、热销榜这类业务，大概率被问过这样一个问题：Redis 的有序集合（Sorted Set）为什么能同时做到按分数排序、按名次查人、按分数区间筛选，而且插入和查询都接近 O(logN) 的复杂度？答案就藏在它的底层数据结构里——跳跃表（skiplist）。

这是 Redis 数据结构系列的第四篇，前几篇聊过 SDS、链表、字典，这篇专门把跳跃表的节点设计、层高策略、插入过程的指针修正、跨度如何算排名这些细节全部摊开。适合已经会写 ZADD、ZRANK 这类命令、想进一步理解 Redis 底层实现的人；如果你只是调 API，读完也能明白为什么一个 ZRANK 能毫秒级返回。全文基于 Redis 源码中有序集合所用的跳跃表实现来讲，后面涉及的关键结构名以实际源码为准。

1. 一切从有序集合的查询瓶颈说起

1.1 有序集合需要支持哪些操作

有序集合的本质是"成员 + 分数"的映射，但光有映射还不够，业务上经常出现这些需求：

• 按分数排序，随时知道谁是第一名；
• 更新某个成员的分数，排名立刻变化；
• 查某个成员当前排第几名；
• 按分数范围取一批成员，比如"取 80 到 90 分的所有人"。

如果只用一个哈希表存储分数，O(1) 的等值查询能做，但排序和范围查询做不到；用一个有序链表存储，升序排列后从头遍历虽然能排序，但查找一个分数要逐个节点走过去，复杂度是 O(N)。N 一旦到了几十万，一次 ZADD 后面的查找就是几十万步，线上完全扛不住。

树结构理论上是好选择，但红黑树、AVL 树的实现复杂度很高，而且范围查询要借助中序遍历，工程上并不轻松。跳跃表用了一种很巧妙的思路：在链表上叠加多层稀疏索引，让查找过程可以跳过大量节点。

1.2 单链表为什么不行

想象一个按分数从小到大排列的单链表。你要找 score=80 的节点，只能从表头开始，顺着 next 指针一个一个往后移动。假设链表里有 10 万个节点，平均要移动 5 万次。插入也是一样，你得先找到插入位置，再改指针，找位置的成本就是 O(N)。

链表本身没有随机访问能力，这是它的天性。要加速，就得引入"索引"。跳跃表的做法是：在原始链表之上额外维护若干层"快车道"，每一层都是更稀疏的链表。高层的节点不是普通节点，而是"跳板"，能让你一次跨过很多节点。

1.3 跳跃表的核心思想：用稀疏索引换时间

你可以把跳跃表想成一本带目录和页边索引的书：第 0 层是正文每一行，第 1 层是章节标题，第 2 层是书的目录。查内容时先看目录跳到对应章节，再顺着章节找具体行，而不是从第一页逐行往下翻。

每一层都有指向下一节点的前进指针（forward），还有记录"跳了几格"的跨度（span）。查找时从最高层开始，沿着 forward 一路向前，如果下一个节点的分数已经超过目标，就沿当前层的 forward 下降到下一层继续。层数越高，一次跳跃覆盖的节点越多；越往下，路径越精细，直到第 0 层精确命中。

这个设计和二分查找的思想很像，只不过它不需要数组的随机访问，而是用链表天然的前进指针来实现跳跃。查找、插入、删除的期望复杂度都能压到 O(logN)。

2. 从结构体看跳跃表节点

2.1 zskiplistNode 节点的整体布局

Redis 源码里，跳跃表节点的定义大致如下：

typedef struct zskiplistNode { sds ele; double score; struct zskiplistNode *backward; struct zskiplistLevel { struct zskiplistNode *forward; unsigned long span; } level[]; } zskiplistNode;

这里ele是成员名，是一个 SDS 字符串；score是分数，用 double 类型存储，排序时先比 score，score 相同再比 ele。backward是后退指针，只存在节点级别，不随层变化，作用后面专门说。

最关键的是level[]，它是一个柔性数组，每个节点根据随机层高拥有不同数量的zskiplistLevel。每个zskiplistLevel内部包含一个forward和一个span，这两个字段是所有跳跃操作的基石。层数越高，level数组越长，节点占用的内存也越多。

2.2 level 数组与 zskiplistLevel：前进指针和跨度是一对搭档

forward指向当前层"下一个节点"，它决定你能跳到哪；span记录从当前节点到forward所指向的节点之间，在第 0 层顺序上要经过多少个节点。

注意"跨度"的单位很微妙：它不是"跳跃的步数"，而是"第 0 层上目标节点的位置差"。

举个例子：

• 第 0 层上，节点 A 的下一个节点就是节点 B，那么 A 的第 0 层span=1；
• 如果某个高层索引里，A 的forward直接指向节点 D，而 D 在第 0 层位于 A 之后的第 3 个位置，那么 A 在那一层的span=3。

span越大，说明这一层跳过的节点越多。这个设计的意义在于：查找路径上累加所有经过节点的span，就能直接算出目标节点在整个有序集合中的排名。这是 ZRANK 底层能 O(logN) 出结果的根本原因。

你可能会问，既然forward已经能定位到下一个节点，为什么还要span？因为forward只告诉你"下一个是谁"，但没告诉你"中间隔了多少个"。没有span，想算排名只能回到第 0 层重新数，那就退化成了 O(N)。span是为排名计算和插入修正服务的。

2.3 backward 指针：为倒序遍历留的后门

backward不是每个层都有，它只在节点上有且只有一个，指向前一个节点。这个指针的存在主要是为了支持倒序遍历，比如 ZREVRANGE、ZREVRANGEBYSCORE。

有了backward，从tail开始就能一步一步往header方向走，不需要重新从最高层查找。虽然它是 O(N) 级别的线性遍历，但倒序输出本身就要访问每个目标节点，这个成本无法避免。第 0 层是一个双向链表结构，高层则全是单向的，这样设计既满足倒序需求，又不会让每个节点为每一层多付一个指针的内存。

2.4 表头与 zskiplist：header、tail、length、level

跳跃表的主体是一个zskiplist结构：

typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; } zskiplist;

• header是一个特殊节点，不存储实际数据，它的 level 数组长度固定为ZSKIPLIST_MAXLEVEL。查找时所有层都从 header 出发，header 的 forward 指向各层的第一个真实节点。
• tail指向最后一个节点，方便从尾部开始倒序遍历。
• length记录节点总数，这样获取集合大小时不用遍历。
• level是当前所有节点中最高的层数。查找时只从level-1层开始，而不是从ZSKIPLIST_MAXLEVEL-1开始，避免无意义地遍历空层。

我第一次看源码时没注意level这个字段，以为查找永远从第 31 层开始。后来一想，绝大多数跳表的实际层数只有个位数，如果每次都从最高层开始，反而浪费不少空走。Redis 用level记录当前最大层数，是工程上的小优化，但很实用。

3. 层高随机与 ZSKIPLIST_MAXLEVEL：为什么是 32 层加 1/4 概率

3.1 层高如何产生

每个节点的层数不是人为指定的，而是通过随机函数生成：

#define ZSKIPLIST_MAXLEVEL 32 #define ZSKIPLIST_P 0.25 int zslRandomLevel(void) { int level = 1; while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF) && level < ZSKIPLIST_MAXLEVEL) { level++; } return level; }

逻辑很直白：从第 1 层开始，每次有 25% 的概率升一层，直到不再满足条件，或者达到 32 层天花板。所以一个节点最终有多高，完全由这组独立的随机试验决定。

3.2 概率与层数的数学关系

因为每一层出现的概率是上一层的 0.25 倍，所以所有节点的平均层数是：

1 / (1 - 0.25) = 1.333

也就是说，大部分节点只有 1 层或 2 层，少数节点会有较高的层数。你可能会担心平均层数这么低，索引会不会不够用？其实不会。高层节点虽然少，但正是这少数"跳板"节点承担了跨越大段距离的任务。整个跳表的层数分布是金字塔形：底层节点最多，越往上节点越少。

32 层的上限在工程上完全够用。跳跃表的查找复杂度是 O(logN)，32 层意味着理论上可以支撑 2^32 量级的节点规模。现实场景中，即便一个 Redis 实例存了上千万个集合元素，最大层数一般也不会超过 20，32 是一道足够安全的天花板。

3.3 为什么不用确定性层高

有人会想，既然要保证性能，能不能让第 1 个节点 1 层、第 2 个节点 2 层，这样规律地分配？理论上可行，但坏处很明显：如果数据分布或插入顺序恰好让高层节点都集中在某个位置，索引就可能退化为一条长链，查找复杂度重新变成 O(N)。

随机化的好处是让跳表的结构不依赖于插入顺序，即使数据是递增或递减插入，分布仍然均匀。Pugh 的论文已经证明，在随机层高策略下，跳跃表的期望查找、插入、删除复杂度都是 O(logN)。这个"期望"是数学上的保证，而不是赌运气。

Redis 把概率取 0.25 而不是 0.5，偏向于省内存。如果取 0.5，平均层数会翻倍到 2 层，每个节点的内存更多，但查询性能的提升有限。0.25 在内存和性能之间取得了很好的平衡，实测下来非常适合 Redis 单线程事件循环的工作模式。

4. 插入操作逐层拆解：update、rank 和跨度的修正逻辑

4.1 定位插入点：update 数组怎么填

插入是跳跃表里最复杂的操作，因为要同时修改多层指针，还要保证所有层的 span 依然正确。Redis 里有一段核心逻辑，我把它简化后拆开讲：

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) { zskiplistNode *update[ZSKIPLIST_MAXLEVEL]; unsigned long rank[ZSKIPLIST_MAXLEVEL]; int i, level; zskiplistNode *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 && sdscmp(x->level[i].forward->ele, ele) < 0))) { rank[i] += x->level[i].span; x = x->level[i].forward; } update[i] = x; } // ... 后续处理 }

update[i]的含义是：在第 i 层，最后一个分数小于新节点的节点。新节点将要插在update[i]后面。

查找时从当前最高层开始，遇到"下一个节点的 score 小于目标 score"就直接走过去，同时累加这一步的 span；遇到 score 相等但 ele 字典序更小的情况也继续走。为什么 score 相等还要继续走？因为有序集合要求同样的 score 按成员名的字典序排序，保证插入位置是确定的。这一步决定了跳表在大量同分场景下依然稳定有序。

4.2 排名数组 rank：它记录的到底是什么

rank[i]不是最终排名，而是"从 header 到 update[i] 节点的第 0 层距离"。换句话说，如果第 0 层的所有节点排成一列，rank[i]表示update[i]在这一列里的位置。

注意rank[i]的初始化技巧：从最高层向下遍历时，每一层的初始值继承自上一层已经累加的值。因为从 header 到某个节点，不管走哪一层，最终在第 0 层的距离是一样的。这个"继承"操作让跨层累计变得非常高效，也直接服务于后面 span 的修正公式。

4.3 新节点的层数高于现有最大层时怎么办

随机出层数后，如果新节点层数大于zsl->level，就需要把新增的层补上：

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

在新增层里，update[i]都是 header，因为这一层之前没有任何节点。header 在这些层上的 span 被临时设置为zsl->length，意思是"从 header 到链尾的节点数是整个集合的长度"。这个值后面会随节点的插入和删除动态修正。

这一步做完，新节点就能在它拥有的所有层里正确连上指针。

4.4 调整 forward 与 span 的细节

这是整个插入过程中最绕的部分，我把核心代码贴出来：

x = zslCreateNode(level, score, ele); 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++;

先说 forward 的调整：新节点 x 在第 i 层的 forward 原本应该指向update[i]在第 i 层的后继，也就是update[i]->level[i].forward；然后update[i]的 forward 改为指向 x。这是链表插入的标准操作，只是每层都要做一遍。

span 的修正要用到前面算出的 rank：

• rank[0] - rank[i]表示在第 0 层上，从update[i]到update[0]之间隔了多少个节点。因为update[0]是第 0 层的插入点前驱，所以新节点 x 要插在它后面。
• update[i]原来的 span 是从它到原后继的距离。插入 x 后，从update[i]经 x 再到原后继的距离不变，所以 x 到原后继的 span 等于原span - (rank[0] - rank[i])。
• update[i]到 x 的 span 等于(rank[0] - rank[i]) + 1，这部分变成了 update 目前到 x 的距离。

最后还有一个容易漏掉的循环：对i >= level的层，x 没有出现在这些层里，但整个链表的节点数多了一个，所以update[i]在这些层的 span 必须加 1。这步不做的话，后续算排名会偏小。

调整 backward 的逻辑也值得一提：如果update[0]是 header，说明 x 插在第一个位置，backward 设为 NULL；否则指向update[0]。如果 x 不是最后一个节点，还要把原后继的 backward 改为指向 x；如果 x 是最后一个节点，更新zsl->tail = x。

插入过程虽然细节多，但理清 "rank 继承 + span 分拆 + 高层 span 补偿" 这三步之后，再看代码会通畅很多。

5. ZRANK 背后的秘密：跨度如何算出排名

5.1 排名计算的源码逻辑

ZRANK 命令用于返回某个成员的排名，Redis 内部调用zslGetRank。它的思路也是从 header 的高层出发，不断累加经过节点的 span：

unsigned long zslGetRank(zskiplist *zsl, double score, sds ele) { zskiplistNode *x = zsl->header; unsigned long rank = 0; int i; 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 && sdscmp(x->level[i].forward->ele, ele) <= 0))) { rank += x->level[i].span; x = x->level[i].forward; } if (x->ele && x->score == score && sdscmp(x->ele, ele) == 0) { return rank; } } return 0; }

这段代码没有遍历第 0 层，而是从最高层开始一路向下找。每经过一个节点，就把该节点所在层的 span 加到 rank 上。因为 span 记录的是"当前节点到 forward 节点在第 0 层上的距离"，把这些跨层的距离累加起来，正好就是目标节点在第 0 层的位置。这就是 ZRANK 能在 O(logN) 时间内返回结果的原理。

这里有个细节需要注意：zslGetRank返回的 rank 是从 1 开始的，而 ZRANK 对外返回的是 0 开始的排名。所以 Redis 在命令层会做一次减 1 转换。第一名内部 rank 是 1，对外展示是 0。

5.2 手动推演一遍排名过程

光看代码不够直观，我用一个具体例子推一遍。

假设跳表里现在有 5 个成员，分数和层高如下：

各层的 forward 和 span 我整理成表：

现在查 d（score=40）的排名。

从 header 的 L3 开始：

1. header.L3.forward指向 c，c 的 score=30 < 40，所以走过去，rank += 3，此时 rank=3，x=c。继续看 c 的 L3.forward，是 NULL，L3 层结束。
2. 降到 L2，当前 x=c。c 在 L2 的 forward 指向 d，d 的 score=40，因为查找条件是score < 40 || (score == 40 && ele <= "d")，这里满足，所以走过去，rank += 1，此时 rank=4，x=d。d 的 L2.forward 是 NULL，L2 层结束。
3. 判断 x 恰好是 d，ele 和 score 都匹配，返回 rank=4。

这个 4 的含义是：d 在第 0 层的位置索引是 4（a=1, b=2, c=3, d=4）。如果走第 0 层从 header 慢慢数，也要数到 4；但跳跃表通过两次跳转（header->c 跨 3 格，c->d 跨 1 格）就算出来了，而且不用访问中间节点。

5.3 删除节点时 span 的变化

删除操作同样要修复各层指针，但比插入简单一些，因为它不需要提前计算 rank，只需要记录每层的update[i]：

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

删除时，每一层有两种情况：

• 如果update[i]的 forward 就是要删的 x，说明 x 出现在这一层，需要把update[i]的 forward 改成 x 的 forward，span 变成update[i]原来的 span 加上 x 的 span 再减 1。因为两个节点合并成直接相邻，跳过的节点数要扣除 x 自身。
• 如果 x 不出现在这一层，update[i]的 span 直接减 1 就行，因为集合长度少了一个。

删除完还要检查一个边界条件：如果最高层已经没有节点了，就把zsl->level降下来。这个 while 循环保证跳表不会一直空转在高空层，后续查找从实际存在的最高层开始。

6. 范围操作：ZRANGEBYSCORE 如何利用多层指针

6.1 查找区间起点

范围查询是跳跃表比哈希表强大得多的能力。ZRANGEBYSCORE要返回分数在 min 和 max 之间的所有成员。它的做法是：

1. 调用zslFirstInRange找到第一个 score >= min 的节点；
2. 从该节点开始，沿着第 0 层的 forward 一直向后遍历；
3. 直到遇到 score > max 的节点停止，期间收集结果。

zslFirstInRange本身也是一个多层查找过程，和查单个节点类似，只不过比较条件从"等于目标值"变成了"第一个大于等于下限的节点"。高层指针在这里的用处是快速跳过不满足条件的节点，接近目标范围时再逐层精细定位。

输出过程必须走第 0 层，因为要按顺序返回 M 个元素。总复杂度是 O(logN + M)，M 是返回的元素个数。如果范围覆盖整个集合，输出本身就是 O(N)，这个无法避免，但至少查找起点没有被浪费。

6.2 分数相等时的字典序规则

跳跃表对 score 相同的节点不是随意排序的，而是按 ele 的字典序排列。这就保证了同分节点之间有一个确定的相对顺序，范围查询的结果是稳定且可预期的。

在实际业务里，这个特性常被用来做"同分按时间戳排序"之类的二级排序。比如把时间戳的负数作为 score，或者把成员名作为 tiebreaker，Redis 的字典序规则会帮你维持好顺序。

6.3 区间删除如何批量进行

ZREMRANGEBYSCORE这类命令底层走zslDeleteRangeByScore。它会先定位到区间左边界，然后沿第 0 层一个一个删除区间内的节点，删除每个节点时重新连好各层指针，并同步更新 span。

批量删除的细节在于，它会先收集区间内的所有节点，再统一处理各层的指针修正，这样比删一个调整一次更高效。删除后同样要更新tail和level。整个过程利用了backward和forward的双向链表特性，逻辑清晰了不少。

7. 为什么是跳跃表而不是红黑树

7.1 各种方案的对比

很多人在学习跳跃表时会有一个疑问：红黑树也能做到 O(logN) 的插入、删除、查找，为什么 Redis 选跳跃表？

对比起来很有意思：

红黑树的最坏复杂度确实有保证，跳跃表的是期望复杂度。但在 Redis 单线程事件循环的场景下，"期望 O(logN)"已经足够稳定，而且跳跃表的代码维护成本明显更低。源码里 zslInsert 虽然细节多，但每一步都直白；红黑树插入要处理左右旋、颜色翻转，原作者也要对着论文调半天。

7.2 内存占用实测与优化

跳跃表的内存开销主要在每个节点的 level 数组上。平均层数只有 1.33，也就是说大部分节点只有一个zskiplistLevel，里面包含一个 8 字节指针和一个 8 字节无符号长整型。再加上 ele、score、backward，单节点大概几十字节。和红黑树节点（通常两个孩子指针加一个父指针，可能还要存颜色）相比，并没有明显的劣势。

我在一个模拟排行榜服务里实际压过几十万成员的写入和查询，ZADD 和 ZRANK 的延迟基本都在亚毫秒级别，跳表的内存占用也比预期紧凑。最开始我担心随机层高会带来大量多层节点，实际统计下来，绝大多数节点的 level 都只有 1 或 2，只有极少数节点会达到 6 层以上。

7.3 小数据量时的 listpack 兜底

需要说明的是，Redis 并不是所有有序集合都直接用跳跃表。当集合元素数量少、成员长度短时，底层会用更紧凑的 listpack 结构存储。只有当元素数量超过zset_max_listpack_entries（默认 128）或单个元素大小超过zset_max_listpack_value（默认 64 字节）时，才转换为"哈希表 + 跳跃表"的组合结构。

listpack 的特点是所有数据连续存放在一块内存里，读取时局部性好，但插入删除要搬移数据，所以只适合小集合。一旦数据量上来，跳跃表的 O(logN) 能力才真正发挥价值。我在实际项目里见过一个集合从几百个成员增长到几十万的过程，listpack 转跳跃表的瞬间会有一次耗时操作，但日常读写几乎无感。如果你的业务知道集合一定会很大，可以提前调小阈值，让转换更早发生，避免某一次操作突然延迟。

这一整套设计看下来，跳跃表并不是一个"高深"的数据结构，但它在工程上的选择逻辑很值得学习：能用简单代码解决的事情，就不要引入复杂结构。Redis 用它实现了排行榜、时间线、延迟队列等一大堆功能，每次我在业务里看到 ZRANGEBYSCORE 快速返回数据，都会想起那段几百行的 skiplist 实现。理解它，不只是读懂一个数据结构，更能理解"工程权衡"这四个字到底意味着什么。