核心内容摘要
探索秘境，放飞自我——途虎旅游，点燃你的心动之旅
核心概括Redis 的 Zset 同时具备两个核心特性有序性元素按分值score从小到大排列。
唯一性集合中的成员member是唯一的但分值可以相同分值相同时按成员字典序排列。
为了实现这种高效的、兼具“集合”和“有序”特性的数据结构Redis 采用了两种底层数据结构相结合的方案ziplist压缩列表或 listpack紧凑列表用于元素数量少、元素体积小的场景以节省内存。
skiplist跳跃表 dict哈希表用于通用场景以提供高效的查询和范围操作。
这种根据条件动态切换底层结构的设计体现了 Redis 在性能与内存之间做出的精妙权衡。
两种编码方式在 Redis 内部Zset 有两种编码方式通过配置项 zset-max-ziplist-entries 和 zset-max-ziplist-value 来控制。
ziplist / listpack 编码在 Redis 早期版本使用 ziplist新版本
0逐渐用listpack替代 ziplist。
我们以 listpack 为例讲解。
适用条件同时满足有序集合保存的元素数量小于 zset-max-ziplist-entries 默认 128。
每个成员member的字符串长度小于 zset-max-ziplist-value 默认 64 字节。
内存布局listpack 是一个紧凑的、连续内存块它按 [member1, score1, member2, score2, ...] 的顺序成对存储成员和分值。
按分值排序所有元素在 listpack 内部就是严格按照分值升序排列的。
查找方式由于是紧凑数组查找需要线性遍历。
但因为元素少且内存连续缓存友好效率仍然可以接受。
插入/删除需要移动后续元素时间复杂度 O(N)。
同样因为元素少成本可控。
目的在元素少且小的场景下这种结构避免了额外的指针开销极大地节约了内存。
skiplist 编码当不满足上述任一条件时Zset 会自动转换为 skiplist 编码。
这才是 Zset 的“完全体”和核心实现。
它实际上是一个复合结构包含一个跳跃表skiplist和一个字典dict。
arduinotypedef struct zset { dict *dict; // 哈希字典 zskiplist *zsl; // 跳跃表 } zset;为什么需要两种结构跳跃表zskiplist核心作用在于维护元素的有序性支持高效的范围查询如 ZRANGE, ZRANK和插入/删除操作平均 O(logN)。
字典dict核心作用在于提供O(
时间复杂度的成员查询如 ZSCORE 命令直接根据 member 获取其 score。
如果只用跳跃表查询成员分值需要 O(logN)。
如果只用字典无法进行高效的范围操作。
因此这种“空间换时间”的设计让 Zset 既能快速进行单点查询又能高效进行范围操作是工程上的经典取舍。
核心数据结构剖析
跳跃表Skip List详解跳跃表是一种多层级的有序链表是平衡树的一种概率替代方案实现更简单在并发环境下也更有优势。
结构arduinotypedef struct zskiplist { struct zskiplistNode *header, *tail; // 头尾指针 unsigned long length; // 节点总数 int level; // 当前最大层数 } zskiplist; typedef struct zskiplistNode { sds ele; // 成员SDS字符串 double score; // 分值 struct zskiplistNode *backward; // 后向指针L0层用于逆序 struct zskiplistLevel { struct zskiplistNode *forward; // 该层的前进指针 unsigned long span; // 该层到下一个节点的跨度用于排名 } level[]; // 柔性数组表示节点的层级 } zskiplistNode;关键特性多层链表每个节点随机一个层高
。
level 数组长度即为层高。
有序性节点首先按 score 排序score 相同时按 ele 的字典序排序。
查找路径从最高层header的最高层开始向右遍历找到最后一个 score 小于目标或 score 相等但 ele 小于目标的节点然后下降一层继续。
如此反复直到第0层。
这个过程时间复杂度平均 O(logN)。
跨度spanlevel[i].span 记录了从当前节点到 level[i].forward 节点之间跨越了第0层的多少个节点。
这是 ZRANK 命令获取排名能够 O(logN) 完成的关键。
计算排名时只需将搜索路径上所有符合方向的跨度累加即可。
后向指针backward用于从尾到头遍历支持 ZREVRANGE 等逆序操作。
字典Dict就是一个标准的 Redis 哈希表其作用是键Key存储成员member。
值Value存储该成员对应的分值score一个 double 类型。
这个字典确保了对任意成员的O(
时间复杂度的访问。
操作流程示例假设我们执行 ZADD myzset 10 “alice” 20 “bob” 30 “charlie”。
在 skiplist 编码下内存结构示意图如下sqlzset / \ dict zskiplist (header) | (level
alice - 10 | bob - 20 | charlie- 30 V --------------------- | Span | ... | Span | (高层稀疏指针快速跳跃) --------------------- | | V V --------------------- | score | ele | level | - Node(10, alice) | 10 |alice| 2 | --------------------- | | V (L
V (L
------------------------------------------ | score | ele | level | score | ele | level | - Node(20, bob) | 20 |bob | 3 | 20 |bob | 3 | ------------------------------------------ | | V (L
V (L
------------------------------------------ | score | ele | level | score | ele | level | - Node(30, charlie) | 30 |char | 1 | 30 |char | 1 | ------------------------------------------ | V (L
NULL关键操作如何工作ZSCORE myzset bob直接在 dict 中查找键 bob立即返回其值 20。
O(
。
ZRANGE myzset 1 2从 zskiplist 的 header 出发利用高层指针快速定位到起始节点bob然后沿低层指针遍历输出。
O(logN M)M为返回元素个数。
ZRANK myzset charlie从 zskiplist 的 header 出发搜索 charlie 的路径同时累加沿途的 span 值。
最终得到的累加和就是其排名从0开始。
O(logN)。
ZADD myzset 15 david先在 dict 中检查 david 是否存在保证唯一性。
然后在 zskiplist 中执行标准的跳表插入操作O(logN)找到插入位置。
最后在 dict 中插入 david - 15 的键值对。
整个操作O(logN)。
ZSET ZRANGE 操作序列图下面这个序列图展示了当执行 ZRANGE myzset 1 3 命令时Redis 内部不同组件之间的交互流程
五、
总结与要点双编码策略Zset 是智能的小数据用紧凑的 listpack 省内存大数据用功能强大的“跳表哈希”组合保性能。
核心复合结构skiplist dict 是 Zset 的灵魂。
skiplist 负责排序和范围操作dict 负责快速单点访问。
二者通过共享成员和分值的指针来保证数据一致性没有冗余存储。
跳跃表的角色它不仅是一个有序链表其跨度span属性是实现 O(logN) 复杂度的排名查询的关键。
时间复杂度添加/删除/按分值查询平均O(logN)。
按成员查分值O(
。
范围查询如 ZRANGEO(logN M)。
获取排名ZRANKO(logN)。
选择原因相比于红黑树等严格平衡树跳跃表实现简单区间查询更直观且在并发环境下更容易实现无锁优化。
面试回答它的底层实现其实采用了两种数据结构相结合的‘混合’策略目的是在内存使用和性能之间取得一个平衡。
具体来说它同时使用了跳跃表Skip List字典或哈希表Hash Table这两种结构会共享集合中元素成员和分数分值的数据但通过指针引用所以不会造成双倍的内存开销。
为什么需要两种结构呢这主要是为了应对 Zset 不同的操作场景让它们都能非常高效跳跃表的核心作用是维持元素的有序性。
它的结构像多层链表上层是“快速通道”下层是“精确通道”。
这使得范围型操作以及插入、删除的平均时间复杂度都能在O(log N)级别效率很高。
字典的核心作用是提供‘成员 - 分数’ 的快速映射。
当我们执行像去获取某个成员的分数或者更新一个已有成员这类操作时如果能直接通过成员名key在哈希表里O(
时间复杂度查到它的分数那就太快了。
如果只用跳跃表这个查询就需要 O(log N)。
所以简单来讲可以把 Zset 想象成一个用哈希表做‘索引’用跳跃表做‘排序清单’的组合体。
哈希表保证了点查的极致速度跳跃表保证了范围操作的效率。
不过在 Redis 的后续版本中我记得是
0 之后为了进一步节省内存还有另一种编码方式叫 Ziplist紧凑列表。
当 Zset 同时满足两个条件时
元素数量较少默认 ≤ 128 个
每个成员字符串长度较短默认 ≤ 64 字节Redis 会使用一块连续内存的 ziplist 来存储。
在这个链表里成员和分数是挨个交替存放的它因为少了跳跃表和哈希表的结构开销所以非常节省内存。
一旦不满足上述任一条件它就会自动转换成标准的“跳跃表字典”结构。
这个转换对使用者是无感的。
总结一下我的理解是Zset 的底层会根据数据规模灵活选择对于小型集合使用内存紧凑的 ziplist。
对于通用集合使用‘跳跃表 字典’的双结构同时保证高效的范围操作和单点查询。
这也是一个在工程上非常经典的‘用空间换时间’和‘空间时间平衡’的设计思路。