Redis 的 ZSET（Sorted Set，有序集合）

2025-3-4 diaba Redis

Redis 的 ZSET（Sorted Set，有序集合） 是一种非常强大的数据结构，它结合了集合（Set）和哈希表（Hash）的特点，能够存储带有分数（score）的成员（member），并且根据分数对成员进行排序。ZSET 的高效性和灵活性使其在许多场景中被广泛应用，例如实现排行榜、优先队列等。

ZSET 的底层实现结构

Redis 的 ZSET 底层使用了两种数据结构来实现：
  1. 双跳表（Skip List）
  2. 哈希表（Hash Table）
这两种结构共同工作，使得 ZSET 能够高效地支持快速插入、删除和范围查询等操作。

1. 双跳表（Skip List）

跳表是一种基于链表的多级索引数据结构，能够实现快速的查找、插入和删除操作。Redis 的跳表是双层跳表，即每个成员在跳表中同时维护两个指针：
  • 正向指针：用于从低分值到高分值的遍历。
  • 反向指针：用于从高分值到低分值的遍历。
特点：
  • 快速查找：跳表的时间复杂度为 O(log N)，与平衡树（如红黑树）相当，但实现更简单。
  • 动态扩展：跳表的层数是动态生成的，通过随机化算法决定每个节点的层数。
  • 支持范围查询：可以高效地获取某个分数范围内的成员。

2. 哈希表（Hash Table）

为了快速访问成员及其对应的分数，Redis 在跳表的基础上增加了一个哈希表。哈希表的键是成员（member），值是一个指针，指向跳表中的节点。
特点：
  • 快速访问：通过哈希表，可以在 O(1) 时间复杂度内直接访问到成员及其分数。
  • 去重：哈希表确保成员的唯一性，因为每个成员在哈希表中只能有一个键。

ZSET 的底层结构组合

Redis 的 ZSET 结构将跳表和哈希表结合起来，形成了一种高效的复合数据结构：
  • 哈希表：用于快速查找成员及其对应的跳表节点。
  • 跳表：用于快速排序和范围查询，支持高效的插入、删除和排序操作。
这种组合结构使得 ZSET 能够同时满足以下需求：
  1. 快速访问：通过哈希表实现 O(1) 的成员查找。
  2. 快速排序：通过跳表实现 O(log N) 的插入、删除和范围查询。
  3. 成员唯一性：哈希表确保成员不重复。

ZSET 的应用场景

由于 ZSET 的高效性和灵活性，它在以下场景中被广泛应用：
  1. 排行榜：根据分数对用户进行排序，例如游戏排行榜、电商销量排行榜等。
  2. 优先队列：根据分数动态调整队列顺序，例如任务调度、消息队列等。
  3. 时间序列数据：根据时间戳对数据进行排序，例如日志数据、监控数据等。

总结

Redis 的 ZSET 底层由双跳表和哈希表组成。跳表用于快速排序和范围查询，哈希表用于快速访问成员及其分数。这种复合结构使得 ZSET 能够高效地支持插入、删除、查找和范围查询等操作，是 Redis 中非常强大的数据结构之一。

标签: redis 分布式

« IO多路复用在Redis发挥重要作用 | 「Kadane算法」动态规划：求连续子数组最大值»

发表评论：

Powered by emlog 京ICP备15045175号-1 Copyright © 2022