Redis中ZSet的底层看过吗？

Redis 的 ZSet（有序集合）底层结构我看过源码. ## 1. ZSet 的核心作用 ZSet 是一个 **key → score** 的映射集合，按 score 有序，可以通过 score 或排名（rank）获取元素，常用于排行榜、延时队列等。 ## 2. 底层数据结构 Redis 为了在不同数据量、操作模式下都高效，**ZSet 底层是两种结构的组合**： 1. **ziplist / listpack**（压缩列表 / 紧凑存储） * 当集合元素少（`zset_max_ziplist_entries`，默认 128）且元素成员字符串短（`zset_max_ziplist_value`，默认 64字节）时使用。 * 优点：连续内存存储，空间紧凑，内存占用小。 * 缺点：查找、插入需要线性遍历，性能 O(N)。 * Redis 7 开始 ziplist 全部换成 listpack。 2. **skiplist + dict**（跳表 + 哈希表） * 当元素多或成员太长时使用。 * **dict**：member → score 映射，O(1) 查找元素分数。 * **skiplist**：按 score 有序存储，支持范围查找、排名操作，O(logN)。 * 两者组合：dict 用于快速按 member 找 score，skiplist 用于按 score 有序访问。 ## 3. skiplist 的实现细节 源码在 `t_zset.c` 和 `server.h` 里定义。 ### 3.1 结构定义 ```c typedef struct zskiplistNode { sds ele; // 成员字符串 double score; // 分数 struct zskiplistNode *backward; // 后退指针 struct zskiplistLevel { struct zskiplistNode *forward; // 前向指针 unsigned long span; // 跨越的节点数 } level[]; // 多层指针（高度随机生成） } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; unsigned long length; int level; // 当前最大层数 } zskiplist; ``` ### 3.2 跳表特点 * **多层索引**：最高 32 层（`ZSKIPLIST_MAXLEVEL`）。 * **随机层数**：`zslRandomLevel()` 按概率生成高度（几何分布，p=0.25）。 * **span** 作用：快速计算 rank（第几名）。 ### 3.3 插入流程 1. 在每层找到插入位置（update\[] 数组记录前驱）。 2. 随机层高。 3. 更新 forward 指针和 span。 4. 插入节点，更新 backward。 时间复杂度：O(logN)。 ### 3.4 查询 & 范围操作 * **按 score 查范围**：从顶层向下走，利用 score 过滤，性能 O(logN + M)（M=返回元素数）。 * **按 rank 查**：利用 span 快速跳过节点。 ## 4. dict 的作用 跳表按 score 排序，但按 member 查分数效率低，因此 Redis 额外用一个字典： ```c dict<member, score> ``` 这样： * 按 member 查 → dict O(1)。 * 按 score 查 → skiplist O(logN)。 ## 5. 内存结构选择逻辑 源码 `zsetAdd()` 中： ```c if (encoding == OBJ_ENCODING_LISTPACK) { if (too_big) convert_to_skiplist(); } ``` 规则： * 元素个数 > zset\_max\_ziplist\_entries * 或 成员字符串长度 > zset\_max\_ziplist\_value 就会从 listpack 升级为 skiplist+dict。 ## 6. 操作复杂度 | 操作 | ziplist/listpack | skiplist+dict | | ---------------- | ---------------- | ------------- | | 按 member 查 score | O(N) | O(1) | | 按 score 查 member | O(N) | O(logN) | | 插入/删除 | O(N) | O(logN) | | 范围查找（score） | O(N) | O(logN + M) | | 按 rank 获取 | O(N) | O(logN) | ## 7. 源码位置（Redis 7） * `src/t_zset.c`：ZSet 核心 API。 * `src/server.h`：结构体定义。 * `src/ziplist.c` / `src/listpack.c`：压缩存储实现。 * `src/skiplist.c`（逻辑嵌在 t\_zset.c 里）。 ## 8. 应用层面建议 * **少量元素** → listpack 更省内存，适合小排行榜。 * **大量元素 + 频繁范围查找** → skiplist+dict。 * 排行榜更新频繁、排名查询多 → ZSet 非常适合（跳表天然支持排名）。 * 如果只需要按 member 查分数且无序，不用 ZSet，直接 hash 更快。