02.5 - ZSet 与 SkipList
定位: Redis 的有序集合——在集合基础上附加"分值"排序，底层由 skip list + dict 双重结构实现
面试高频度: ⭐⭐⭐⭐⭐
考查方式: 跳表原理与查询过程、为什么用跳表不用平衡树、ZRANGE/ZREVRANK 复杂度
一、这是什么？为什么需要它？
是什么
ZSet（Sorted Set）在 Set 的"唯一性"基础上增加了 score（分值），所有元素按 score 排序。读场景时可以作为排行榜、延迟队列、范围查询使用。
为什么需要 ZSet？
核心能力
ZADD leaderboard 100 "player1" ← 添加/更新
ZINCRBY leaderboard 10 "player1" ← 增加分数
ZRANK leaderboard "player1" ← 排名
ZREVRANGE leaderboard 0 9 ← Top 10
ZRANGEBYSCORE leaderboard 80 100 ← 分数区间查询
ZREMRANGEBYRANK leaderboard 0 99 ← 移除底部的 100 人二、原理拆解
2.1 双重数据结构
2.2 跳表（SkipList）原理
为什么用跳表不用平衡树（红黑树）？
| 维度 | 跳表（SkipList） | 平衡树（红黑树） |
|------|----------------|----------------|
| 实现复杂度 | ~50 行 C 代码 | ~500 行 C 代码 |
| 范围查询 | 同层链表遍历，天然支持 | 需要中序遍历，实现复杂 |
| 插入/删除 | 不改结构，只改指针 | 需要旋转/染色 |
| 平均复杂度 | O(logN) | O(logN) |
| 内存占用 | 平均 2 个指针/元素 | 2 个指针/元素（引用） |
| 并发友好性 | 容易加锁分层 | 难 |
核心原因：实现简单、范围查询天然支持、不需要重平衡。
2.3 跳表层高与随机化
Redis 跳表层高分配算法：
每次插入新节点时，通过随机函数决定其层高：
int zslRandomLevel(void) {
int level = 1;
// 每次有 25% 概率增加一层
while ((random() & 0xFFFF) < 0.25 * 0xFFFF)
level += 1;
// 限制最大层高 ZSKIPLIST_MAXLEVEL = 32
return (level < 32) ? level : 32;
}
实际分布：
层高 1: 75% ← 大部分元素在底层
层高 2: 18.75%
层高 3: 4.69%
层高 4: 1.17%
...
层高 32: 几乎为零
这意味着：
100 万个元素的 ZSet
→ 大部分在底层
→ 少量高层节点做"索引"
→ 平均每个节点 ~2 个指针
ZSKIPLIST_P = 0.25 的经验值：
√ 层高增长慢 → 节省指针内存
√ 搜索性能仍为 O(logN)2.4 编码切换
三、图解全景
四、实战验证
4.1 基础操作
redis-cli
# 游戏排行榜
127.0.0.1:6379> ZADD leaderboard 8000 "player1" 9500 "player2" 7200 "player3"
(integer) 3
# 获取 Top 3（按分数从高到低）
127.0.0.1:6379> ZREVRANGE leaderboard 0 2 WITHSCORES
1) "player2"
2) "9500"
3) "player1"
4) "8000"
5) "player3"
6) "7200"
# 获取某个玩家的排名
127.0.0.1:6379> ZRANK leaderboard "player1"
(integer) 1 # 0-based，第 2 名4.2 编码验证
redis-cli
# 1. 小 ZSet → ziplist
127.0.0.1:6379> ZADD smallzset 1 a 2 b 3 c
(integer) 3
127.0.0.1:6379> OBJECT ENCODING smallzset
"listpack" # Redis 7.x 或者 "ziplist"（6.x）
# 2. 超过阈值 → skiplist
127.0.0.1:6379> EVAL "for i=1,200 do redis.call('ZADD',KEYS[1],i,i) end" 1 bigzset
(nil)
127.0.0.1:6379> ZCARD bigzset
(integer) 200
127.0.0.1:6379> OBJECT ENCODING bigzset
"skiplist"4.3 跳表搜索性能验证
# 创建大数据集（模拟千万级排行榜）
for i in $(seq 1 100000); do
redis-cli ZADD bigrank $i "player:$i" > /dev/null 2>&1
done
# 验证范围查询性能
time redis-cli ZREVRANGE bigrank 0 99 WITHSCORES > /dev/null
# ~几毫秒（O(logN + 100)）
time redis-cli ZRANK bigrank "player:99999"
# (integer) 99998
# ~微秒级（O(logN)）
# 验证 ZSCORE 的 O(1) 性能
time redis-cli ZSCORE bigrank "player:99999"
# "99999"
# ~微秒级4.4 延迟队列模拟
# 用 ZSet 实现定时任务调度
# 添加定时任务（score = 执行时间戳）
redis-cli ZADD delayed:tasks \
$(date -d "+1 minute" +%s) "send_email:user1" \
$(date -d "+5 minute" +%s) "process_order:order123" \
$(date -d "+1 hour" +%s) "cleanup_temp_files"
# 轮询到期任务
while true; do
# 取出所有 score <= 当前时间的任务
tasks=$(redis-cli ZRANGEBYSCORE delayed:tasks -inf $(date +%s) WITHSCORES)
if [ -n "$tasks" ]; then
echo "到期任务: $tasks"
# 移除已取出任务
redis-cli ZREMRANGEBYSCORE delayed:tasks -inf $(date +%s)
fi
sleep 1
done五、面试视角
| 追问 | 答案要点 |
|------|---------|
| 为什么 ZSet 用跳表不用红黑树？ | 实现简单（50行 vs 500行）；范围查询天然支持（同层链表遍历）；树旋转代价 |
| 跳表的层高怎么确定？ | 随机确定，每次 25% 概率升一层，最大 32 层；平均每个节点 ~2 个指针 |
| ZRANK 和 ZSCORE 的复杂度？ | ZRANK O(logN)（跳表）；ZSCORE O(1)（dict） |
| ZRANGE 的复杂度？ | O(logN + M) — logN 找到起始位置 + M 遍历 M 个元素 |
| 为什么 ZSet 需要 dict+跳表双重结构？ | dict 做 O(1) 查分值，跳表做范围查询；各自优缺点互补 |
| ZINCRBY 的原子性？ | 原子操作：dict 更新分值 + 跳表中调整位置，不存在中间状态 |
| ZSet 的 ziplist 转换为什么不可逆？ | 同 Hash 的 ziplist→hashtable，假设数据量增长后不会再压缩回去 |
📚 相关链接
**Set 底层** — ZSet 是 Set 的排序版本
**Hash 底层** — 共享的 ziplist/listpack 编码策略
**ZSet 用于滑动窗口限流**
← 返回 **核心数据结构索引**