Redis 的 Zset底层是怎么实现的?

一、面试题简述

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、提到空间换时间与高频路径优化

#八股文##大厂##面经##面试问题记录#
技术必备题库 文章被收录于专栏

带你复盘大厂后端和算法面试,拆解面试官到底想听啥

全部评论
写的太好了。
1 回复 分享
发布于 03-06 20:48 陕西
写的很好
点赞 回复 分享
发布于 03-09 23:35 新疆

相关推荐

简历很重要,很多同学的简历现在都是偏陈列一些概念,有的时候技术能力都够的,项目也做了不少,但是不会提现在简历上。你做了8分,可以包装优化成10分,但是很多同学的项目写的只有五分。下面就给大家一些可以直接参考复用的话术,需要更定制的简历优化等可以私我。一、任务规划 / Agent 核心能力点:多步任务执行能力•设计基于 ReAct / Plan-and-Execute 的 Agent 执行框架,实现复杂任务的自动分解、逐步执行与结果整合•构建支持多轮决策的任务状态机,提升复杂流程下的执行稳定性与可控性⸻点:决策与路由•实现基于模型推理 + 规则约束的任务路由机制,动态选择工具调用路径•设计 tool routing 策略,提升工具选择准确率并减少无效调用⸻二、工具调用(Tool Use)点:工具链设计•封装统一工具调用接口,支持搜索、数据库查询、API 调用等多种能力扩展•构建可插拔工具层,支持快速接入业务系统(如 CRM / 工单系统 / 数据平台)⸻点:调用可靠性•引入参数校验与 schema 约束,显著降低工具调用错误率•设计工具调用重试与 fallback 机制,提升任务成功率⸻三、RAG + Agent 结合(高频加分项)点:检索增强•搭建 RAG 检索模块,结合向量检索与语义重排提升召回质量•将检索结果作为 agent 决策上下文,提高复杂问答准确率⸻点:协同架构(重点包装)•设计 RAG + Agent 协同架构,将“检索-推理-执行”解耦,提升系统可扩展性与稳定性•优化长上下文场景下的信息选择策略,降低噪声对决策的干扰⸻四、记忆(Memory)与上下文管理点:多轮对话能力•实现基于短期记忆 + 长期记忆的上下文管理机制,支持复杂多轮任务•设计 memory 压缩与摘要策略,降低 token 消耗并提升响应效率⸻点:用户状态•构建用户级上下文存储,实现个性化任务执行与历史行为复用⸻五、稳定性 / 防“翻车”(非常关键)点:防幻觉 / 防乱调用•通过输出约束(JSON schema / function schema)减少模型幻觉与格式错误•引入结果校验与二次确认机制,提高关键任务可靠性⸻点:异常处理•设计超时控制、异常捕获与降级策略,保障系统在不稳定情况下仍可运行•构建 fallback 逻辑(规则/模板回复),避免任务完全失败⸻六、评估与数据驱动(很多人不会写,但很加分)点:评估体系•构建 Agent 评估指标体系,包括任务完成率、工具调用准确率、响应延迟与 token 成本•设计离线评测集与自动化评估流程,支持模型与策略迭代⸻点:优化闭环•基于日志分析持续优化 prompt 与工具策略,提升整体执行效果⸻七、性能优化(工程感直接拉满)点:延迟 & 成本•优化 prompt 结构与上下文长度,使平均响应时间下降 X%•引入缓存与结果复用机制,降低 token 成本 X%⸻点:并发与吞吐•设计异步执行与任务队列,提高系统并发处理能力•支持多任务并行执行,提升复杂流程处理效率⸻八、工程化能力(决定你是不是“能进组的人”)点:可观测性•构建日志与 tracing 系统,记录 agent 决策路径与工具调用链路•实现任务级监控,支持问题快速定位与回溯⸻点:系统化落地•将 agent 服务化部署,提供标准 API 接口供业务调用•支持模块化扩展,降低后续功能迭代成本⸻九、业务价值(一定要写,不然像玩具)点:效率提升•将原本依赖人工处理的流程自动化,日均节省 X 小时人工成本•提升任务处理效率 X%,缩短响应时间 X%⸻点:场景覆盖•支持 X 类业务场景(如客服、数据查询、报告生成等),提升系统使用率⸻十、直接可用的“完整项目描述”(可复制)大家可以直接用这个版本👇项目:智能 Agent 平台(LLM + Tool Use + RAG)•设计并实现基于任务分解与工具调用的 Agent 执行框架,支持多步推理与复杂流程自动化•构建 RAG + Agent 协同架构,将检索、决策与执行解耦,提升复杂问题处理能力•封装统一工具接口,接入搜索、数据库与业务 API,实现多场景任务执行•引入参数校验、重试机制与 fallback 策略,显著提升任务执行稳定性•实现多轮对话记忆管理与上下文压缩,优化长任务下的性能与成本•构建评估体系(任务完成率 / 延迟 / token 成本),驱动持续优化成果:•任务完成率提升 XX%•平均响应时间降低 XX%•人工介入率下降 XX%
肖先生~:牛客多推送一点这样的文章给我
AI求职记录
点赞 评论 收藏
分享
评论
10
42
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务