Redis用跳表而非红黑树实现zset，因其支持O(log N)范围查询、ZRANK和ZSCORE，且span字段优化rank计算，代码简洁、内存紧凑、缓存友好；源码见t_zset.c。
Redis 的跳表（SkipList）不是 Java 实现的，而是用 C 语言在 Redis 源码中实现的；Java 面试中问“Redis 跳表的实现原理”，实际是在考察你是否理解 Redis 内部如何用跳表替代平衡树来支持有序集合（zset），以及能否讲清其结构设计与工程取舍。
为什么 Redis 用跳表而不是红黑树
跳表在 Redis 中承担 zset 的底层存储，核心目标是：支持范围查询（ZRANGE）、按 rank 查元素（ZRANK）、按 score 查元素（ZSCORE），同时兼顾插入/删除/查找的平均效率和实现简洁性。
- 红黑树虽理论性能稳定，但实现复杂、内存碎片多、范围遍历需中序递归或栈模拟，不利于 Redis 单线程 + 内存紧凑的设计
- 跳表用多层链表模拟“分层索引”，天然支持 O(log N) 平均查找，且所有操作均可顺序遍历完成，代码更易写、易维护、易调试
- Redis 的跳表还额外维护了每个节点的
span（跨域长度），使得ZRANK可 O(log N) 完成，而红黑树做 rank 查询需每个节点存子树大小并持续维护，开销更大 - 实测在常见数据规模（万级以内）下，跳表的常数因子和缓存友好性优于红黑树
zskiplistNode 和 zskiplist 的关键字段
Redis 跳表由两个核心结构组成：zskiplistNode（单个节点）和 zskiplist（全局控制结构）。理解它们的字段是读懂源码的关键。
-
zskiplistNode包含：score（double 类型，排序依据）、obj（robj*，指向成员对象）、level[]（柔性数组，每层的前向指针 +span值） -
level[i].forward指向第 i 层下一个节点；level[i].span表示从当前节点到forward节点之间跨越了多少个原始层级 0 节点（用于快速算 rank） -
zskiplist包含：header（头节点，不存真实数据）、tail（尾节点指针）、length（当前节点总数）、level（当前最大层数） - 注意：
header的level数组在初始化时就分配了最大可能层数（默认 32），但其他节点的 level 是随机生成的（通过zslRandomLevel()），服从概率分布：P(level = k) = 1/2ᵏ
插入时如何确定层数和更新 span
插入新节点前，Redis 先从 header 出发，逐层查找插入位置，并记录每层的“最后可到达节点”和该路径上的累计 span。这是跳表支持高效 rank 的关键逻辑。
- 调用
zslRandomLevel()生成新节点层数：循环抛硬币（random() & 0xFFFF - 查找过程中，对每一层 i，记录
update[i]（该层插入点前一个节点）和rank[i]（从 header 到update[i]的 span 累计值） - 插入后，对每一层 i（≤ 新节点层数），更新
update[i]->level[i].forward指向新节点，并重算update[i]->level[i].span和新节点level[i].span -
span更新公式：新节点level[i].span = rank[0] - rank[i] + 1；update[i]->level[i].span则增加1 - level[i].span
面试时容易被追问的细节
如果你只背了“跳表是多层链表”，大概率会被追问卡住。下面这些点，是面试官判断你是否真读过源码或深入思考过的信号：
- Redis 跳表的
score相同时，怎么比较？答：先比score，相等时调用dictSdsKeyCompare()比成员字符串的字典序（所以ZADD zset 1 a 1 b中 a 在 b 前） - 为什么不用 std::map 或 TreeMap？答：Redis 是 C 写的，不依赖 STL；且跳表内存布局更紧凑（无虚函数表、无额外指针），更适合 Redis 的内存管理模型
- 跳表的最坏时间复杂度是多少？答：O(N)，当随机层数全为 1 时退化为链表，但概率极低（2⁻³²）；Redis 不做 worst-case 保证，只保平均性能
- 如果我要在 Java 里模拟 Redis 跳表的 rank 计算，必须自己维护 span 字段，不能只靠遍历计数——这点常被忽略
真正难的不是画出跳表结构图，而是说清 span 怎么参与 rank、update、delete 全流程，以及为什么 Redis 宁可多存一个整数也要换掉更“理论优美”的树结构。源码就在 src/t_zset.c 里，zslInsert 函数不到 150 行，值得逐行盯一遍。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
