Redis 有序集合

Redis 有序集合简介

Redis 有序集合是一个包含唯一字符串(成员)的集合,这些字符串按关联的分数排序。当多个字符串具有相同的分数时,它们按字典序排序。有序集合的一些用例包括

  • 排行榜。例如,您可以使用有序集合轻松维护大型在线游戏中的最高分有序列表。
  • 速率限制器。特别是,您可以使用有序集合构建一个滑动窗口速率限制器,以防止过多的 API 请求。

您可以将有序集合视为集合(Set)和哈希(Hash)的混合体。像集合一样,有序集合由唯一的、不重复的字符串元素组成,所以在某种意义上,有序集合也是一个集合。

然而,集合内部的元素是无序的,而有序集合中的每个元素都关联着一个浮点数值,称为分数(这就是为什么这种类型也类似于哈希,因为每个元素都映射到一个值)。

此外,有序集合中的元素是按顺序存放的(因此它们不是在请求时排序,顺序是用于表示有序集合的数据结构的特有属性)。它们按照以下规则排序:

  • 如果 B 和 A 是具有不同分数的两个元素,那么如果 A 的分数 > B 的分数,则 A > B。
  • 如果 B 和 A 具有完全相同的分数,那么如果字符串 A 在字典序上大于字符串 B,则 A > B。B 和 A 字符串不能相等,因为有序集合只包含唯一元素。

让我们从一个简单的例子开始,我们将添加所有赛车手及其在第一场比赛中的得分

如您所见,ZADDSADD 类似,但多了一个参数(放在要添加的元素之前)作为分数。ZADD 也是可变参数的,因此您可以自由指定多个分数-值对,如上面的示例所示。

使用有序集合,返回按分数排序的赛车手列表非常简单,因为实际上它们已经排好序了

实现说明:有序集合通过包含跳跃列表和哈希表的双端口数据结构实现,因此每次添加元素时,Redis 执行 O(log(N)) 操作。这是优点,所以当我们请求有序元素时,Redis 无需进行任何工作,它们已经排好序了。请注意,ZRANGE 的顺序是从低到高,而 ZREVRANGE 的顺序是从高到低

注意:0 和 -1 表示从索引 0 到最后一个元素(-1 在这里的工作方式与 LRANGE 命令中相同)。

也可以使用 WITHSCORES 参数返回分数

范围操作

有序集合比这更强大。它们可以对范围进行操作。让我们获取所有得分小于等于 10 的赛车手。我们使用 ZRANGEBYSCORE 命令来完成此操作

我们要求 Redis 返回所有分数在负无穷到 10 之间的元素(包括两端)。

要删除一个元素,我们只需使用赛车手的名字调用 ZREM。也可以删除元素范围。让我们删除赛车手 Castilla 以及所有得分严格小于 10 的赛车手

ZREMRANGEBYSCORE 命令名称可能不是最好的,但它非常有用,并返回被移除元素的数量。

为有序集合元素定义的另一个非常有用的操作是获取排名(get-rank)操作。可以查询一个元素在有序元素集合中的位置。为了获取按降序排序的元素排名,还可以使用 ZREVRANK 命令。

按字典序排序

在 Redis 2.8 版本中,引入了一项新功能,允许按字典序获取范围,前提是向有序集合中插入的所有元素都具有相同的分数(元素使用 C 语言的 memcmp 函数进行比较,因此保证没有排序规则差异,并且每个 Redis 实例将返回相同的结果)。

用于字典序范围操作的主要命令是 ZRANGEBYLEXZREVRANGEBYLEXZREMRANGEBYLEXZLEXCOUNT

例如,让我们再次添加著名赛车手列表,但这次所有元素都使用分数零。我们将看到,由于有序集合的排序规则,它们已经按字典序排序。使用 ZRANGEBYLEX 我们可以请求字典序范围

范围可以是包含或不包含的(取决于第一个字符),字符串的无穷大和负无穷大分别用字符串 +- 指定。有关更多信息,请参阅文档。

此功能很重要,因为它允许我们将有序集合用作通用索引。例如,如果您想按 128 位无符号整数参数对元素进行索引,您只需将元素添加到具有相同分数(例如 0)的有序集合中,但前缀为 16 字节,包含大端序的 128 位数字。由于大端序数字按字典序(原始字节顺序)排序时,实际上也按数值排序,您可以在 128 位空间中请求范围,并获取元素值,同时丢弃前缀

更新分数:排行榜

在切换到下一主题之前,关于有序集合的最后一句话。有序集合的分数可以随时更新。只需对有序集合中已包含的元素调用 ZADD,就会以 O(log(N)) 的时间复杂度更新其分数(和位置)。因此,当有大量更新时,有序集合非常适用。

由于此特性,一个常见的用例是排行榜。典型的应用是 Facebook 游戏,您可以结合按最高分排序用户的功能以及获取排名操作,以便显示前 N 名用户和用户在排行榜中的排名(例如,“您在这里排名第 4932 位”)。

示例

  • 有两种方法可以使用有序集合表示排行榜。如果我们知道赛车手的新分数,可以直接通过 ZADD 命令更新。但是,如果我们想在现有分数上增加分数,可以使用 ZINCRBY 命令。

您会看到,当成员已存在时,ZADD 返回 0(分数被更新),而 ZINCRBY 返回新分数。赛车手 Henshaw 的分数从 100 变为 150,这与之前的分数无关,然后又增加了 50 分,变为 200。

基本命令

  • ZADD 向有序集合添加新成员和关联分数。如果成员已存在,则更新分数。
  • ZRANGE 返回有序集合中给定范围内的成员,按分数排序。
  • ZRANK 返回给定成员的排名,假定有序集合按升序排列。
  • ZREVRANK 返回给定成员的排名,假定有序集合按降序排列。

查看 有序集合命令的完整列表

性能

大多数有序集合操作的时间复杂度为 O(log(n)),其中 n 是成员数。

在使用 ZRANGE 命令返回大量结果(例如,数万或更多)时要小心。此命令的时间复杂度为 O(log(n) + m),其中 m 是返回结果的数量。

替代方案

Redis 有序集合有时用于索引其他 Redis 数据结构。如果您需要索引和查询数据,请考虑 JSON 数据类型和 Redis Query Engine 功能。

了解更多

评价此页面
返回顶部 ↑