Redis 有序集合

Redis 有序集合简介

Redis 有序集合是一个由唯一字符串(成员)组成的集合,这些字符串按照关联的分数进行排序。 当多个字符串具有相同的分数时,这些字符串按字典顺序排序。 有序集合的一些使用场景包括:

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

你可以将排序集合视为集合和哈希之间的混合体。与集合一样,排序集合由唯一的、不重复的字符串元素组成,因此在某种意义上,排序集合也是一个集合。

然而,虽然集合中的元素没有顺序,但排序集合中的每个元素都与一个浮点值相关联,称为分数(这就是为什么该类型也类似于哈希,因为每个元素都映射到一个值)。

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

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

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

正如你所见,ZADD 类似于 SADD,但多了一个参数(放在要添加的元素之前),即分数。 ZADD 也是可变参数的,因此你可以自由指定多个分数-值对,即使在上面的示例中没有使用。

使用有序集合,返回按出生年份排序的赛车手列表非常简单,因为实际上它们已经是有序的

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

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

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

操作范围

有序集合比这更强大。它们可以在范围内操作。 让我们获取所有得分在10分或以下的赛车手。我们 使用ZRANGEBYSCORE命令来完成这个操作:

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

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

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

另一个对排序集合元素非常有用的操作是获取排名操作。可以询问一个元素在有序元素集合中的位置。为了获取排名,还可以使用ZREVRANK命令,考虑元素以降序方式排序。

词典编纂分数

在Redis 2.8版本中,引入了一个新特性,允许按字典顺序获取范围,假设有序集合中的所有元素都以相同的分数插入(元素使用C语言的memcmp函数进行比较,因此保证没有排序规则,每个Redis实例都会返回相同的输出)。

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

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

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

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

更新分数:排行榜

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

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

示例

  • There are two ways we can use a sorted set to represent a leaderboard. If we know a racer's new score, we can update it directly via the ZADD command. However, if we want to add points to an existing score, we can use the ZINCRBY command.

你会看到,当成员已经存在时(分数被更新),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 功能。

了解更多

RATE THIS PAGE
Back to top ↑