Redis中的Zset是怎么实现的？

## **1. ZSet 的基本概念** - ZSet（Sorted Set）是 Redis 提供的一种**有序字典结构**，每个元素包括： - **成员（Member）**：存储的实际值。 - **分值（Score）**：用于排序的 `double` 类型数值。 - **典型应用**： - 排行榜（游戏积分、网站流行度排行） - 延迟队列（任务调度） - 优先级队列（任务调度优先级） ## **2. ZSet 的数据结构** Redis 采用两种方式存储 ZSet： 1. **ListPack（紧凑列表，原 ZipList）** 2. **SkipList（跳表）+ Dict（哈希表）** ### **2.1 ListPack（紧凑列表）** - **适用于小型集合**（元素少、值短）。 - **连续内存存储**，减少内存碎片，提高访问效率。 - **Redis 7.0** 彻底移除了 ZipList，全部换成 ListPack。 #### **存储规则** - **元素数量 < `zset-max-listpack-entries`（默认 128）** - **元素长度 < `zset-max-listpack-value`（默认 64 字节）** **优缺点** | **优点** | **缺点** | |----------|----------| | 占用内存小 | 不能高效排序和查找 | | 适合小数据量 | 插入/删除时性能下降 | ### **2.2 SkipList（跳表）+ Dict（哈希表）** 当 ZSet 数据量超过阈值，Redis 自动切换到 **跳表 + 字典** 结构。 #### **跳表（SkipList）** - **按分值（Score）排序**，支持快速范围查询。 - **多级索引** 结构，加速查找，`O(log n)` 复杂度。 - **增删改查** 均为 `O(log n)`。 #### **字典（Dict）** - **成员（Member） → 分值（Score）映射**，用于 O(1) 查找。 - **键值对存储**，键是 `Member`，值是 `Score`。 #### **跳表 + 字典 配合** - **跳表** 维护有序性，提供按 **Score 查询**（如 `zrange`）。 - **字典** 允许 **O(1) 访问特定元素**（如 `zscore`）。 **优缺点** | **优点** | **缺点** | |----------|----------| | 高效范围查询 (`O(log n)`) | 占用更多内存 | | 数据结构稳定 | 插入/删除比 ListPack 慢 | ## **3. ListPack 与 SkipList 之间的切换** ### **3.1 什么时候使用 ListPack** - **元素数量** < `zset-max-listpack-entries`（默认 128） - **每个元素长度** < `zset-max-listpack-value`（默认 64 字节） ### **3.2 什么时候切换到 SkipList** - **元素超出 128** - **元素长度超出 64 字节** - **执行复杂操作**（如 `zrange` 大量查询） ### **3.3 切换过程** 1. 遍历 ListPack 所有元素 2. 依次插入 SkipList 3. 同时更新字典结构 ## **4. 跳表（SkipList）结构** ### **4.1 什么是跳表** 跳表是一个**带索引的有序链表**，用于加速查找。 **普通链表查找**：O(n) **跳表查找**：O(log n)（因为有索引） ### **4.2 跳表索引示例** 普通链表：  跳表（多级索引）：  在上面这个结构中，插入23的过程是 先使用第2层链接head->7->19->26，发现26比23大，就回到19 再用第1层连接19->22->26，发现比23大，那么就插入到26之前，22之后 ### **4.3 跳表的操作** | **操作** | **时间复杂度** | |----------|--------------| | 插入 | O(log n) | | 删除 | O(log n) | | 查找 | O(log n) | ## **5. ZSet 典型应用场景** | **应用** | **实现方式** | |----------|------------| | **排行榜** | `zadd` 添加分值，`zrange` 按分数排序 | | **延迟队列** | `zadd` 任务时间戳，`zrangebyscore` 查找可执行任务 | | **优先级队列** | `zadd` 任务优先级，`zpopmin` 取最高优先级任务 | ## **6. 结论** 1. **小规模数据**：用 **ListPack**，节省内存。 2. **大规模数据**：用 **SkipList + Dict**，提升查询效率。 3. **跳表** 适用于范围查询，**字典** 适用于 O(1) 访问。 4. Redis 7.0 **彻底移除 ZipList**，统一改用 **ListPack**。 这样实现了 **性能与存储效率的平衡**，适用于排行榜、任务队列、优先级调度等场景。