企业官网建设流程全解析

跳表(SkipList)底层: ZSet的ZADD为什么比平衡树更快？

引言: 一个被忽视的数据结构杰作

当我们需要有序集合时，大多数人首先想到的是红黑树或AVL树。但Redis的ZSet(Sorted Set)却选择了一个相对小众的数据结构——跳表(SkipList)。

这不是偶然。跳表在插入、删除、查找的平均时间复杂度都是O(logN)，与平衡树持平。但它的实现简单得多(没有旋转操作)，范围查询天然高效，支持无锁并发优化。更重要的是，Redis的跳表实现还做了独特的改进——在每一层增加了span字段来快速计算排名。

本节将深入跳表的底层结构，从原理到Redis源码实现，让你彻底理解为什么ZADD比平衡树更快。

一、跳表的基本结构

1.1 从链表到跳表: 空间换时间

/** * 跳表的核心思想: 多级索引加速查找 * * 查找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跳表

三、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; // } // // 概率: Level1=100%, Level2=25%, Level3=6.25%, Level4=1.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(span=2)"); System.out.println(" 累计排名 += 2"); System.out.println(" 2. Level 1: node1 → node2(span=1)"); 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(" 在查找过程中累加span，O(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(logN+M) | 底层双向链表顺序遍历 |

6.2 面试应答模板

问: Redis为什么用跳表而不是红黑树实现ZSet? 答: 三个核心原因: 1. 实现简单: 跳表约200行代码，红黑树约1000行。 没有旋转操作，bug少、好维护。 2. 范围查询友好: 跳表底层是双向链表， 找到起点后顺序遍历即可。 ZRANGE复杂度O(logN+M)且常数小。 3. 并发友好: 跳表更容易实现无锁操作。 虽然Redis本身是单线程，但设计上预留了扩展性。 补充: Redis跳表还做了独特优化: - span字段: 快速计算排名(ZRANK O(logN)) - 25%概率: 减少内存占用 - ZSet使用跳表+哈希表组合

---

如果本文帮你理解了跳表的底层原理和Redis的设计选择，欢迎点赞收藏。有任何疑问，欢迎评论区交流！