Redis Zset 的实现原理是什么？

回答重点

Redis 中的 ZSet（有序集合，Sorted Set） 是一种由 跳表（Skip List） 和 哈希表（Hash Table） 组成的数据结构。ZSet 结合了集合（Set）的特性和排序功能，能够存储具有唯一性的成员，并根据成员的分数（score）进行排序。

ZSet 的实现由两个核心数据结构组成：

1. 跳表（Skip List）：用于存储数据的排序和快速查找。
2. 哈希表（Hash Table）：用于存储成员与其分数的映射，提供快速查找。

当 Zset 元素数量较少时，Redis 会使用压缩列表（Zip List）来节省内存

• 即元素个数 ≤ zset-max-ziplist-entries（默认 128）
• 元素成员名和分值的长度 ≤ zset-max-ziplist-value（默认 64 字节）

如果任何一个条件不满足，Zset 将使用 跳表 + 哈希表 作为底层实现。

扩展知识

跳表的实现原理

• 638. Redis 中跳表的实现原理是什么？

哈希表

Redis 使用哈希表来存储 ZSet 中的成员和分数之间的映射关系。哈希表的键是 ZSet 的成员，值是该成员的分数。哈希表提供了 O(1) 的查找、更新和删除操作。

通过哈希表，Redis 可以快速查找某个成员的分数，避免每次查询时都需要遍历跳表。

• Redis 的 hash 是什么？

ZSet 的插入、删除和查找操作

插入操作（ZADD）：插入操作的时间复杂度为 **O(log N)**，因为在跳表中查找插入位置的时间复杂度是 O(log N)，哈希表的更新操作是 O(1)。

1. 使用哈希表存储成员和分数的映射关系，分数作为哈希表中的值。
2. 同时，将成员和分数插入跳表，跳表会根据分数排序。
3. 如果是更新操作，Redis 会在哈希表中更新成员的分数，然后在跳表中更新该成员的位置。

删除操作（ZREM）：删除操作的时间复杂度为 **O(log N)**，其中 N 是跳表中元素的数量。

1. 使用哈希表删除成员的映射。
2. 同时在跳表中删除该成员。

查找操作（ZSCORE）：

1. 在哈希表中查找成员的分数，时间复杂度为 **O(1)**。

范围查询操作（ZRANGE、ZREVRANGE、ZRANGEBYSCORE）：

1. 在跳表中根据分数区间查找成员，查找时间复杂度为 **O(log N + M)**，其中 M 是返回的成员数量。
2. 哈希表用于快速查找成员的分数。

时间复杂度

ZSet 操作的核心时间复杂度是 **O(log N)**，因为大多数操作（如插入、删除、查找等）都需要通过跳表查找元素的位置。

对于范围查询操作，由于返回的数据量可能很大，时间复杂度为 **O(log N + M)**，其中 M 是返回的元素数量。

通过成员分数查询（如 ZSCORE）的时间复杂度为 **O(1)**，因为 Redis 使用哈希表来存储成员与分数的映射。

ZSet 的应用场景

Redis 的 ZSet 常用于实现需要排序和快速查询的场景，比如：

• 排行榜：例如游戏中的积分排行榜。
• 延迟队列：基于 ZSet 按时间戳排序，可以实现任务调度和延迟任务。
• 社交网络中的关注/粉丝数排序：如微博、Twitter 中的用户粉丝数排名。
• 662. 如何使用 Redis 快速实现排行榜？