上一篇【第14篇】Rehash揭秘——Redis字典扩容缩容的精妙设计** 下一篇**【第16篇】跳跃表vs平衡树——谁才是有序集合的真正王者摘要跳跃表Skip List大概是Redis所有数据结构里最有趣的一个——它用一个随机算法每层晋升概率25%替代了平衡树的复杂旋转操作在保持O(log N)查找性能的同时代码却比红黑树简单了不止一个数量级。本文从William Pugh 1990年的原始论文讲起逐步拆解Redis跳跃表的zskiplistNode和zskiplist结构体重点剖析span字段的排名计算机制以及那个抛硬币决定层高的随机算法。最后通过ZADD/ZRANK/ZRANGE/ZRANGEBYSCORE命令演示跳跃表在Redis有序集合中的实际运作。一、跳跃表的起源一个天才的偷懒方案1.1 William Pugh的烦恼1990年马里兰大学的William Pugh教授面对一个难题平衡树AVL树、红黑树虽然查找快但实现起来太复杂了——旋转操作、颜色维护、各种边界条件随便写错一行代码就全盘皆崩。他的思路是既然平衡树的核心价值是跳过不必要的比较那能不能用更简单的方式达到同样的效果答案是给有序链表加多层索引。1.2 跳跃表的核心思想想象你在查一本字典。你不是从第一页开始逐页翻而是先在字母索引里找到R开头的页码范围在这个范围里再找到R-e-d的精确页码翻到那一页跳跃表做的就是类似的事——在基础链表之上建立多层快车道让你可以跳过大量不相关的节点快速定位到目标。普通有序链表找55需要走5步 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60 ① ② ③ ④ ⑤ ✓ 跳跃表加一层索引找55只需要走4步 索引层 10 ──────── 30 ──────── 50 ──────── NULL | | | 原始层 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60 ① ② ③ ④ ⑤ ✓ 走到索引的50后下一跳是NULL回头下到原始层继续走50→55完成。1.3 更高效的多层索引理想情况下每层的节点按一定比例选取形成类似金字塔的结构层级2 (每4个选1个) ────────────────── 40 ──────────────── NULL | 层级1 (每2个选1个) ──────── 20 ──────── 40 ──────── 60 ── NULL | | | 层级0 (全部节点) 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60查找55的过程从最高层层级2开始40的下一个是NULL下降到层级140的下一个是6055在40处下降到层级040→50→55找到总共走了4步相比原始链表的5步数据量大时优势更加明显。二、zskiplistNode跳跃表的细胞2.1 结构体定义typedefstructzskiplistNode{sds ele;// 成员对象字符串doublescore;// 分值排序依据structzskiplistNode*backward;// 后退指针structzskiplistLevel{structzskiplistNode*forward;// 前进指针unsignedlongspan;// 跨度}level[];// 柔性数组——层级数组}zskiplistNode;2.2 每个字段的职责ele (sds)节点存储的元素是一个SDS字符串。注意这是成员和分值是两回事。score (double)排序依据。跳跃表按照score从小到大排列所有节点。如果score相同则按ele的字典序排序。backward (zskiplistNode*)后退指针。指向当前节点的前一个节点在层级0上。用于逆向遍历——比如ZREVRANGE命令。level[] (zskiplistLevel数组)这是跳跃表的灵魂。每个元素包含forward当前层上指向下一个节点的指针。当forwardNULL时表示当前层已到末尾span当前层上从当前节点到forward节点之间跨越了几个原始层节点。这个字段是Redis跳跃表独有的——用来快速计算排名2.3 zskiplistLevel中的span图解span字段的精确含义是在当前层上从当前节点走到forward节点在原始层level[0]上经过了多少个节点不含自身含forward。level[2]: [node A, span3] ──────────────── [node E, span2] ── NULL | | level[1]: [A, span2] ── [C, span2] ── [E, span2] ── [G, span0] | | | | level[0]: A ── B ── C ── D ── E ── F ── G ←────── backward指针方向 ←────── A在level[2]的span3 表示从A到E在level[0]上经过A→B→C→D→EA本身不算跨越了B,C,D,E共4个 但span的定义是含forward也就是 B,C,D,E 4不对... 实际上span A到E之间在level[0]上的节点数 不包含A本身但包含E所以 A→B→C→D→E 是经过了B,C,D的3跳后到达E 但通常span的语义是从A的forward到E跨越的节点数1。 简单理解span就是排名差。如果A的排名是1E的排名是5 那么A.level[2].span 5 - 1 4。实际上Redis源码中span的设计语义是node.level[i].forward指向下一个节点node.level[i].span等于从当前节点到下一个节点之间跨越的节点数包含下一个节点但不包含当前节点用来快速计算rank排名三、zskiplist跳跃表的管理结构3.1 结构体定义typedefstructzskiplist{structzskiplistNode*header,*tail;// 头尾节点指针unsignedlonglength;// 节点总数不含headerintlevel;// 当前最高层级}zskiplist;3.2 四字段详解字段类型作用headerzskiplistNode*指向跳跃表的头节点。注意header是一个特殊的哨兵节点不存实际数据tailzskiplistNode*指向最后一个实际节点。从tail通过backward指针可以逆序遍历lengthunsigned long跳跃表中实际节点的数量不含header。ZCARD命令直接读这个字段levelint当前最高的层级索引不含header的层。比如最高节点有3层level就是33.3 哨兵节点header的作用header不存数据但它拥有最高层级的level数组ZSKIPLIST_MAXLEVEL32。它的作用类似链表的dummy head——让所有插入/删除操作不需要特殊处理边界情况。zskiplist ------------------- | header ───────────┼────────────┐ ------------------- | | tail ─────────────┼──────┐ | ------------------- | | | length: 4 | | | ------------------- | | | level: 2 | | | ------------------- | | v v header(哨兵) node A node B node C node D ----------- ----------- ----------- ----------- ----------- | L2: fwd→A |--------| L2: fwd→D |----| L2: NULL | | L2: NULL | | L2: NULL | | L1: fwd→A |--------| L1: fwd→B |----| L1: fwd→D |--| L1: fwd→D |--| L1: NULL | | L0: fwd→A |--------| L0: fwd→B |----| L0: fwd→C |--| L0: fwd→D |--| L0: NULL | | backward | | backward←──|──┐ | backward←──|┐ | backward←──|┐ | backward | | ele: NULL | | ele: a | | | ele: b || | ele: c || | ele: d | | score: 0 | | score: 1.0 | | | score: 2.0 || | score: 3.0|| | score:4.0| ----------- ----------- | -----------| -----------| ----------- └───────────────┘ └─────────────┘ └───────────── (backward指针指向左边节点)四、span字段排名计算的关键4.1 为什么需要span标准跳跃表中没有span字段。但Redis的ZSet需要支持ZRANK命令——返回元素的排名。如果没有span你需要从头遍历整个层级0链表来数排名那是O(N)的。有了span计算排名变成O(log N)// 计算某个节点排名的核心逻辑unsignedlongzslGetRank(zskiplist*zsl,doublescore,sds ele){zskiplistNode*x;unsignedlongrank0;inti;xzsl-header;for(izsl-level-1;i0;i--){while(x-level[i].forward(x-level[i].forward-scorescore||(x-level[i].forward-scorescoresdscmp(x-level[i].forward-ele,ele)0))){rankx-level[i].span;// 累加spanxx-level[i].forward;// 前进}}returnrank;}4.2 span累加过程图查找 score55 的排名 初始化: rank0, xheader header.level[2].span3 ↓ ┌──────────────┴──────────────┐ | header | | L2: -[span3]-[40] | 40.score40 55 ✓ | L1: -[span2]-[20] ... | 但更高效的是走L2 | L0: -[span1]-[10] ... | ───────────────────────────── ① header的L2: forward是40, 40.score40 55 → rank span3, x40 ② 40的L2: forward是NULL → 降层 ③ 40的L1: forward60, 60.score60 ≥ 55 → 不前进降层 ④ 40的L0: forward50, 50.score50 55 → rank span1, rank4, x50 ⑤ 50的L0: forward55, 55.score55 ≤ 55 → rank span1, rank5 最终 rank 555的排名是第5位五、节点层高的随机算法5.1 幂次定律Power LawRedis跳跃表中节点层高由随机算法决定遵循幂次定律P(level 1) 1 (100%) P(level 2) 0.25 (25%) P(level 3) 0.25 * 0.25 0.0625 (6.25%) P(level 4) 0.25^3 0.0156 (1.56%) P(level 5) 0.25^4 ≈ 0.004 (0.4%) ... P(level 32) 0.25^31 ≈ 2.2 × 10^{-19} (几乎不可能)这意味着一百万个节点中期望层高分布如下层高期望节点数1750,0002187,500346,875411,71952,9306732……32接近05.2 Redis的随机层高实现#defineZSKIPLIST_P0.25// 晋升概率#defineZSKIPLIST_MAXLEVEL32// 最大层高intzslRandomLevel(void){intlevel1;// 每轮有25%的概率level1while((random()0xFFFF)(ZSKIPLIST_P*0xFFFF))level1;return(levelZSKIPLIST_MAXLEVEL)?level:ZSKIPLIST_MAXLEVEL;}解读random() 0xFFFF生成一个0~65535的随机数ZSKIPLIST_P * 0xFFFF 0.25 * 65535 ≈ 16384随机数 16384 的概率正好是25%所以每轮有25%概率层高175%概率停下来5.3 为什么选p0.25而不是0.5很多人直觉觉得p0.550%晋升概率更好——层数多跳得快。但Redis选择p0.25有深层原因指标p0.5p0.25 (Redis)平均层高~2~1.33内存开销每节点约2个forwardspan每节点约1.33个forwardspan查找性能O(log N)常数较小O(log N)常数稍大空间效率差好Redis选择p0.25是空间换时间的逆向操作——牺牲了一点查找速度常数因子换来了更好的内存利用率。毕竟Redis是内存数据库内存比CPU更金贵。六、跳跃表的四大操作6.1 查找查找是跳跃表的核心ZADD判断是否已存在、ZSCORE、ZRANK都依赖它。// 查找的简化逻辑zskiplistNode*zslFind(zskiplist*zsl,doublescore,sds ele){zskiplistNode*xzsl-header;// 从最高层开始逐层下降for(intizsl-level-1;i0;i--){while(x-level[i].forward(x-level[i].forward-scorescore||(x-level[i].forward-scorescoresdscmp(x-level[i].forward-ele,ele)0))){xx-level[i].forward;}}// x现在是目标位置的前一个节点xx-level[0].forward;if(xx-scorescoresdscmp(x-ele,ele)0){returnx;// 找到了}returnNULL;}时间复杂度O(log N)6.2 插入插入比查找多一步需要记录每层的前驱节点update数组和每层的排名rank数组// 插入的简化逻辑zskiplistNode*zslInsert(zskiplist*zsl,doublescore,sds ele){zskiplistNode*update[ZSKIPLIST_MAXLEVEL];// 每层的前驱节点unsignedlongrank[ZSKIPLIST_MAXLEVEL];// 每层前驱节点的排名zskiplistNode*xzsl-header;for(intizsl-level-1;i0;i--){// 初始化排名最顶层从头开始下层从上层的位置继续rank[i](izsl-level-1)?0:rank[i1];while(x-level[i].forward(x-level[i].forward-scorescore||...)){rank[i]x-level[i].span;// 累加spanxx-level[i].forward;// 前进}update[i]x;// 记录前驱}// 生成随机层高intlevelzslRandomLevel();if(levelzsl-level){// 新节点层高超过当前最高层更新header的更高层for(intizsl-level;ilevel;i){rank[i]0;update[i]zsl-header;update[i]-level[i].spanzsl-length;}zsl-levellevel;}// 创建新节点...// 在每层插入新节点更新forward/span和backward...}时间复杂度O(log N)6.3 删除删除的逻辑和插入类似——先找到每层的前驱节点然后逐层摘除// zslDelete的简化逻辑intzslDelete(zskiplist*zsl,doublescore,sds ele,zskiplistNode**node){zskiplistNode*update[ZSKIPLIST_MAXLEVEL];zskiplistNode*xzsl-header;for(intizsl-level-1;i0;i--){while(x-level[i].forward...){xx-level[i].forward;}update[i]x;}xx-level[0].forward;if(xscorex-scoresdscmp(ele,x-ele)0){// 逐层移除节点for(inti0;izsl-level;i){if(update[i]-level[i].forwardx){// 跳过xspan要调整update[i]-level[i].spanx-level[i].span-1;update[i]-level[i].forwardx-level[i].forward;}else{// x不在这一层span减1update[i]-level[i].span-1;}}// 更新backward指针// 释放节点内存return1;// 删除成功}return0;// 未找到}时间复杂度O(log N)6.4 遍历Redis支持正向和逆向遍历// 正向遍历ZRANGEzskiplistNode*xzsl-header-level[0].forward;// 第一个实际节点while(x){// 处理 x-ele, x-scorexx-level[0].forward;}// 逆向遍历ZREVRANGEzskiplistNode*xzsl-tail;// 最后一个节点while(x){// 处理 x-ele, x-scorexx-backward;}时间复杂度按需ZRANGE返回M个元素是O(M)但定位起点是O(log N)6.5 四大操作复杂度汇总操作时间复杂度说明查找O(log N)从最高层逐层下降每层跳过大量节点插入O(log N)先查找位置O(log N)再逐层插入O(level)删除O(log N)同插入先查找再逐层摘除遍历O(M)M为返回的元素个数定位起点O(log N)七、Redis跳跃表 vs 标准跳跃表特性标准跳跃表Redis跳跃表后退遍历不支持支持backward指针排名计算O(N)需遍历O(log N)span字段score唯一性通常要求唯一允许重复按ele字典序决定先后头节点可有可无固定有header哨兵节点层高上限无明确上限ZSKIPLIST_MAXLEVEL32晋升概率通常p0.5p0.25Redis跳表的三个独门秘技backward指针— 让逆序遍历成为可能实现ZREVRANGEspan字段— 让排名计算降为O(log N)实现ZRANK/ZREVRANKscore可重复— 通过ele的字典序作为二级排序依据八、ZADD/ZRANK/ZRANGE/ZRANGEBYSCORE与跳表的对应关系8.1 ZADD插入操作# 插入三个元素到有序集合127.0.0.1:6379ZADD leaderboard100alice200bob150charlie(integer)3底层三次zslInsert调用每次O(log N)。如果元素已存在则是更新score需要删除旧节点插入新节点相当于两次O(log N)操作。8.2 ZRANK排名查询127.0.0.1:6379ZRANK leaderboardcharlie(integer)1# charlie排第2排名从0开始127.0.0.1:6379ZRANK leaderboardalice(integer)0# alice排第1127.0.0.1:6379ZRANK leaderboardbob(integer)2# bob排第3底层zslGetRank函数利用span字段在O(log N)内算出排名。8.3 ZRANGE正向范围查询127.0.0.1:6379ZRANGE leaderboard0-1WITHSCORES1)alice2)1003)charlie4)1505)bob6)200底层先zslGetElementByRank定位起点O(log N)然后通过level[0].forward遍历返回O(M)M为返回元素数。8.4 ZRANGEBYSCORE按分值范围查询127.0.0.1:6379ZRANGEBYSCORE leaderboard100150WITHSCORES1)alice2)1003)charlie4)150底层通过跳表的查找逻辑定位到第一个score≥min的节点O(log N)然后遍历到scoremax为止O(M)。8.5 实操命令集# 创建有序集合添加数据127.0.0.1:6379ZADD students90张三85李四95王五88赵六(integer)4# 查看元素数量O(1)直接读zsl-length127.0.0.1:6379ZCARD students(integer)4# 查看某个元素的排名O(log N)利用span127.0.0.1:6379ZRANK students王五(integer)3# 王五排第40-based# 按排名范围查询O(log N M)127.0.0.1:6379ZRANGE students01WITHSCORES1)李四2)853)赵六4)88# 查看分值最高的前N名等同于ZREVRANGE127.0.0.1:6379ZREVRANGE students00WITHSCORES1)王五2)95九、跳跃表的优势与局限9.1 相比平衡树的优势维度跳跃表红黑树/AVL树实现复杂度低——核心代码约200行高——旋转重染色逻辑复杂范围查询天然支持——走level[0]就行需要中序遍历并发友好容易实现lock-free版本并发控制复杂调试难度低——结构直观高——红黑规则难验证常数因子稍大多层指针较小9.2 适用场景跳跃表最适合需要范围查询ZRANGEBYSCORE这类操作跳表天然支持需要排名查询ZRANKspan字段让排名计算降为O(log N)数据量大且动态变化插入/删除频繁跳表不用旋转可重复score排行榜场景很常见9.3 不适用场景内存极度受限的环境每个节点的level数组有额外开销纯粹的点查询且数据量不大的场景哈希表更合适十、总结跳跃表作为Redis有序集合的核心数据结构完美诠释了用概率替代确定的设计哲学多层索引用空间换时间将查找从O(N)降到O(log N)随机层高省去了平衡树的旋转操作代码量减少80%span字段让排名计算不再需要遍历O(log N)完成backward指针让逆序遍历成为可能补全了双向遍历能力p0.25的选择反映了Redis内存效率优先的价值观每次你在Redis里用ZADD给排行榜加分用ZRANGE查询Top N用ZRANK看某人的名次——背后都是这套精妙的跳跃表在默默运转。下一篇我们将进入跳跃表的对手视角——把跳跃表和平衡树放在一起正面PK看看在Redis的场景下谁才是真正的赢家。上一篇【第14篇】Rehash揭秘——Redis字典扩容缩容的精妙设计** 下一篇**【第16篇】跳跃表vs平衡树——谁才是有序集合的真正王者
【Redis从入门到精通】第15篇：跳跃表——有序集合背后的精妙数据结构
发布时间：2026/5/31 11:28:40
上一篇【第14篇】Rehash揭秘——Redis字典扩容缩容的精妙设计** 下一篇**【第16篇】跳跃表vs平衡树——谁才是有序集合的真正王者摘要跳跃表Skip List大概是Redis所有数据结构里最有趣的一个——它用一个随机算法每层晋升概率25%替代了平衡树的复杂旋转操作在保持O(log N)查找性能的同时代码却比红黑树简单了不止一个数量级。本文从William Pugh 1990年的原始论文讲起逐步拆解Redis跳跃表的zskiplistNode和zskiplist结构体重点剖析span字段的排名计算机制以及那个抛硬币决定层高的随机算法。最后通过ZADD/ZRANK/ZRANGE/ZRANGEBYSCORE命令演示跳跃表在Redis有序集合中的实际运作。一、跳跃表的起源一个天才的偷懒方案1.1 William Pugh的烦恼1990年马里兰大学的William Pugh教授面对一个难题平衡树AVL树、红黑树虽然查找快但实现起来太复杂了——旋转操作、颜色维护、各种边界条件随便写错一行代码就全盘皆崩。他的思路是既然平衡树的核心价值是跳过不必要的比较那能不能用更简单的方式达到同样的效果答案是给有序链表加多层索引。1.2 跳跃表的核心思想想象你在查一本字典。你不是从第一页开始逐页翻而是先在字母索引里找到R开头的页码范围在这个范围里再找到R-e-d的精确页码翻到那一页跳跃表做的就是类似的事——在基础链表之上建立多层快车道让你可以跳过大量不相关的节点快速定位到目标。普通有序链表找55需要走5步 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60 ① ② ③ ④ ⑤ ✓ 跳跃表加一层索引找55只需要走4步 索引层 10 ──────── 30 ──────── 50 ──────── NULL | | | 原始层 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60 ① ② ③ ④ ⑤ ✓ 走到索引的50后下一跳是NULL回头下到原始层继续走50→55完成。1.3 更高效的多层索引理想情况下每层的节点按一定比例选取形成类似金字塔的结构层级2 (每4个选1个) ────────────────── 40 ──────────────── NULL | 层级1 (每2个选1个) ──────── 20 ──────── 40 ──────── 60 ── NULL | | | 层级0 (全部节点) 10 ── 20 ── 30 ── 40 ── 50 ── 55 ── 60查找55的过程从最高层层级2开始40的下一个是NULL下降到层级140的下一个是6055在40处下降到层级040→50→55找到总共走了4步相比原始链表的5步数据量大时优势更加明显。二、zskiplistNode跳跃表的细胞2.1 结构体定义typedefstructzskiplistNode{sds ele;// 成员对象字符串doublescore;// 分值排序依据structzskiplistNode*backward;// 后退指针structzskiplistLevel{structzskiplistNode*forward;// 前进指针unsignedlongspan;// 跨度}level[];// 柔性数组——层级数组}zskiplistNode;2.2 每个字段的职责ele (sds)节点存储的元素是一个SDS字符串。注意这是成员和分值是两回事。score (double)排序依据。跳跃表按照score从小到大排列所有节点。如果score相同则按ele的字典序排序。backward (zskiplistNode*)后退指针。指向当前节点的前一个节点在层级0上。用于逆向遍历——比如ZREVRANGE命令。level[] (zskiplistLevel数组)这是跳跃表的灵魂。每个元素包含forward当前层上指向下一个节点的指针。当forwardNULL时表示当前层已到末尾span当前层上从当前节点到forward节点之间跨越了几个原始层节点。这个字段是Redis跳跃表独有的——用来快速计算排名2.3 zskiplistLevel中的span图解span字段的精确含义是在当前层上从当前节点走到forward节点在原始层level[0]上经过了多少个节点不含自身含forward。level[2]: [node A, span3] ──────────────── [node E, span2] ── NULL | | level[1]: [A, span2] ── [C, span2] ── [E, span2] ── [G, span0] | | | | level[0]: A ── B ── C ── D ── E ── F ── G ←────── backward指针方向 ←────── A在level[2]的span3 表示从A到E在level[0]上经过A→B→C→D→EA本身不算跨越了B,C,D,E共4个 但span的定义是含forward也就是 B,C,D,E 4不对... 实际上span A到E之间在level[0]上的节点数 不包含A本身但包含E所以 A→B→C→D→E 是经过了B,C,D的3跳后到达E 但通常span的语义是从A的forward到E跨越的节点数1。 简单理解span就是排名差。如果A的排名是1E的排名是5 那么A.level[2].span 5 - 1 4。实际上Redis源码中span的设计语义是node.level[i].forward指向下一个节点node.level[i].span等于从当前节点到下一个节点之间跨越的节点数包含下一个节点但不包含当前节点用来快速计算rank排名三、zskiplist跳跃表的管理结构3.1 结构体定义typedefstructzskiplist{structzskiplistNode*header,*tail;// 头尾节点指针unsignedlonglength;// 节点总数不含headerintlevel;// 当前最高层级}zskiplist;3.2 四字段详解字段类型作用headerzskiplistNode*指向跳跃表的头节点。注意header是一个特殊的哨兵节点不存实际数据tailzskiplistNode*指向最后一个实际节点。从tail通过backward指针可以逆序遍历lengthunsigned long跳跃表中实际节点的数量不含header。ZCARD命令直接读这个字段levelint当前最高的层级索引不含header的层。比如最高节点有3层level就是33.3 哨兵节点header的作用header不存数据但它拥有最高层级的level数组ZSKIPLIST_MAXLEVEL32。它的作用类似链表的dummy head——让所有插入/删除操作不需要特殊处理边界情况。zskiplist ------------------- | header ───────────┼────────────┐ ------------------- | | tail ─────────────┼──────┐ | ------------------- | | | length: 4 | | | ------------------- | | | level: 2 | | | ------------------- | | v v header(哨兵) node A node B node C node D ----------- ----------- ----------- ----------- ----------- | L2: fwd→A |--------| L2: fwd→D |----| L2: NULL | | L2: NULL | | L2: NULL | | L1: fwd→A |--------| L1: fwd→B |----| L1: fwd→D |--| L1: fwd→D |--| L1: NULL | | L0: fwd→A |--------| L0: fwd→B |----| L0: fwd→C |--| L0: fwd→D |--| L0: NULL | | backward | | backward←──|──┐ | backward←──|┐ | backward←──|┐ | backward | | ele: NULL | | ele: a | | | ele: b || | ele: c || | ele: d | | score: 0 | | score: 1.0 | | | score: 2.0 || | score: 3.0|| | score:4.0| ----------- ----------- | -----------| -----------| ----------- └───────────────┘ └─────────────┘ └───────────── (backward指针指向左边节点)四、span字段排名计算的关键4.1 为什么需要span标准跳跃表中没有span字段。但Redis的ZSet需要支持ZRANK命令——返回元素的排名。如果没有span你需要从头遍历整个层级0链表来数排名那是O(N)的。有了span计算排名变成O(log N)// 计算某个节点排名的核心逻辑unsignedlongzslGetRank(zskiplist*zsl,doublescore,sds ele){zskiplistNode*x;unsignedlongrank0;inti;xzsl-header;for(izsl-level-1;i0;i--){while(x-level[i].forward(x-level[i].forward-scorescore||(x-level[i].forward-scorescoresdscmp(x-level[i].forward-ele,ele)0))){rankx-level[i].span;// 累加spanxx-level[i].forward;// 前进}}returnrank;}4.2 span累加过程图查找 score55 的排名 初始化: rank0, xheader header.level[2].span3 ↓ ┌──────────────┴──────────────┐ | header | | L2: -[span3]-[40] | 40.score40 55 ✓ | L1: -[span2]-[20] ... | 但更高效的是走L2 | L0: -[span1]-[10] ... | ───────────────────────────── ① header的L2: forward是40, 40.score40 55 → rank span3, x40 ② 40的L2: forward是NULL → 降层 ③ 40的L1: forward60, 60.score60 ≥ 55 → 不前进降层 ④ 40的L0: forward50, 50.score50 55 → rank span1, rank4, x50 ⑤ 50的L0: forward55, 55.score55 ≤ 55 → rank span1, rank5 最终 rank 555的排名是第5位五、节点层高的随机算法5.1 幂次定律Power LawRedis跳跃表中节点层高由随机算法决定遵循幂次定律P(level 1) 1 (100%) P(level 2) 0.25 (25%) P(level 3) 0.25 * 0.25 0.0625 (6.25%) P(level 4) 0.25^3 0.0156 (1.56%) P(level 5) 0.25^4 ≈ 0.004 (0.4%) ... P(level 32) 0.25^31 ≈ 2.2 × 10^{-19} (几乎不可能)这意味着一百万个节点中期望层高分布如下层高期望节点数1750,0002187,500346,875411,71952,9306732……32接近05.2 Redis的随机层高实现#defineZSKIPLIST_P0.25// 晋升概率#defineZSKIPLIST_MAXLEVEL32// 最大层高intzslRandomLevel(void){intlevel1;// 每轮有25%的概率level1while((random()0xFFFF)(ZSKIPLIST_P*0xFFFF))level1;return(levelZSKIPLIST_MAXLEVEL)?level:ZSKIPLIST_MAXLEVEL;}解读random() 0xFFFF生成一个0~65535的随机数ZSKIPLIST_P * 0xFFFF 0.25 * 65535 ≈ 16384随机数 16384 的概率正好是25%所以每轮有25%概率层高175%概率停下来5.3 为什么选p0.25而不是0.5很多人直觉觉得p0.550%晋升概率更好——层数多跳得快。但Redis选择p0.25有深层原因指标p0.5p0.25 (Redis)平均层高~2~1.33内存开销每节点约2个forwardspan每节点约1.33个forwardspan查找性能O(log N)常数较小O(log N)常数稍大空间效率差好Redis选择p0.25是空间换时间的逆向操作——牺牲了一点查找速度常数因子换来了更好的内存利用率。毕竟Redis是内存数据库内存比CPU更金贵。六、跳跃表的四大操作6.1 查找查找是跳跃表的核心ZADD判断是否已存在、ZSCORE、ZRANK都依赖它。// 查找的简化逻辑zskiplistNode*zslFind(zskiplist*zsl,doublescore,sds ele){zskiplistNode*xzsl-header;// 从最高层开始逐层下降for(intizsl-level-1;i0;i--){while(x-level[i].forward(x-level[i].forward-scorescore||(x-level[i].forward-scorescoresdscmp(x-level[i].forward-ele,ele)0))){xx-level[i].forward;}}// x现在是目标位置的前一个节点xx-level[0].forward;if(xx-scorescoresdscmp(x-ele,ele)0){returnx;// 找到了}returnNULL;}时间复杂度O(log N)6.2 插入插入比查找多一步需要记录每层的前驱节点update数组和每层的排名rank数组// 插入的简化逻辑zskiplistNode*zslInsert(zskiplist*zsl,doublescore,sds ele){zskiplistNode*update[ZSKIPLIST_MAXLEVEL];// 每层的前驱节点unsignedlongrank[ZSKIPLIST_MAXLEVEL];// 每层前驱节点的排名zskiplistNode*xzsl-header;for(intizsl-level-1;i0;i--){// 初始化排名最顶层从头开始下层从上层的位置继续rank[i](izsl-level-1)?0:rank[i1];while(x-level[i].forward(x-level[i].forward-scorescore||...)){rank[i]x-level[i].span;// 累加spanxx-level[i].forward;// 前进}update[i]x;// 记录前驱}// 生成随机层高intlevelzslRandomLevel();if(levelzsl-level){// 新节点层高超过当前最高层更新header的更高层for(intizsl-level;ilevel;i){rank[i]0;update[i]zsl-header;update[i]-level[i].spanzsl-length;}zsl-levellevel;}// 创建新节点...// 在每层插入新节点更新forward/span和backward...}时间复杂度O(log N)6.3 删除删除的逻辑和插入类似——先找到每层的前驱节点然后逐层摘除// zslDelete的简化逻辑intzslDelete(zskiplist*zsl,doublescore,sds ele,zskiplistNode**node){zskiplistNode*update[ZSKIPLIST_MAXLEVEL];zskiplistNode*xzsl-header;for(intizsl-level-1;i0;i--){while(x-level[i].forward...){xx-level[i].forward;}update[i]x;}xx-level[0].forward;if(xscorex-scoresdscmp(ele,x-ele)0){// 逐层移除节点for(inti0;izsl-level;i){if(update[i]-level[i].forwardx){// 跳过xspan要调整update[i]-level[i].spanx-level[i].span-1;update[i]-level[i].forwardx-level[i].forward;}else{// x不在这一层span减1update[i]-level[i].span-1;}}// 更新backward指针// 释放节点内存return1;// 删除成功}return0;// 未找到}时间复杂度O(log N)6.4 遍历Redis支持正向和逆向遍历// 正向遍历ZRANGEzskiplistNode*xzsl-header-level[0].forward;// 第一个实际节点while(x){// 处理 x-ele, x-scorexx-level[0].forward;}// 逆向遍历ZREVRANGEzskiplistNode*xzsl-tail;// 最后一个节点while(x){// 处理 x-ele, x-scorexx-backward;}时间复杂度按需ZRANGE返回M个元素是O(M)但定位起点是O(log N)6.5 四大操作复杂度汇总操作时间复杂度说明查找O(log N)从最高层逐层下降每层跳过大量节点插入O(log N)先查找位置O(log N)再逐层插入O(level)删除O(log N)同插入先查找再逐层摘除遍历O(M)M为返回的元素个数定位起点O(log N)七、Redis跳跃表 vs 标准跳跃表特性标准跳跃表Redis跳跃表后退遍历不支持支持backward指针排名计算O(N)需遍历O(log N)span字段score唯一性通常要求唯一允许重复按ele字典序决定先后头节点可有可无固定有header哨兵节点层高上限无明确上限ZSKIPLIST_MAXLEVEL32晋升概率通常p0.5p0.25Redis跳表的三个独门秘技backward指针— 让逆序遍历成为可能实现ZREVRANGEspan字段— 让排名计算降为O(log N)实现ZRANK/ZREVRANKscore可重复— 通过ele的字典序作为二级排序依据八、ZADD/ZRANK/ZRANGE/ZRANGEBYSCORE与跳表的对应关系8.1 ZADD插入操作# 插入三个元素到有序集合127.0.0.1:6379ZADD leaderboard100alice200bob150charlie(integer)3底层三次zslInsert调用每次O(log N)。如果元素已存在则是更新score需要删除旧节点插入新节点相当于两次O(log N)操作。8.2 ZRANK排名查询127.0.0.1:6379ZRANK leaderboardcharlie(integer)1# charlie排第2排名从0开始127.0.0.1:6379ZRANK leaderboardalice(integer)0# alice排第1127.0.0.1:6379ZRANK leaderboardbob(integer)2# bob排第3底层zslGetRank函数利用span字段在O(log N)内算出排名。8.3 ZRANGE正向范围查询127.0.0.1:6379ZRANGE leaderboard0-1WITHSCORES1)alice2)1003)charlie4)1505)bob6)200底层先zslGetElementByRank定位起点O(log N)然后通过level[0].forward遍历返回O(M)M为返回元素数。8.4 ZRANGEBYSCORE按分值范围查询127.0.0.1:6379ZRANGEBYSCORE leaderboard100150WITHSCORES1)alice2)1003)charlie4)150底层通过跳表的查找逻辑定位到第一个score≥min的节点O(log N)然后遍历到scoremax为止O(M)。8.5 实操命令集# 创建有序集合添加数据127.0.0.1:6379ZADD students90张三85李四95王五88赵六(integer)4# 查看元素数量O(1)直接读zsl-length127.0.0.1:6379ZCARD students(integer)4# 查看某个元素的排名O(log N)利用span127.0.0.1:6379ZRANK students王五(integer)3# 王五排第40-based# 按排名范围查询O(log N M)127.0.0.1:6379ZRANGE students01WITHSCORES1)李四2)853)赵六4)88# 查看分值最高的前N名等同于ZREVRANGE127.0.0.1:6379ZREVRANGE students00WITHSCORES1)王五2)95九、跳跃表的优势与局限9.1 相比平衡树的优势维度跳跃表红黑树/AVL树实现复杂度低——核心代码约200行高——旋转重染色逻辑复杂范围查询天然支持——走level[0]就行需要中序遍历并发友好容易实现lock-free版本并发控制复杂调试难度低——结构直观高——红黑规则难验证常数因子稍大多层指针较小9.2 适用场景跳跃表最适合需要范围查询ZRANGEBYSCORE这类操作跳表天然支持需要排名查询ZRANKspan字段让排名计算降为O(log N)数据量大且动态变化插入/删除频繁跳表不用旋转可重复score排行榜场景很常见9.3 不适用场景内存极度受限的环境每个节点的level数组有额外开销纯粹的点查询且数据量不大的场景哈希表更合适十、总结跳跃表作为Redis有序集合的核心数据结构完美诠释了用概率替代确定的设计哲学多层索引用空间换时间将查找从O(N)降到O(log N)随机层高省去了平衡树的旋转操作代码量减少80%span字段让排名计算不再需要遍历O(log N)完成backward指针让逆序遍历成为可能补全了双向遍历能力p0.25的选择反映了Redis内存效率优先的价值观每次你在Redis里用ZADD给排行榜加分用ZRANGE查询Top N用ZRANK看某人的名次——背后都是这套精妙的跳跃表在默默运转。下一篇我们将进入跳跃表的对手视角——把跳跃表和平衡树放在一起正面PK看看在Redis的场景下谁才是真正的赢家。上一篇【第14篇】Rehash揭秘——Redis字典扩容缩容的精妙设计** 下一篇**【第16篇】跳跃表vs平衡树——谁才是有序集合的真正王者
