面经策

Redis 中跳表的实现原理是什么？ ​

  • 标签：后端、Redis

🏛 业务架构师 ​

跳表（Skip List）是多层链表结构：底层是完整有序链表，上层抽取部分节点做"快速通道"，查找从最高层往右、往下逐层逼近目标，O(logN)。节点层数按概率随机决定（每层晋升概率 1/4），插入删除只改前后指针。

为什么 ZSet 用跳表而不是红黑树——Redis 作者 antirez 的取舍理由很有业务味道：

  • 实现简单：跳表代码量约为平衡树的几分之一，没有旋转、变色这些易错操作——基础设施软件，简单性直接等于低缺陷率；
  • 范围查询天然友好：定位起点后沿底层链表顺序遍历即可（ZRANGE 榜单区间取值），平衡树需要中序遍历回溯；
  • 内存可调：晋升概率控制层数，空间开销可预期。

业务落地：跳表就是排行榜、延迟队列（score 存执行时间戳）、带权重的有序集合这些场景的引擎。ZRANGEBYSCORE 取一段、ZADD 实时更新，运营活动里的"实时榜单"全部建立在它上面。

架构启示值得强调：技术选型时"实现简单、好维护"的权重经常被低估。红黑树理论性能与跳表同阶，但复杂度成本高——一旦出现并发 bug 或内存问题，修复难度天差地别。我评审自研组件时的必问问题就是："有没有更笨但更稳的方案"。跳表用概率换确定性结构，这个"工程上够好优于理论上最优"的思路，和业务架构里"简单方案先落地、复杂方案等规模"是同一个哲学。

🏗 系统架构师 ​

跳表是有序集合的"概率平衡"结构，ZSet 底层（与 listpack/ziplist 按大小自适应切换）：

结构：每个节点随机生成层高（每层指针指向右侧更远的节点），平均 1.33 个指针/节点。多层链表形成"高速公路 + 慢速路"：

  • 查找：从最高层起步，逐层向右试探、不行就下一层，平均 O(logN)——像二分但靠概率而非旋转维护平衡；
  • 插入/删除：先查找定位（记录每层前驱），局部改指针即可，无需全局再平衡。

为什么 Redis 不用红黑树（必被追问）：功能上跳表范围查询（ZRANGE）天然顺链走，红黑树要中序遍历；实现上跳表简单得多（无旋转/变色），易于调试、控制和加层扩展；并发上锁粒度友好。作者 antirez 的原话就是"实现简单 + 范围操作直观 + 内存可控（可配节点层高上限 64、概率 1/4）"。

架构对比：跳表用 O(n) 额外指针换实现简单性，红黑树用实现复杂度换最坏情况严格保证——ConcurrentSkipListMap 也用跳表正是因为无锁并发实现比红黑树容易得多。选型逻辑：需要并发/范围操作选跳表，需要严格最坏界选平衡树。

💻 全栈开发专家 ​

跳表 = 多层有序链表 + 每个节点随机决定层高，用"空间换层数"实现 O(logN) 查询：

text
第3层:  head ------------------------> 50 --------------> nil
第2层:  head ------> 20 ------------> 50 ------> 70 ----> nil
第1层:  head --> 10 -> 20 --> 40 --> 50 -> 70 --> 90 --> nil
查找 40：从最高层出发，50 太大下沉 → 20 前进 → 40 命中，只走 3 步

关键机制：

  • 每插入一个节点，以概率 p 抽层高（Redis p=0.25，最高 32 层），层高服从幂次定律——大部分节点 1~2 层，极少数很高；
  • 查询从最高层往右走、走不动就下沉，单层内跳过的都是"肯定不在这区间"的节点，期望 O(logN)；
  • ZSET 里 skiplist 和 dict 双结构并存：skiplist 负责有序范围（ZRANGE），dict 负责 O(1) 按 member 查分值，空间换查询效率。

为什么不用红黑树（面试核心）：1）范围查询 skiplist 沿底层链表顺序走天然高效，红黑树要中序回溯；2）实现简单得多，插入删除只改几个指针，无旋转重平衡；3）并发改造容易（ConcurrentSkipListMap 按 level 分段加 CAS）。

工程联系：JUC 的 ConcurrentSkipListMap（我用来做并发有序缓存/延迟任务索引）、LevelDB/RocksDB 的 memtable 也是跳表——写多、要有序遍历的场景跳表是首选。