Redis Sorted Set底层实现原理：跳表与排行榜实战应用

Sorted Set（有序集合）是 Redis 提供的一种高级数据结构。它与 Set 类似，保证成员（member）的唯一性，但每个成员会关联一个浮点数类型的分数（score）。集合内的元素会依据这个分数进行升序排序，如果分数相同，则按照成员字符串的字典顺序进行排序。

这种特性使其非常适合用于实现排行榜、延迟队列、滑动窗口限流器等场景。要深入理解其高性能背后的原因，就必须探究其底层的存储实现。

Sorted Set 的两种存储方式

Sorted Set 并非使用单一的数据结构，而是根据数据规模和内容动态选择存储方式，以达到性能与内存的平衡。

1. listpack（7.0版本前为 ziplist）存储：当集合元素数量不超过 zset-max-listpack-entries（默认128），且每个成员的大小不超过 zset-max-listpack-value（默认64字节）时，Redis 会选择使用 listpack 存储。这是一种紧凑的连续内存结构，member 和 score 成对顺序存放，旨在节省内存。
2. skiplist（跳表）+ dict（字典）存储：当不满足上述条件时，Redis 会采用 skiplist 和 dict 组合的方式来存储数据。这是一种典型的空间换时间的策略。新元素插入时，会同时向跳表和散列表中写入数据，以保证两者的一致性。

这种组合设计的目的是为了同时支持高效的范围查询和单点查询。ZRANGE 等范围查询命令得益于 skiplist，时间复杂度为 O(log(n)) + m；而像 ZSCORE key member 这样的单点查询，则通过 dict 实现 O(1) 时间复杂度的查询。

核心结构：跳表 (Skiplist) + 字典 (Dict)

跳表是 Sorted Set 实现有序性和高效范围查询的核心。

什么是跳表？
跳表的本质是一个支持“二分查找”的多层有序链表。它在基础的有序链表之上，通过随机算法构建多级索引，从而将查找、插入、删除的平均时间复杂度优化至 O(log n)，其性能与平衡树相当，但实现更为简单。

设想一个简单的有序链表，查询需要 O(n) 的时间。

如果在相邻节点间增加一个指向“下下个”节点的指针，形成第二层稀疏链表，查找效率就能提升一倍。

Redis 的跳表在此基础上更进一步，为每个节点随机生成一个层高。插入新节点时，只需修改前后指针，无需为了维持严格的索引比例而调整整个结构，从而保证了 O(log n) 的插入性能。

跳表的查找过程
查找总是从最高层索引开始。如果当前节点的值小于目标值，则继续访问本层的下一个节点；如果下一个节点的值大于目标值，则“下降”到当前节点的下一层链表继续查找。整个过程类似于在多层路径上进行跳跃式二分查找。

例如，在上图中查找 26，其路径如红色箭头所示，最终找到目标。

Redis 中跳表的结构定义
在源码中，Sorted Set (zset) 结构包含一个字典和一个跳表指针：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

跳表结构 zskiplist 定义如下：

typedef struct zskiplist {
    // 指向头节点和尾节点，便于双向遍历
    struct zskiplistNode *header, *tail;
    // 跳表中节点的数量（不含头节点）
    unsigned long length;
    // 当前跳表内，所有节点的最大层数
    int level;
} zskiplist;

跳表的节点 zskiplistNode 是关键：

typedef struct zskiplistNode {
    sds ele;          // 存储成员内容
    double score;     // 关联的分数
    struct zskiplistNode *backward; // 指向前一个节点的后退指针（用于双向遍历）

    struct zskiplistLevel {
        struct zskiplistNode *forward; // 该层的前进指针
        unsigned long span;           // 该层到下一个节点的跨度
    } level[]; // 柔性数组，表示节点的层级
} zskiplistNode;

• backward 指针使得跳表底层（Level 0）是一个双向链表，支持倒序遍历。
• level 数组的每一层都包含一个 forward 指针和 span 跨度值。span 记录了该层当前节点到下一个节点之间，跨越了底层（Level 0）多少个节点。这个值对于计算元素的排名至关重要，例如执行 ZRANK 命令时，只需将查找路径上各节点的 span 累加即可。

下图展示了一个包含具体元素的 Redis 跳表结构：

紧凑存储：listpack

当集合规模较小时，为节省内存，Redis 会使用 listpack 存储。在源码 zaddGenericCommand 函数中，会根据配置决定使用 createZsetObject()（跳表+字典）还是 createZsetListpackObject()。

listpack 是一块连续内存，每个 (member, score) 对在其中紧凑排列，member 在前，score 在后。查找时需要顺序遍历，时间复杂度为 O(n)，但由于数据量小，对性能影响有限，却换来了显著的内存节省。

实战：游戏排行榜实现

掌握了原理，我们来看一个经典应用：实时游戏高分排行榜。需求如下：

• 按分数从高到低排名，查询 Top N。
• 新增或更新玩家分数。
• 查看任意玩家的排名和分数。

我们可以用 Sorted Set 轻松实现：member 存储玩家 ID，score 存储游戏分数。但有一个细节：分数相同，先达到该分数的玩家排名更靠前。这意味着时间戳也需要影响排序。

分数设计
由于分数越大排名越高，而时间戳越小排名越高，两者规则相反。我们可以设计一个复合分数：
最终分数 = 游戏分数 + ((基准时间 - 获得分数的时间) / 基准时间)

这里的“基准时间”是一个未来的超大时间戳（例如 12023 年）。公式后半部分 ((基准时间 - t) / 基准时间) 的结果小于 1，作为小数部分附加在游戏分数后。游戏分数相同时，获得分数越早（t 越小），计算得到的小数部分越大，从而总分数越高，排名越靠前。

private double calcScore(int playerScore, long playerScoreTime) {
  return playerScore + (BASE_TIME - playerScoreTime) * 1.0 / BASE_TIME;
}

操作指令示例
假设基准时间戳为 317242022400，对应 12023 年。

1. 更新/新增玩家分数：使用 ZADD 命令。

   redis> ZADD leaderboard:339 2500.994707057989 player:1
   redis> ZADD leaderboard:339 500.99470705798905 player:2
   redis> ZADD leaderboard:339 500.9947097814618 player:3  # 与player:2同分，但时间稍晚

2. 获取 Top 3 玩家：使用 ZRANGE key start stop REV WITHSCORES 进行逆序（分数从高到低）查询。

   > ZRANGE leaderboard:339 0 2 REV WITHSCORES
   1) "player:1"
   2) "2500.9947070579892"
   3) "player:3"
   4) "500.99470978146178"
   5) "player:2"
   6) "500.99470705798905"

   可以看到，分数相同时，player:2（小数部分更小）排在了 player:3 后面。

3. 获取指定玩家排名：使用 ZREVRANK 命令，排名从 0 开始。

   > ZREVRANK leaderboard:339 player:2
   (integer) 2  # 表示第三名

总结

Sorted Set 是 Redis 中功能强大的数据结构，其底层通过动态选择 listpack 或（skiplist + dict）的存储策略，在内存效率与查询性能之间取得了精妙的平衡。理解跳表的工作原理，不仅能帮助我们更好地使用 Sorted Set，也揭示了其支持高效范围查询和排序的根源。将其应用于排行榜等场景时，通过巧妙的分数设计，可以满足复杂的业务排序规则。