一、面试题简述

Redis 里的Zset你用过吗？它既能按照 score 排序，又能按照 member 快速查找，这是怎么做到的？

底层到底用了什么数据结构？为什么这样设计？

二、面试官想听的

这道题本质不是问Zset 用了什么结构，而是在考察：

1、你是否能从需求出发推导结构设计

2、你是否理解时间复杂度与操作路径的权衡

3、你能不能讲清楚为什么不用别的结构

面试官真正想听的是你能不能从工程约束推导出 Hash + SkipList 是一种必然，而不是偶然。

三、面试回答举例

Zset 的核心需求其实很矛盾：

第一，它要按 score 有序；

第二，它要支持根据 member 快速查找和更新。

这两个需求如果拆开来看，其实分别对应两类完全不同的数据结构：

• 按 score 排序 → 需要有序结构
• 按 member 精确查找 → 需要哈希结构

单一结构很难同时在两个维度都做到最优。

所以 Redis 的设计思路不是找一个万能结构，而是采用结构组合。

在元素数量较多时，Zset 的底层是一个 Hash 表 + 一个 SkipList

其中，Hash 表的作用是：

• key：member
• value：score
• 时间复杂度：O(1)

它负责解决：

• 判断某个 member 是否存在
• 获取或更新某个 member 的 score

其中，SkipList 的作用是：

• 按 score 有序组织数据
• 每个节点存储 score + member
• 插入 / 删除 / 查找期望复杂度 O(logN)

它负责解决：

• 按 score 排序遍历
• 按 score 范围查询
• 获取排名

这种设计的本质是让定位元素和维护顺序分别走最优路径。

（1）查 member → 走 Hash

（2）排序、范围查询 → 走 SkipList

两者各司其职，避免一个结构承担双重职责而退化。

另外，当元素数量较少，或者 member / score 较短时，Redis 会使用 ziplist 这种紧凑结构。

这是典型的：

（1）小数据优先考虑内存密度

（2）大数据优先考虑时间复杂度

当元素超过阈值（数量或元素长度）后，会自动转换为 Hash + SkipList 结构。

这是一个非常典型的工程分层设计。

四、由浅入深分析

1、从需求反推结构

Zset 的需求本质是：

• 动态插入
• 动态更新 score
• 排序
• 排名
• 范围查询
• 快速查找 member

如果只用 Hash：

• 查找 O(1)
• 但排序需要 O(N logN)
• 每次排序代价巨大

如果只用有序结构，比如红黑树或者跳表：

• 排序没问题
• 但按 member 查找只能 O(logN)

在比如排行榜、实时排名系统等的高频场景下，O(logN) 的频繁查找是不划算的。

Redis 选择空间换时间，把查找路径压缩到 O(1)。

2、为什么用 SkipList 而不是红黑树？

理论上红黑树也可以做到 O(logN)。

Redis 选择 SkipList 的原因有三个现实工程因素：

第一，实现简单，可读性高。

第二，范围查询天然支持顺序遍历。

第三，概率平衡结构在 Redis 这种单线程模型下足够稳定。

跳表在工程上的简单 + 可控，比红黑树更适合 C 语言实现。

3、不要迷信单结构万能

很多初学者会本能地想：有没有一个结构可以同时搞定所有问题？

Redis 的设计告诉我们：真正高性能系统的思路不是找到完美结构，而是把需求拆分，用不同结构分别优化。

4、复杂度路径分析

Zset 常见操作：

• ZADD
• ZRANGE
• ZRANK
• ZSCORE

我们可以看高频路径：

• 查找 score → O(1)
• 排名查询 → O(logN)
• 插入 → O(logN)

没有任何一个高频操作退化为 O(N)。

这说明设计目标很明确：保证高频操作路径时间复杂度稳定。

五、面试加分点

1、强调这是结构组合设计，而不是单一结构

2、从需求出发推导复杂度，而不是直接背 Hash + SkipList

3、提到 ziplist / listpack 的升级策略

4、能说明 SkipList 选择背后的工程现实原因

5、提到空间换时间与高频路径优化