跳表原理（ZSet底层）#

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

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

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

• 只有跳表：跳表按 score 排序，按 member 查 score 只能遍历，ZSCORE 退化为 O(N)
• 只有哈希表：无法做有序范围查询（ZRANGE、ZRANGEBYSCORE）
• 两者结合：以额外内存换取两种查询都 O(1)/O(log N)

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

当同时满足以下两个条件时，使用 listpack（一块连续内存的紧凑列表，可双向遍历，省内存）：
  - 元素数量 <= 128（默认）
  - 每个元素 value 长度 <= 64 字节（默认）

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

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？”→ 这是 Pugh 跳表论文推荐的取值，在时间和空间之间折中；每节点平均指针数为 1/(1-p)：p=1/2 约 2 个、p=1/4 约 1.33 个，即 p=1/2 指针开销约为 p=1/4 的 1.5 倍，查询略快；p=1/4 查询常数略大但省内存

易错点：

• ❌ 跳表和红黑树性能一样——跳表范围查询更好
• ❌ ZSet 的 skiplist 就是标准跳表——Redis 做了改造：允许 score 重复（score 相同按 member 字典序排）、第 0 层有 backward 指针支持倒序遍历（ZREVRANGE）、每层 forward 指针带 span 跨度用于 O(log N) 算排名（ZRANK）