网站导航
> 技术文档 > Redis跳表解密:比平衡树快3倍的排序黑科技

Redis跳表解密:比平衡树快3倍的排序黑科技

网友: 技术文档 2025-09-02 19:05:45

💡 一句话真相:跳表(SkipList)就是给链表装上\"地铁快线\"🚇——多层轨道让查询速度飙升，实现复杂度却只有平衡树的1/10！

🔧 一、为什么Redis不用平衡树而选跳表？

真实性能对比（百万数据查询）:

数据结构 插入耗时 查询耗时 实现复杂度 红黑树 1.8s 0.3ms 高（500行+） 跳表 0.9s 0.4ms 低（200行）

Redis的选择理由:

  1. 范围查询优势:ZRANGE操作比平衡树快5倍
  2. 实现简单:调试成本降低70%
  3. 天然有序:完美契合Sorted Set需求

🏗️ 二、跳表核心原理:给链表加\"高速索引\"

1. 原始链表（慢如自行车）

#mermaid-svg-pOKODLewo9E3nQd1 {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .error-icon{fill:#552222;}#mermaid-svg-pOKODLewo9E3nQd1 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-pOKODLewo9E3nQd1 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-pOKODLewo9E3nQd1 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-pOKODLewo9E3nQd1 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-pOKODLewo9E3nQd1 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-pOKODLewo9E3nQd1 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-pOKODLewo9E3nQd1 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-pOKODLewo9E3nQd1 .marker.cross{stroke:#333333;}#mermaid-svg-pOKODLewo9E3nQd1 svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-pOKODLewo9E3nQd1 .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .cluster-label text{fill:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .cluster-label span{color:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .label text,#mermaid-svg-pOKODLewo9E3nQd1 span{fill:#333;color:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .node rect,#mermaid-svg-pOKODLewo9E3nQd1 .node circle,#mermaid-svg-pOKODLewo9E3nQd1 .node ellipse,#mermaid-svg-pOKODLewo9E3nQd1 .node polygon,#mermaid-svg-pOKODLewo9E3nQd1 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-pOKODLewo9E3nQd1 .node .label{text-align:center;}#mermaid-svg-pOKODLewo9E3nQd1 .node.clickable{cursor:pointer;}#mermaid-svg-pOKODLewo9E3nQd1 .arrowheadPath{fill:#333333;}#mermaid-svg-pOKODLewo9E3nQd1 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-pOKODLewo9E3nQd1 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-pOKODLewo9E3nQd1 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-pOKODLewo9E3nQd1 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-pOKODLewo9E3nQd1 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-pOKODLewo9E3nQd1 .cluster text{fill:#333;}#mermaid-svg-pOKODLewo9E3nQd1 .cluster span{color:#333;}#mermaid-svg-pOKODLewo9E3nQd1 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-pOKODLewo9E3nQd1 :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;}13579

查询数字7需要遍历4个节点 → O(N)

2. 跳表结构（升级为地铁网）

#mermaid-svg-1yIMHNSGT2FtBW3E {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .error-icon{fill:#552222;}#mermaid-svg-1yIMHNSGT2FtBW3E .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1yIMHNSGT2FtBW3E .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-1yIMHNSGT2FtBW3E .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1yIMHNSGT2FtBW3E .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1yIMHNSGT2FtBW3E .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1yIMHNSGT2FtBW3E .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1yIMHNSGT2FtBW3E .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1yIMHNSGT2FtBW3E .marker.cross{stroke:#333333;}#mermaid-svg-1yIMHNSGT2FtBW3E svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1yIMHNSGT2FtBW3E .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .cluster-label text{fill:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .cluster-label span{color:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .label text,#mermaid-svg-1yIMHNSGT2FtBW3E span{fill:#333;color:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .node rect,#mermaid-svg-1yIMHNSGT2FtBW3E .node circle,#mermaid-svg-1yIMHNSGT2FtBW3E .node ellipse,#mermaid-svg-1yIMHNSGT2FtBW3E .node polygon,#mermaid-svg-1yIMHNSGT2FtBW3E .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1yIMHNSGT2FtBW3E .node .label{text-align:center;}#mermaid-svg-1yIMHNSGT2FtBW3E .node.clickable{cursor:pointer;}#mermaid-svg-1yIMHNSGT2FtBW3E .arrowheadPath{fill:#333333;}#mermaid-svg-1yIMHNSGT2FtBW3E .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-1yIMHNSGT2FtBW3E .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-1yIMHNSGT2FtBW3E .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-1yIMHNSGT2FtBW3E .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-1yIMHNSGT2FtBW3E .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-1yIMHNSGT2FtBW3E .cluster text{fill:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E .cluster span{color:#333;}#mermaid-svg-1yIMHNSGT2FtBW3E div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-1yIMHNSGT2FtBW3E :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;}L4:9L3:9L2:9L1:9

查询数字7的路径:
L4(1) → L4(9) 太大 → 降级到L3
L3(1) → L3(5) → L3(9) 太大 → 降级到L2
L2(5) → L2(7) 命中！ 仅3步 → O(logN)

⚙️ 三、跳表实现四步拆解

🔑 1. 节点结构设计（C源码精简版）
typedef struct zskiplistNode { robj *obj;// 存储的值（如\"玩家A\"）  double score;  // 排序分值（如95.5）  struct zskiplistNode *backward; // 后向指针（L0层）  struct zskiplistLevel { // 层级数组  struct zskiplistNode *forward; // 前向指针  unsigned int span; // 到下一个节点的跨度  } level[];// 柔性数组，长度随机 } zskiplistNode;
🎲 2. 层高随机生成算法（核心！）

Redis跳表解密:比平衡树快3倍的排序黑科技

代码实现:

int zslRandomLevel(void) { int level = 1; // 0.25概率升级  while ((random()&0xFFFF) < (0.25 * 0xFFFF) && level < 32) level++; return level; }

概率分布:

层数 概率 类比 1 75% 公交站（每站停） 2 18.75% 地铁快线（隔站停） 3 4.69% 高铁（跨城） ≥4 <1% 飞机（跨省）
🔍 3. 查询过程图解

#mermaid-svg-OWXEv3N7rxHEVkGF {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF .error-icon{fill:#552222;}#mermaid-svg-OWXEv3N7rxHEVkGF .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OWXEv3N7rxHEVkGF .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-OWXEv3N7rxHEVkGF .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OWXEv3N7rxHEVkGF .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OWXEv3N7rxHEVkGF .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OWXEv3N7rxHEVkGF .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OWXEv3N7rxHEVkGF .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OWXEv3N7rxHEVkGF .marker.cross{stroke:#333333;}#mermaid-svg-OWXEv3N7rxHEVkGF svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OWXEv3N7rxHEVkGF .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-OWXEv3N7rxHEVkGF text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-OWXEv3N7rxHEVkGF .actor-line{stroke:grey;}#mermaid-svg-OWXEv3N7rxHEVkGF .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF .sequenceNumber{fill:white;}#mermaid-svg-OWXEv3N7rxHEVkGF #sequencenumber{fill:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF .messageText{fill:#333;stroke:#333;}#mermaid-svg-OWXEv3N7rxHEVkGF .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-OWXEv3N7rxHEVkGF .labelText,#mermaid-svg-OWXEv3N7rxHEVkGF .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-OWXEv3N7rxHEVkGF .loopText,#mermaid-svg-OWXEv3N7rxHEVkGF .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-OWXEv3N7rxHEVkGF .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-OWXEv3N7rxHEVkGF .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-OWXEv3N7rxHEVkGF .noteText,#mermaid-svg-OWXEv3N7rxHEVkGF .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-OWXEv3N7rxHEVkGF .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-OWXEv3N7rxHEVkGF .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-OWXEv3N7rxHEVkGF .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-OWXEv3N7rxHEVkGF .actorPopupMenu{position:absolute;}#mermaid-svg-OWXEv3N7rxHEVkGF .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-OWXEv3N7rxHEVkGF .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-OWXEv3N7rxHEVkGF .actor-man circle,#mermaid-svg-OWXEv3N7rxHEVkGF line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-OWXEv3N7rxHEVkGF :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;}客户端跳表头节点头节点L3L2节点5节点7查询score=7的节点当前层向后查找下一个节点score=9 >7降级到L2向后到score=5向后到score=7返回找到的节点客户端跳表头节点头节点L3L2节点5节点7

➕ 4. 插入节点流程

#mermaid-svg-OikFgdj9OaATlfPC {font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-OikFgdj9OaATlfPC .error-icon{fill:#552222;}#mermaid-svg-OikFgdj9OaATlfPC .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-OikFgdj9OaATlfPC .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-OikFgdj9OaATlfPC .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-OikFgdj9OaATlfPC .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-OikFgdj9OaATlfPC .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-OikFgdj9OaATlfPC .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-OikFgdj9OaATlfPC .marker{fill:#333333;stroke:#333333;}#mermaid-svg-OikFgdj9OaATlfPC .marker.cross{stroke:#333333;}#mermaid-svg-OikFgdj9OaATlfPC svg{font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-OikFgdj9OaATlfPC .label{font-family:\"trebuchet ms\",verdana,arial,sans-serif;color:#333;}#mermaid-svg-OikFgdj9OaATlfPC .cluster-label text{fill:#333;}#mermaid-svg-OikFgdj9OaATlfPC .cluster-label span{color:#333;}#mermaid-svg-OikFgdj9OaATlfPC .label text,#mermaid-svg-OikFgdj9OaATlfPC span{fill:#333;color:#333;}#mermaid-svg-OikFgdj9OaATlfPC .node rect,#mermaid-svg-OikFgdj9OaATlfPC .node circle,#mermaid-svg-OikFgdj9OaATlfPC .node ellipse,#mermaid-svg-OikFgdj9OaATlfPC .node polygon,#mermaid-svg-OikFgdj9OaATlfPC .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-OikFgdj9OaATlfPC .node .label{text-align:center;}#mermaid-svg-OikFgdj9OaATlfPC .node.clickable{cursor:pointer;}#mermaid-svg-OikFgdj9OaATlfPC .arrowheadPath{fill:#333333;}#mermaid-svg-OikFgdj9OaATlfPC .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-OikFgdj9OaATlfPC .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-OikFgdj9OaATlfPC .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-OikFgdj9OaATlfPC .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-OikFgdj9OaATlfPC .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-OikFgdj9OaATlfPC .cluster text{fill:#333;}#mermaid-svg-OikFgdj9OaATlfPC .cluster span{color:#333;}#mermaid-svg-OikFgdj9OaATlfPC div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\"trebuchet ms\",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-OikFgdj9OaATlfPC :root{--mermaid-font-family:\"trebuchet ms\",verdana,arial,sans-serif;}计算新节点层高查找插入位置保存搜索路径连接前后指针更新跨度值

关键代码:

// 保存每层的前驱节点 zskiplistNode *update[32]; // 查找插入位置 for (int i = zsl->level-1; i >= 0; i--) { while (next && next->score < score) { prev = next; next = next->level[i].forward; } update[i] = prev; // 记录路径 }

📊 四、跳表 vs 平衡树:三大关键差异

特性 跳表 红黑树 范围查询 ⭐⭐⭐ 顺序遍历即可 ⭐⭐ 需中序遍历 实现复杂度 ⭐⭐ 200行代码 ⭐⭐⭐ 500+行代码 内存占用 ⭐⭐ 额外存储层指针 ⭐ 仅左右孩子指针 插入删除 ⭐⭐⭐ 只需修改相邻指针 ⭐⭐ 需旋转+变色 调试难度 ⭐ 肉眼可见结构 ⭐⭐⭐ 复杂旋转逻辑

⚠️ 五、跳表使用避坑指南

🚫 坑1:层高参数设置不合理

错误配置:

# redis.conf 错误设置 zset-max-ziplist-entries 0 # 强制所有Sorted Set用跳表

后果:小数据集内存暴增3倍！

优化方案:

zset-max-ziplist-entries 128 # ≤128元素用压缩列表 zset-max-ziplist-value 64 # 元素≤64字节用压缩列表
🚫 坑2:大对象存储导致性能骤降

测试数据对比:

成员大小 插入QPS 内存占用（百万成员） 16字节 85,000 64MB 1KB 9,200 1.8GB 黄金法则:Sorted Set成员值≤64字节

💡 六、高频面试题解析

❓ 问题1:为什么Redis跳表最高32层？

答案:

  • 232足够覆盖20亿数据（log₂(232)=32）
  • 超过32层概率低于1/2^32（≈0.000000023%）
❓ 问题2:跳表层数为什么用随机而不用固定？

答案:

  • 固定层级会导致插入效率退化（极端情况退化成单链表）
  • 随机分布保证概率均衡，查询效率稳定在O(logN)

🌟 七、总结:跳表设计的精妙之处

  1. 空间换时间:额外指针带来查询飞跃
  2. 随机平衡:用概率代替复杂旋转操作
  3. 渐进更新:插入只需修改相邻节点
  4. 层级压缩:高层索引跳过无效遍历

🔧 Redis的选择智慧:在工程中，足够好且简单 > 理论最优但复杂

Redis跳表解密:比平衡树快3倍的排序黑科技

#Redis源码 #数据结构 #算法
👉 关注我，解锁《Redis核心数据结构深度解析》系列！

网络标签：

相关问题