ZSet详解

要理解Redis的ZSet（有序集合，Sorted Set），需要从核心特性、底层实现原理、操作逻辑和应用场景四个维度展开。ZSet是Redis中最强大的数据结构之一，兼具集合的唯一性（成员不重复）和有序性（按分数排序），适用于多种复杂场景（如排行榜、延迟队列、范围查询等）。

一、ZSet的核心特性

ZSet中的每个元素由两部分组成：成员（Member） 和 分数（Score）。其核心特点如下：

1. 成员唯一性：每个Member在ZSet中唯一，无法重复（类似Set）。
2. 分数可重复：不同Member可以有相同的Score（如多个用户得分为100）。
3. 有序性：ZSet会按Score从小到大自动排序（支持升序/降序查询）。
4. 灵活的分数类型：Score可以是双精度浮点数（如10.5、-3.14），支持精确排序。

二、ZSet的底层实现：跳跃表（Skip List）+ 哈希表（Hash Table）

Redis的ZSet并没有使用红黑树、AVL树等平衡树结构，而是采用跳跃表（Skip List）和哈希表（Hash Table）的组合结构。这种设计兼顾了快速查询、插入/删除和范围遍历的需求。

1. 哈希表（Hash Table）：快速定位Member的Score

• 作用：存储Member→Score的映射，用于快速判断Member是否存在（O(1)时间）和获取Member的Score（O(1)时间）。
• 细节：哈希表的Key是Member（字符串），Value是对应的Score（双精度浮点数）。当执行ZSCORE key member时，直接通过哈希表查询，无需遍历有序结构。

2. 跳跃表（Skip List）：维护有序结构，支持快速范围操作

跳跃表是ZSet的核心有序结构，用于实现按Score排序和快速插入/删除/范围查询（均为O(logN)时间复杂度，N为元素数量）。

（1）跳跃表的结构设计

跳跃表是一种多层链表，每层都是一个有序链表（按Score升序排列）。其节点结构如下（简化版）：

typedef struct zskiplistNode {
    sds member;          // 成员（字符串）
    double score;        // 分数
    struct zskiplistNode *backward;  // 反向指针（用于从后往前遍历）
    struct zskiplistLevel {
        struct zskiplistNode *forward;  // 正向指针（指向当前层的下一个节点）
        unsigned long span;             // 当前节点到下一个节点的间隔数（用于计算排名）
    } level[];           // 动态层级数组（每层一个forward指针和span）
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header;  // 表头节点（不存储实际数据）
    struct zskiplistNode *tail;    // 表尾节点
    unsigned long length;          // 跳跃表中的节点数量（即ZSet的大小）
    int level;                     // 跳跃表的最高层级（表头的层级）
} zskiplist;

（2）跳跃表的核心特性

• 层级随机性：每个新节点的层级是随机生成的（通过概率算法），遵循幂次定律（即层级越高，出现的概率越低）。例如：

  • 层级为1的概率是1/2；
  • 层级为2的概率是1/4；
  • 层级为3的概率是1/8；
  • 以此类推，最高层级默认是32（可配置）。 这种设计保证了跳跃表的平衡性，避免退化成普通链表（O(N)时间复杂度）。

• 快速查询：查询时从表头的最高层开始，逐层向下遍历。每一层都跳过不需要的节点（例如，当前层的下一个节点Score小于目标Score，则继续前进；否则，下降到下一层）。直到找到目标节点或到达底层。

  • 示例：查询Score=20的节点，过程如下：
    1. 从最高层（假设是3层）开始，表头的forward指针指向节点A（Score=10），继续前进；
    2. 节点A的3层forward指针指向节点C（Score=30），此时30>20，下降到2层；
    3. 节点A的2层forward指针指向节点B（Score=20），找到目标节点。

• 范围遍历：由于跳跃表是双向链表（每个节点有backward指针），且每层都是有序的，因此可以快速实现升序/降序的范围查询（如ZRANGE、ZREVRANGE）。例如，获取Score在[10, 30]之间的所有节点，只需找到起始节点（Score=10），然后沿底层的forward指针遍历到结束节点（Score=30）即可。

（3）跳跃表 vs 平衡树（红黑树）

Redis选择跳跃表而非红黑树的原因：

• 实现简单：跳跃表的插入、删除逻辑比红黑树更直观（无需旋转操作），代码可读性和维护性更好。
• 性能相当：在大多数场景下，跳跃表的查询、插入、删除时间复杂度与红黑树相同（O(logN)），且缓存命中率更高（节点的层级连续，内存访问更高效）。
• 范围查询更高效：跳跃表的范围遍历是线性的（O(K)，K为结果数量），而红黑树需要遍历整个树结构（O(logN + K)），跳跃表的范围操作更直接。

三、ZSet的常见操作及时间复杂度

ZSet的操作主要围绕成员管理、分数修改、排序查询三类，以下是关键操作的说明：

操作	描述	时间复杂度
ZADD key score member	添加/修改成员（存在则更新Score）	O(logN)
ZREM key member	删除成员	O(logN)
ZSCORE key member	获取成员的Score	O(1)（哈希表查询）
ZRANGE key start stop	按Score升序获取[start, stop]区间的成员	O(logN + K)（K为结果数量）
ZREVRANGE key start stop	按Score降序获取区间成员	O(logN + K)
ZRANK key member	获取成员的升序排名（从0开始）	O(logN)
ZREVRANK key member	获取成员的降序排名	O(logN)
ZRANGEBYSCORE key min max	按Score范围获取成员（支持闭区间/开区间）	O(logN + K)
ZINCRBY key increment member	增加成员的Score（原子操作）	O(logN)

四、ZSet的应用场景

ZSet的有序性和快速范围查询特性使其适用于多种场景：

1. 排行榜系统

• 例如：用户积分排行榜、文章阅读量排行榜。
• 操作：使用ZADD添加/更新用户积分，ZREVRANGE获取前N名用户（降序），ZRANK获取用户的排名。
• 示例：

  ZADD rank:user 100 alice 200 bob 150 charlie  # 添加用户积分
  ZREVRANGE rank:user 0 2 WITHSCORES  # 获取前3名（降序）：bob(200)、charlie(150)、alice(100)
  ZRANK rank:user alice  # 获取alice的升序排名：2（从0开始）

2. 延迟队列

• 例如：订单超时未支付自动关闭、定时任务调度。
• 原理：将任务的执行时间作为Score，存入ZSet。消费者定期查询ZRANGEBYSCORE key 0 当前时间，获取到期的任务并执行。
• 操作：

  ZADD delay:order 1625097600 order:123  # 订单123的执行时间是2021-07-01 00:00:00（时间戳）
  ZRANGEBYSCORE delay:order 0 1625097600 WITHSCORES  # 获取到期的订单
  ZREM delay:order order:123  # 执行完成后删除任务

3. 范围查询

• 例如：获取分数在[80, 100]之间的学生、统计活跃用户（最后登录时间在最近7天内）。
• 操作：

  ZADD score:student 85 tom 90 jerry 95 lucy 70 mike  # 添加学生分数
  ZRANGEBYSCORE score:student 80 100 WITHSCORES  # 获取分数在80-100之间的学生：tom(85)、jerry(90)、lucy(95)

4. 有序集合的交集/并集

• 例如：获取两个用户群体的共同关注（交集）、合并两个排行榜（并集）。
• 操作：ZINTERSTORE（交集）、ZUNIONSTORE（并集），支持按Score求和、取最大值、取最小值。
• 示例：

  ZADD set1 1 a 2 b 3 c  # 集合1
  ZADD set2 2 b 3 c 4 d  # 集合2
  ZINTERSTORE result 2 set1 set2 AGGREGATE SUM  # 交集（b、c），Score求和：b(4)、c(6)
  ZRANGE result 0 -1 WITHSCORES  # 输出：b(4)、c(6)

五、ZSet的优化与注意事项

1. Score的精度问题：Score是双精度浮点数，存在精度损失（如0.1+0.2=0.30000000000000004）。如果需要精确排序，建议使用整数（如将分数乘以100转为整数）。
2. 内存占用：ZSet的内存占用比Set大（每个元素需要存储在哈希表和跳跃表中）。对于大规模数据，建议合理设置跳跃表的最高层级（默认32层，足够支持2^32个元素）。
3. 避免高频更新：频繁执行ZADD（更新Score）会导致跳跃表的节点重新排序，影响性能。如果需要高频更新，建议使用ZINCRBY（原子递增），而非每次重新设置Score。
4. 范围查询的效率：ZRANGEBYSCORE和ZRANGE的时间复杂度是O(logN + K)，其中K是结果数量。如果K很大（如获取全部元素），建议使用ZRANGE key 0 -1（O(N)时间），而非ZRANGEBYSCORE（O(logN + N)）。

总结

ZSet是Redis中有序性和唯一性结合的核心数据结构，其底层通过跳跃表实现有序结构（支持快速插入/删除/范围查询），通过哈希表实现快速的Member定位（O(1)时间）。这种组合设计使其适用于排行榜、延迟队列、范围查询等多种场景，是Redis中最常用的数据结构之一。

理解ZSet的底层原理，有助于更好地优化其使用（如避免Score精度问题、减少内存占用、提高操作效率），从而充分发挥Redis的性能优势。