IT 面试题库

Redis 的 ZSet 为什么用跳表而不用红黑树或 B+ 树?

高级简答题后端架构师算法工程师Java后端工程师Java开发工程师Redis跳表数据结构

题目

请解释跳表的结构与复杂度,以及相比红黑树在 Redis 场景下的优势。

参考答案

内容深度:适中 · 无代码示例 · 来源:网络整理 · 未复核 · 71 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

跳表:多层有序链表,底层包含全部元素,上层是下层的"快速通道"索引;节点以随机概率(Redis 中每层晋升概率 1/4,最高 32 层)决定层高。查找/插入/删除均 O(logN)(从顶层往下逐层缩小范围),范围查询沿底层链表顺序走。

相比红黑树:

  1. 实现简单得多——无旋转变色,插入删除只改前后指针;
  2. 范围查询天然高效——定位起点后沿底层链表线性遍历(ZRANGEBYSCORE 的核心操作);红黑树需要中序遍历回溯,更繁琐;
  3. 并发与内存可控——通过概率参数权衡层数与内存。

相比 B+ 树:B+ 树为磁盘页设计(减少 IO),而 Redis 全内存、无 IO 压力;跳表实现更轻。

补充:ZSet 元素少时(≤128 且元素短)实际用 listpack 存储,跳表只在数据量上来后启用——"小数据走压缩编码"是 Redis 的通用设计。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题