ZSet 要同时满足「按 score 有序」「范围查询」「按 member 秒查」三件事，Redis 给出的答案是跳表加哈希表。跳表用概率平衡替代严格平衡，换来实现简单、范围遍历顺滑的工程收益，这是理解 ZSet 底层设计的关键入口。

为什么不用红黑树

同样是有序结构、同样的 O(log N) 复杂度，红黑树输在了三个工程细节上。第一是范围查询的代价：跳表查到区间起点后，沿第 0 层链表顺序走即可，指针连续、缓存友好；红黑树要做中序遍历，不断在父子节点间跳跃，常数开销明显更大，而 ZRANGE 恰恰是 ZSet 最高频的操作。第二是实现复杂度：红黑树的旋转和染色逻辑分支繁多，跳表的插入只是「找位置 + 随机层高 + 改几个前向指针」，代码量和调试难度都不在一个量级，作者 antirez 本人也直言跳表足够简单，以至于社区只用很少改动就给它加上了 O(log N) 的 ZRANK。第三是内存与并发：跳表每个节点的指针开销可通过晋升概率调节（Redis 取 p=0.25，平均每节点约 1.33 层指针），且修改只涉及局部几个指针，天然适合做无锁或细粒度锁的并发变体——Redis 主流程虽是单线程，但这个特性让跳表在其他系统里同样受欢迎。红黑树的旋转则可能波及从插入点到根的一整条路径。

zskiplist 的结构

Redis 的跳表定义在 server.h 中，核心是两个结构：

# 逻辑视图（非真实代码，仅示意字段）
zskiplist:     header, tail, length, level      # 头节点、尾节点、节点数、当前最大层数
zskiplistNode: ele, score, backward, level[]    # 成员、分值、后退指针、层数组
# level[i] = { forward, span }                  # 每层一个前向指针 + 跨度

几个设计要点：层数上限为 32，插入时以 1/4 的概率逐层晋升，期望层高 O(log N)；backward 后退指针让从尾向前的 ZREVRANGE 也能高效进行；每层的 span 记录两个节点在第 0 层之间隔着多少个元素，沿途累加 span 就能得到排名，这是 ZRANK 做到 O(log N) 的全部秘密。score 允许重复，相同时按 member 字典序决胜，保证了全序关系。另外别忘了小集合的入口：元素少且短时 ZSet 用 listpack 存储，超过 zset-max-listpack-entries（默认 128）或 zset-max-listpack-value（默认 64 字节）才切换到跳表加哈希表。

插入与范围查询流程

插入一个新成员的路径分四步：

  1. 随机层高：以 p=0.25 的概率反复掷硬币，得到 1 到 32 之间的层数。
  2. 自上而下找位置：从头节点的当前最高层出发，每层尽量向右走（比较 score，再比较 member），走不动就下移一层；沿途用 update[] 数组记录每层最后停留的节点，用 rank[] 记录排名，供稍后更新 span。
  3. 拼接指针：新节点在每一层接住 update[i] 的 forward，update[i] 改指新节点，同时用记录的跨度校准各层 span。
  4. 收尾：接上后退指针，若新节点层高超过当前最大层数则提升整个跳表的 level。

范围查询（ZRANGEBYSCORE）则是先复用同样的下沉逻辑找到第一个 score ≥ min 的节点，耗时 O(log N)，然后沿第 0 层逐个输出直到 score > max，总复杂度 O(log N + M)，M 为返回个数。删除与插入对称，同样靠 update[] 逐层摘链。

与其他结构的对比

结构 单点查询 范围查询 实现复杂度 指针开销
跳表 O(log N) O(log N + M)，顺序遍历 低 可调（p=0.25）
红黑树 O(log N) 需中序遍历，常数大 高（旋转+染色） 固定两指针
B+ 树 O(log N) 叶子链表遍历，优秀 高（分裂合并） 为磁盘页设计

B+ 树范围能力同样出色，但它是为「减少磁盘 IO」而生的结构；Redis 是纯内存系统，没有页的概念，用 B+ 树属于杀鸡用牛刀。

面试视角

ZSet 为什么用跳表不用红黑树？ 三点：范围查询只需沿底层链表顺序走，红黑树要中序遍历；实现和调试简单得多，没有旋转染色；晋升概率可调，内存开销与并发改造都更友好。

跳表如何支持 O(log N) 的排名查询？ 每个前向指针带一个 span，记录两节点在底层隔几个元素。查询时把沿途经过的 span 累加，到达目标节点时累加值就是排名。

score 相同怎么办？ 按 member 的字典序排序，保证集合内全序，插入位置唯一确定。

跳表在 ZSet 里是唯一结构吗？ 不是。小集合先用 listpack；转跳表后也是「跳表 + dict」双结构，dict 负责按 member 的 O(1) 查询，跳表负责顺序与范围。

小结

  • 跳表用概率平衡换掉严格平衡，赢得简单、范围友好、内存可调。
  • zskiplist 的层数组、后退指针和 span 三个字段，分别撑起查找、逆序和排名。
  • 插入 = 随机层高 + 逐层定位 + 局部接链；范围查询 = 定位起点 + 底层顺扫。
  • 跳表与 dict 的分工是「顺序归跳表、定位归哈希」，这套双视图思路在工程里屡试不爽。