高困难

跳表原理（ZSet底层）#

一句话答案#

跳表是多层有序链表，逐层跳跃实现 O(logn) 查找，Redis 选它因为实现简单、范围查询方便、并发友好。

核心要点

ZSet 的双重底层结构（同时维护两个）：

ZSet
├── hashtable（哈希表）：member → score 的映射
│   作用：O(1) 查找某个 member 的 score（ZSCORE 命令）
│
└── skiplist（跳表）：按 score 排序的有序索引
    作用：O(log N) 范围查询、排名查询（ZRANGE、ZRANK 命令）

plaintext

为什么要同时维护两个结构？

只有跳表：ZSCORE 需要 O(log N)，不够快
只有哈希表：无法做有序范围查询（ZRANGE、ZRANGEBYSCORE）
两者结合：以额外内存换取两种查询都 O(1)/O(log N)

编码切换（小数据量优化内存）：

当同时满足以下两个条件时，使用 listpack（紧凑型双向链表，省内存）：
  - 元素数量 <= 128（默认）
  - 每个元素 value 长度 <= 64 字节（默认）

超过任一阈值 → 转换为 skiplist + hashtable

plaintext

面试回答（2分钟版）

Redis 的 ZSet 底层同时维护两个数据结构：一个 hashtable 做 member 到 score 的 O(1) 映射，一个 skiplist 按 score 排序支持 O(logN) 的范围查询和排名查询。跳表本质是多层有序链表，底层是完整的有序链表，上面每一层是下层的稀疏索引，查找时从最高层开始逐层向右向下跳跃，类似二分查找的效果。Redis 选跳表而不选红黑树有两个关键原因：一是跳表实现简单，插入删除只需要调整前后指针加随机层数，红黑树需要复杂的旋转操作；二是跳表对范围查询天然友好，找到起始节点后顺序遍历链表即可，红黑树需要中序遍历。小数据量时 ZSet 用 listpack 编码节省内存，元素数超过 128 或单个值超过 64 字节就自动转为 skiplist+hashtable。层数随机生成，每层概率 1/4，期望层数约 1.33 层。

追问与易错

追问方向：

“ZSet 什么时候用 ziplist？”→ 当元素数量不超过 128（zset-max-listpack-entries）且每个元素 value 长度不超过 64 字节（zset-max-listpack-value）时用紧凑编码；Redis 7.0+ ziplist 已被 listpack 替代
“跳表层数怎么决定？”→ 每个新插入的节点随机生成层数，每层概率为 p（Redis 中 p=1/4），即有 1/4 概率升一层；最大层数限制为 32（ZSKIPLIST_MAXLEVEL），期望层数为 1/(1-p) 约 1.33 层
“为什么概率是 1/4？”→ Redis 作者实测 p=1/4 在时间和空间之间取得最佳平衡；p=1/2 索引更密查询更快但内存多一倍，p=1/4 索引稀疏内存省但查询略慢，实际性能差距很小而内存节省显著

易错点：

❌ 跳表和红黑树性能一样——跳表范围查询更好
❌ ZSet 的 skiplist 就是标准跳表——Redis 做了优化