IT 面试题库

ZSet 的底层编码是什么,为什么用跳表而不是平衡树?

高级简答题Java后端工程师后端开发工程师RedisZSet跳表skiplist底层编码

题目

有序集合既要按 score 排序又要按成员查找,Redis 为何选择「跳表 + 哈希表(或 listpack)」的组合,而不是红黑树?

参考答案

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

编码组成:元素少且小时用 listpack(紧凑);元素多时升级为「跳表 skiplist + 字典」双结构——字典以 member 查 score(O(1)),跳表维护有序以支持范围遍历。

为何不用平衡树:跳表的 range 操作(ZRANGEBYSCORE、排名)只需顺着前向指针走,实现简单、范围扫描效率高;红黑树做区间遍历需中序且缓存局部性更差。

范围与排名优势:跳表每层是链表,按 score 区间取 TopN、计算排名(ZRANK)非常自然,平均 O(log n);且插入/删除不需像平衡树那样频繁旋转,代码更直观。

代价:跳表平均空间略高于平衡树(多级指针),但工程收益(范围查询 + 实现简单)明显占优,因此成为 ZSet 主选。

练这道题

同分类 · 高频题

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

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