Redis 的 ZSet（有序集合）基础类型是一个非常有趣且高效的数据结构，它通过两种不同的内部编码（encoding）来实现其特性，在内存使用和性能之间做出了精妙的权衡。

我们主要关注以下几个方面：

  1. ZSet 的两种内部编码
  2. 数据结构定义
  3. 核心操作的源码逻辑
  4. 编码转换
  5. 总结

ZSet 的两种内部编码

ZSet 并非由单一数据结构实现，而是根据一定的条件，在两种编码之间动态选择：

  • OBJ_ENCODING_ZIPLIST (压缩列表)： 在元素数量较少、元素值长度较小时使用。它是一种为节省内存而设计的紧凑型线性数据结构。所有元素（member）和分值（score）都按顺序紧密排列在同一个内存块中。
  • OBJ_ENCODING_SKIPLIST (跳跃表)： 当元素数量或大小超过 zset-max-ziplist-entries 和 zset-max-ziplist-value 配置的阈值时，ZSet 会从 ZIPLIST 转换为 SKIPLIST。它结合了跳跃表（skiplist） 和字典（dict） 两种数据结构，以同时保证排序和高效查找。

这种设计哲学是 Redis 的核心：优先使用紧凑、节省内存的编码，当数据量变大导致效率下降时，再转换为更耗内存但性能更高的编码。

数据结构定义

让我们看看在 server.h 中是如何定义这些结构的。

压缩列表 (ZIPLIST) 编码

ZIPLIST 本身是一个通用的字节数组结构，并不是 ZSet 独有的。在 ZSet 的上下文中，它的布局如下：
| member1 | score1 | member2 | score2 | ... |

每个元素（member）和其对应的分值（score）作为两个连续的 entry 存储在 ziplist 中。元素按分值从小到大排序。这种结构非常节省内存，但查询、插入、删除的平均时间复杂度都是 O(N)，因为它需要遍历。

跳跃表 + 字典 (SKIPLIST) 编码

当使用 SKIPLIST 编码时，ZSet 的实际结构是一个包含两个成员的结构体 zset：

1
2
3
4
5
// server.h
typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

a) 跳跃表 (zskiplist / zskiplistNode)

跳跃表负责维护有序的元素序列，支持高效的范围查询（如 ZRANGE）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// server.h
typedef struct zskiplistNode {
    sds ele; // 元素值（SDS 字符串）
    double score; // 分值
    struct zskiplistNode *backward; // 后退指针，用于双向遍历
    struct zskiplistLevel {
        struct zskiplistNode *forward; // 前进指针
        unsigned long span; // 跨度，用于计算排名（ZRANK）
    } level[]; // 柔性数组，表示节点的层级
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length; // 节点数量
    int level; // 当前跳跃表的最大层数
} zskiplist;

跳跃表的每个节点有多个层级（Level），高层级的指针可以跳跃过多个节点，从而加快查找速度。插入一个节点时，会通过随机算法决定它的层高。

为什么需要跳跃表？
它使得按分值排序和范围查询的效率非常高，平均时间复杂度为 O(log N)。

b) 字典 (dict)

字典负责提供 O(1) 时间复杂度的 ZSCORE 操作（根据 member 查找 score）。

1
2
3
4
5
6
7
8
// dict.h
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; // 两个哈希表，用于渐进式 rehash
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    int iterators; /* number of iterators currently running */
} dict;

在 ZSet 的字典中：

  • Key: 是元素值（member，即 SDS 字符串）。
  • Value: 是分值（score，被存储为一个 double 类型的值）。但注意，字典的值并不是直接存 double，而是存储了一个指向该 double 的指针。这个 double 值实际上和跳跃表节点 zskiplistNode->score 是同一个内存地址。

为什么需要字典？
如果没有字典，仅凭跳跃表，根据 member 查找 score 需要 O(N) 的时间（遍历）。字典的引入用空间换时间，将这个操作优化到了 O(1)。

协同工作：
zset 结构中的 dict 和 zsl 共享了元素的成员和分值。即，dict 的 key 和 zskiplistNode 的 ele 指向同一个 SDS 字符串对象；dict 的 value（指向 double 的指针）和 zskiplistNode 的 score 是同一个地址。这避免了多余的内存分配，保证了数据一致性。

核心操作源码逻辑

我们以 ZADD, ZRANGE, ZSCORE 为例，看看它们在不同编码下的实现。

ZADD

函数调用路径： zaddCommand -> zaddGenericCommand -> …

  1. 检查编码并可能触发转换：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    // t_zset.c
    zobj = lookupKeyWrite(c->db, key);
    if (zobj == NULL) {
        // ... 创建新的 ZSet 对象，默认尝试使用 ZIPLIST 编码
        if (server.zset_max_ziplist_entries == 0 ||
            server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
        {
            zobj = createZsetObject(); // 创建 SKIPLIST 编码的 zset
        } else {
            zobj = createZsetZiplistObject(); // 创建 ZIPLIST 编码的 zset
        }
        dbAdd(c->db,key,zobj);
    }
    // 如果现有对象是 ZIPLIST，但插入新元素后可能超出阈值，则转换为 SKIPLIST
    if (zobj->encoding == OBJ_ENCODING_ZIPLIST) {
        if (zzlLength(zobj->ptr) + 1 > server.zset_max_ziplist_entries ||
            sdslen(ele) > server.zset_max_ziplist_value)
        {
            zsetConvert(zobj, OBJ_ENCODING_SKIPLIST); // 编码转换
        }
    }

  2. 插入逻辑：

    • ZIPLIST 编码 (zzlInsert):

      1. 遍历 ziplist，每次前进两个 entry（member 和 score）。
      2. 将当前遍历到的 score 与要插入的 score 比较，找到正确的插入位置以保持有序。
      3. 调用 ziplistInsert 两次，先将 member 插入，紧接着再插入 score。
      4. 时间复杂度为 O(N)。

    • SKIPLIST 编码 (zslInsert + dictAdd):

      1. 先尝试在 dict 中查找 member：如果存在且策略是 XX（更新现有），则更新分值；如果不存在且策略是 NX（只添加新），则拒绝。
      2. 插入跳跃表 (zslInsert)：从跳跃表的最高层开始，从左向右遍历，找到每一层需要插入的位置，并记录下路径。然后随机生成新节点的层高，修改相关指针完成插入。平均时间复杂度 O(log N)。
      3. 插入字典 (dictAdd)：以 member 为 key，以新节点（或现有节点）的 score 成员的地址作为 value（&node->score）进行存储。时间复杂度接近 O(1)。
      4. 如果 member 已存在，则需要先删除跳跃表中的旧节点，再插入新节点，并更新字典中的 value 指针指向新的 score。

ZRANGE

函数调用路径： zrangeCommand -> genericZrangebyscoreCommand -> …

  1. ZIPLIST 编码:

    • 因为 ziplist 本身已经是有序的，所以直接从头（或从尾，如果是逆序）开始遍历。
    • 使用 ziplistIndex 找到起始位置，然后依次获取每个 member-score 对。
    • 返回给客户端。时间复杂度 O(N)。

  2. SKIPLIST 编码:

    • 通过跳跃表进行范围查询是其强项。
    • 首先使用 zslFirstInRange 在跳跃表中找到分值范围内的第一个节点（O(log N)）。
    • 然后从这个节点开始，通过 level[0] 的 forward 指针（最底层链表）依次遍历，直到超出范围为止。
    • 遍历过程中收集元素。整个范围查询的时间复杂度是 O(log N + M)，其中 M 是返回的元素个数。

ZSCORE

函数调用路径： zscoreCommand -> …

  1. ZIPLIST 编码:

    • 遍历 ziplist，每次比较当前 member 是否与目标 member 相等。
    • 如果找到，下一个 entry 就是其 score。
    • 时间复杂度 O(N)。

  2. SKIPLIST 编码:

    • 直接使用字典：dictFind(zs->dict, ele)。
    • 这是一个哈希查找操作，时间复杂度 O(1)。
    • 找到后，字典的 value 就是一个指向 double 的指针，直接返回该指针指向的值即可。

编码转换

转换发生在 zsetConvert 函数中（t_zset.c）。

  • 转换方向：通常是从 ZIPLIST 转换为 SKIPLIST。反向转换仅在调试命令等特殊情况下发生。
  • 过程：
    1. 创建一个新的 zset 结构（包含一个空的 skiplist 和一个空的 dict）。
    2. 遍历原 ziplist 中的所有 (member, score) 对。
    3. 对每一对，调用 zslInsert 插入到新的 skiplist 中。
    4. 同时，调用 dictAdd 将 (member, &(刚创建的node->score)) 加入到新的 dict 中。
    5. 将 Redis 对象的 encoding 设置为 OBJ_ENCODING_SKIPLIST。
    6. 将 Redis 对象的 ptr 指针指向新创建的 zset 结构。
    7. 释放旧的 ziplist。

这是一个阻塞操作，在转换期间，其他命令无法处理这个 key，但对于大型 zset，这个转换开销是值得的。

总结

特性方面 ZIPLIST 编码 SKIPLIST (ZSET) 编码
内存使用 极低，无额外指针开销 较高，需要存储多层级指针、字典哈希表开销
ZADD 性能 O(N) O(log N) (平均)
ZRANGE 性能 O(N) O(log N + M) (优秀)
ZSCORE 性能 O(N) O(1) (卓越)
适用场景 元素数量少、元素体积小 元素数量大、或需要高频单键查询

Redis ZSet 的设计精髓在于：

  1. 双重编码：根据数据规模和配置智能选择最合适的底层实现，在内存和CPU之间取得最佳平衡。
  2. 混合数据结构：对于 SKIPLIST 编码，巧妙地结合了跳跃表和字典的优势：
    • 跳跃表优雅地解决了有序集合的排序和范围查询问题。
    • 字典弥补了跳跃表在单点查询上的性能短板。
  3. 数据共享：跳跃表节点和字典条目共享了 member 和 score 的内存，避免了数据冗余和不一致。
  4. 渐进式Rehash：底层的字典结构支持渐进式 rehash，在扩容时不会阻塞服务。

正是通过这些精心的设计，Redis 的 ZSet 才能同时高效地支持插入、排序、按分值范围查询和按成员查询等多种操作，成为一个功能强大且性能卓越的数据结构。