有序集合Zset

  • Redis 有序集合 zset 与普通集合 set 非常相似,是一个没有重复元素的字符串集合。

  • 不同之处是有序集合的每个成员都关联了一个评分(score),这个评分(score)被用来按照从最低分到最高分的方式排序集合中的成员。集合的成员是唯一的,但是评分可以是重复了 。

  • 因为元素是有序的,所以你也可以很快的根据评分(score)或者次序(position)来获取一个范围的元素。

  • 访问有序集合的中间元素也是非常快的,因此你能够使用有序集合作为一个没有重复成员的智能列表。
     

常用命令

  • zadd <key><score1><value1><score2><value2> 将一个或多个member元素及其score值加入到有序集key中

  • zrange <key><start><stop> [WITHSCORES] 返回有序集key中,下标在 之间的元素,带WITHSCORES,可以让分数一起和值返回到结果集

  • zrangebyscore key minmax [withscores] [limit offset count] 返回有序集key中,所有score值介于min和max之间(把包括等于min或max)的成员。有序集成员按score值递增(从小到大)次序排列

  • zrevrangebyscore key maxmin [withscores] [limit offset count] 同上,改为从大到小排列

  • zincrby <key> <increment> <value> 为元素的score加上增量

  • zrem <key> <value> 删除该集合下,指定值的元素

  • zcount <key> <min> <max> 统计该集合,分数区间内的元素个数

  • zrank <key> <value> 返回该值在集合中的排名,从0开始
     

Zset数据结构

SortedSet (zset) 是 Redis 提供的一个非常特别的数据结构,一方面它等价于 Java 的数据结构 Map<String, Double>,可以给每一个元素 value 赋予一个权重 score,另一方面它又类似于 TreeSet,内部的元素会按照权重 score 进行排序,可以得到每个元素的名次,还可以通过 score 的范围来获取元素的列表。

zset 底层使用了两个数据结构:

  1. hash,hash 的作用就是关联元素 value 和权重 score,保障元素 value 的唯一性,可以通过元素 value 找到相应的 score 值。

  2. 跳跃表,跳跃表的目的在于给元素 value 排序,根据 score 的范围获取元素列表。
     

跳跃表

有序集合在生活中比较常见,例如根据成绩对学生排名,根据得分对玩家排名等。对于有序集合的底层实现,可以用数组、平衡树、链表等。数组不便元素的插入、删除;平衡树或红黑树虽然效率高但结构复杂;链表查询需要遍历所有效率低。Redis 采用的是跳跃表,跳跃表效率堪比红黑树,实现远比红黑树简单。

对比有序链表和跳跃表,从链表中查询出 51:

有序链表

​ 要查找值为 51 的元素,需要从第一个元素开始依次查找、比较才能找到。共需要 6 次比较。

跳跃表

  • 从第 2 层开始,1 节点比 51 节点小,向后比较;

  • 21 节点比 51 节点小,继续向后比较,后面就是 NULL 了,所以从 21 节点向下到第 1 层;

  • 在第 1 层,41 节点比 51 节点小,继续向后,61 节点比 51 节点大,所以从 41 向下;

  • 在第 0 层,51 节点为要查找的节点,节点被找到,共查找 4 次。

从此可以看出跳跃表比有序链表效率要高。