跳表(SkipList)底层: ZSet的ZADD为什么比平衡树更快引言: 一个被忽视的数据结构杰作当我们需要有序集合时大多数人首先想到的是红黑树或AVL树。但Redis的ZSet(Sorted Set)却选择了一个相对小众的数据结构——跳表(SkipList)。这不是偶然。跳表在插入、删除、查找的平均时间复杂度都是O(logN)与平衡树持平。但它的实现简单得多(没有旋转操作)范围查询天然高效支持无锁并发优化。更重要的是Redis的跳表实现还做了独特的改进——在每一层增加了span字段来快速计算排名。本节将深入跳表的底层结构从原理到Redis源码实现让你彻底理解为什么ZADD比平衡树更快。一、跳表的基本结构1.1 从链表到跳表: 空间换时间第二层索引(每4个取1个)第一层索引(每2个取1个)原始有序链表(查询O(n))1357911131591319/** * 跳表的核心思想: 多级索引加速查找 * * 查找7的过程: * 1. 从最高层开始: 1 → 9 (大于7回退到1) * 2. 下降到第一层: 1 → 5 → 9 (大于7回退到5) * 3. 下降到原始链表: 5 → 7 (找到!) * * 比较了3次 vs 原始链表需要4次 * 数据量越大优势越明显! */ public class SkipListCoreIdea { public static void main(String[] args) { System.out.println( 跳表核心思想 \n); System.out.println(跳表 有序链表 多级索引\n); System.out.println(类比: 地铁线路图); System.out.println( 快线(高层索引): 只停大站快速跨越大段距离); System.out.println( 慢线(底层链表): 每站都停精确定位); System.out.println( 换乘: 从高层下降到低层\n); System.out.println(复杂度分析:); System.out.println( 查找: O(logN) - 从高层跳跃低层精确定位); System.out.println( 插入: O(logN) - 先查找位置再随机生成层数插入); System.out.println( 删除: O(logN) - 先查找再从各层移除); System.out.println( 范围查询: O(logN M) - M是返回元素数); } }二、Redis跳表的数据结构2.1 核心结构定义// Redis跳表节点 (源码: server.h) typedef struct zskiplistNode { sds ele; // 成员对象(字符串) double score; // 分值(排序依据) struct zskiplistNode *backward; // 后退指针(双向链表) struct zskiplistLevel { struct zskiplistNode *forward; // 前进指针 unsigned long span; // 跨度(该层到下一个节点的距离) } level[]; // 柔性数组每层一个 } zskiplistNode; // 跳表结构 typedef struct zskiplist { struct zskiplistNode *header, *tail; // 头尾节点 unsigned long length; // 节点数量 int level; // 最大层数(不含header) } zskiplist;/** * Redis跳表节点的Java示意 */ public class RedisSkipListStructure { // 跳表节点 static class SkipListNode { String element; // 存储的元素 double score; // 分值 SkipListNode backward; // 后退指针 // 层级数组(每层包含前进指针和跨度) Level[] levels; static class Level { SkipListNode forward; // 前进指针 int span; // 跨度(到forward节点的距离) } SkipListNode(String element, double score, int maxLevel) { this.element element; this.score score; this.levels new Level[maxLevel]; for (int i 0; i maxLevel; i) { levels[i] new Level(); } } } // 跳表结构 static class SkipList { SkipListNode header; // 头节点(不存储数据) SkipListNode tail; // 尾节点 long length; // 节点数量 int level; // 当前最大层数 } public static void main(String[] args) { System.out.println( Redis跳表结构特点 \n); System.out.println(1. 基于分值(score)排序); System.out.println( - score相同则按元素字典序排序\n); System.out.println(2. 后退指针(backward)); System.out.println( - 构成双向链表); System.out.println( - 方便逆序范围查询(ZREVRANGE)\n); System.out.println(3. 跨度(span)字段 ★Redis独创★); System.out.println( - 记录本层到下一个节点的距离); System.out.println( - 快速计算排名(ZRANK)); System.out.println( - 是Redis跳表区别于标准跳表的关键!\n); System.out.println(4. 头节点特殊); System.out.println( - 不存储数据但拥有最大层数(64层)); System.out.println( - 每层的前进指针指向实际数据节点); } }2.2 可视化: 一个实际的Redis跳表RedisZSet跳表示例Level0(原始链表)Level1Level2HeaderHeaderscore:10ele:applescore:30ele:orangeNULLHeaderscore:10ele:applescore:20ele:bananascore:30ele:orangeNULLscore:10ele:applescore:20ele:bananascore:30ele:orangeNULL三、ZADD插入流程3.1 完整的插入步骤/** * ZADD的完整流程 * * Redis源码: t_zset.c 中的 zslInsert() 函数 */ public class ZADDProcess { // 简化的插入逻辑 public SkipListNode zslInsert(SkipList zsl, double score, String element) { // 步骤1: 从高层到低层查找插入位置 SkipListNode[] update new SkipListNode[ZSKIPLIST_MAXLEVEL]; // 记录每层的插入位置 int[] rank new int[ZSKIPLIST_MAXLEVEL]; // 记录每层走过的总步数 SkipListNode x zsl.header; for (int i zsl.level - 1; i 0; i--) { // 从高层开始逐层下降 rank[i] (i zsl.level - 1) ? 0 : rank[i 1]; while (x.levels[i].forward ! null (x.levels[i].forward.score score || (x.levels[i].forward.score score x.levels[i].forward.element.compareTo(element) 0))) { rank[i] x.levels[i].span; x x.levels[i].forward; } update[i] x; // 记录该层插入位置的前驱节点 } // 步骤2: 随机生成新节点的层数 int level zslRandomLevel(); // 随机算法: 每层50%概率 // 步骤3: 从各层插入新节点 if (level zsl.level) { // 新节点层数超过当前最大层数header需要补充层 for (int i zsl.level; i level; i) { rank[i] 0; update[i] zsl.header; update[i].levels[i].span zsl.length; } zsl.level level; } SkipListNode newNode new SkipListNode(element, score, level); for (int i 0; i level; i) { // 在各层插入新节点(类似链表插入) newNode.levels[i].forward update[i].levels[i].forward; update[i].levels[i].forward newNode; // 更新跨度(span) newNode.levels[i].span update[i].levels[i].span - (rank[0] - rank[i]); update[i].levels[i].span (rank[0] - rank[i]) 1; } // 步骤4: 更新未触及层的跨度 for (int i level; i zsl.level; i) { update[i].levels[i].span; } // 步骤5: 设置后退指针 newNode.backward (update[0] zsl.header) ? null : update[0]; if (newNode.levels[0].forward ! null) { newNode.levels[0].forward.backward newNode; } else { zsl.tail newNode; } zsl.length; return newNode; } // 随机层数生成(Redis核心算法) // #define ZSKIPLIST_P 0.25 // int zslRandomLevel(void) { // int level 1; // while ((random() 0xFFFF) (ZSKIPLIST_P * 0xFFFF)) // level 1; // return (level ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL; // } // // 概率: Level1100%, Level225%, Level36.25%, Level41.56%... public static void main(String[] args) { System.out.println( ZADD插入流程 \n); System.out.println(核心步骤:); System.out.println(1. 从最高层向下查找插入位置(记录update数组)); System.out.println(2. 随机生成层数(概率: 每层25%)); System.out.println(3. 在各层插入新节点(更新forward指针和span)); System.out.println(4. 更新高层跨度); System.out.println(5. 设置后退指针\n); System.out.println(时间复杂度: O(logN)); System.out.println(- 查找: O(logN)); System.out.println(- 插入: O(1) - 只是链表插入操作); System.out.println(- 平衡: 不需要! 随机层数天然保证平衡); } }3.2 span字段的计算/** * Span(跨度)字段的作用和计算 * * Span是Redis跳表区别于标准跳表的关键创新 * 它让ZRANK(ZREVRANK)操作从O(N)优化到O(logN) */ public class SpanCalculation { public static void main(String[] args) { System.out.println( Span字段详解 \n); System.out.println(Span的含义:); System.out.println( 该节点在某层到下一个节点的距离); System.out.println( (在原始链表中跨越的节点数)\n); System.out.println(例如: 计算元素orange的排名\n); System.out.println( 从头节点开始从最高层遍历:); System.out.println( 1. Level 2: header → node1(span2)); System.out.println( 累计排名 2); System.out.println( 2. Level 1: node1 → node2(span1)); System.out.println( 累计排名 1); System.out.println( 3. 找到orange排名 3\n); System.out.println(如果没有span字段:); System.out.println( 需要从头遍历整个链表O(N)); System.out.println(有了span字段:); System.out.println( 在查找过程中累加spanO(logN)); } }四、跳表 vs 平衡树4.1 对比分析/** * 跳表 vs 红黑树 vs AVL树 */ public class SkipListVsBalancedTree { public static void main(String[] args) { System.out.println( 跳表 vs 平衡树 \n); System.out.println(┌──────────────┬──────────────┬──────────────┐); System.out.println(│ 特性 │ 跳表 │ 平衡树 │); System.out.println(├──────────────┼──────────────┼──────────────┤); System.out.println(│ 查找 │ O(logN) │ O(logN) │); System.out.println(│ 插入 │ O(logN) │ O(logN) │); System.out.println(│ 删除 │ O(logN) │ O(logN) │); System.out.println(│ 实现复杂度 │ 简单 │ 复杂 │); System.out.println(│ 平衡维护 │ 不需要 │ 需要旋转 │); System.out.println(│ 范围查询 │ 天然高效 │ 中序遍历 │); System.out.println(│ 并发支持 │ 容易 │ 困难 │); System.out.println(│ 排名计算 │ 需span字段 │ 需size字段 │); System.out.println(│ 内存占用 │ 较高(指针多)│ 较低 │); System.out.println(└──────────────┴──────────────┴──────────────┘\n); System.out.println(Redis选择跳表的核心原因:\n); System.out.println(1. 实现简单); System.out.println( 跳表核心代码约200行); System.out.println( 红黑树核心代码约1000行); System.out.println( 简单意味着bug少、好维护\n); System.out.println(2. 不需要旋转); System.out.println( 跳表通过随机层数自然平衡); System.out.println( 平衡树需要复杂的旋转操作); System.out.println( 旋转在多线程环境下更难处理\n); System.out.println(3. 范围查询友好); System.out.println( 跳表底层是双向链表); System.out.println( 找到起点后顺序遍历即可); System.out.println( ZRANGE操作: O(logN M)\n); System.out.println(4. 并发优化潜力大); System.out.println( 跳表更容易实现无锁操作); System.out.println( Java ConcurrentSkipListMap 就是无锁实现); } }4.2 为什么范围查询跳表更优/** * 范围查询性能对比 * * 跳表: 底层是双向链表天然支持顺序遍历 * 平衡树: 需要中序遍历实现复杂 */ public class RangeQueryComparison { public static void main(String[] args) { System.out.println( 范围查询对比 \n); System.out.println(ZRANGE key 0 99 (取前100个元素)\n); System.out.println(跳表执行:); System.out.println( 1. 从header开始查找第1个元素 → O(logN)); System.out.println( 2. 顺着Level 0的双向链表向后遍历100个 → O(M)); System.out.println( 3. 总复杂度: O(logN M)\n); System.out.println(平衡树执行:); System.out.println( 1. 找到最小节点 → O(logN)); System.out.println( 2. 中序遍历找到前100个 → O(M)); System.out.println( 但需要维护栈或parent指针); System.out.println( 3. 总复杂度: O(logN M)但常数更大\n); System.out.println(跳表优势:); System.out.println( - 底层就是链表直接顺序走); System.out.println( - 不需要回溯parent节点); System.out.println( - backward指针支持反向遍历); } }五、Redis跳表的独特优化5.1 幂次定律的层数生成/** * Redis跳表层数生成的幂次定律 * * 标准跳表: 每层50%概率(像抛硬币) * Redis跳表: 每层25%概率(ZSKIPLIST_P 0.25) * * 为什么Redis用25%? * - 减少层数减少内存占用 * - 每层跨度更大跳跃更快 * - 实测25%在Redis场景下性能最优 */ public class PowerLawDistribution { public static void main(String[] args) { System.out.println( Redis跳表层数分布 \n); System.out.println(ZSKIPLIST_P 0.25); System.out.println(最大层数 64\n); System.out.println(层数分布(理论):); System.out.println( Level 1: 100%); System.out.println( Level 2: 25%); System.out.println( Level 3: 6.25%); System.out.println( Level 4: 1.56%); System.out.println( Level 5: 0.39%); System.out.println( ...); System.out.println( Level 64: 几乎不可能\n); System.out.println(优势:); System.out.println( - 高层节点少查找跳跃幅度大); System.out.println( - 平均层数 ≈ 1/(1-0.25) ≈ 1.33层); System.out.println( - 内存开销远小于50%概率); } }5.2 跳表在ZSet中的应用/** * Redis ZSet使用跳表哈希表组合 * * ZSet同时使用: * - 跳表: 按score排序支持范围查询、排名操作 * - 哈希表: 按member快速查找(O(1)获取score) */ public class ZSetDataStructure { public static void main(String[] args) { System.out.println( ZSet的双重数据结构 \n); System.out.println(ZSet 跳表 哈希表(dict)\n); System.out.println(跳表的作用:); System.out.println( - ZRANGE: 按排名范围查询); System.out.println( - ZRANGEBYSCORE: 按分值范围查询); System.out.println( - ZRANK: 查询元素排名); System.out.println( - 所有基于顺序的操作\n); System.out.println(哈希表的作用:); System.out.println( - ZSCORE: O(1)获取元素分值); System.out.println( - 快速判断元素是否存在); System.out.println( - 删除时快速定位跳表节点\n); System.out.println(两者协作:); System.out.println( ZADD: 先查哈希表(是否已存在)); System.out.println( 再更新/插入跳表); System.out.println( ZSCORE: 直接查哈希表O(1)); System.out.println( ZRANK: 只查跳表O(logN)); } }六、总结6.1 跳表核心速查| 操作 | 时间复杂度 | 实现要点 ||------|-----------|---------|| ZADD(插入) | O(logN) | 随机层数 多级链表插入 || ZREM(删除) | O(logN) | 多级链表删除 || ZSCORE(查分值) | O(1) | 使用哈希表不是跳表 || ZRANK(查排名) | O(logN) | 利用span字段累加 || ZRANGE(范围) | O(logNM) | 底层双向链表顺序遍历 |6.2 面试应答模板问: Redis为什么用跳表而不是红黑树实现ZSet? 答: 三个核心原因: 1. 实现简单: 跳表约200行代码红黑树约1000行。 没有旋转操作bug少、好维护。 2. 范围查询友好: 跳表底层是双向链表 找到起点后顺序遍历即可。 ZRANGE复杂度O(logNM)且常数小。 3. 并发友好: 跳表更容易实现无锁操作。 虽然Redis本身是单线程但设计上预留了扩展性。 补充: Redis跳表还做了独特优化: - span字段: 快速计算排名(ZRANK O(logN)) - 25%概率: 减少内存占用 - ZSet使用跳表哈希表组合---如果本文帮你理解了跳表的底层原理和Redis的设计选择欢迎点赞收藏。有任何疑问欢迎评论区交流