Redis 面试必备 > redis 基础数据结构
reids 基础数据结构 zset

Redis 有序集合(sorted set)

Redis 有序集合和集合一样也是string类型元素的集合,且不允许重复的成员。

不同的是每个元素都会关联一个double类型的分数。redis正是通过分数来为集合中的成员进行从小到大的排序。

有序集合的成员是唯一的,但分数(score)却可以重复。

redis sorted sets里面当items内容大于64的时候同时使用了hash和skiplist两种设计实现。这也会为了排序和查找性能做的优化。所以如上可知: 添加和删除都需要修改skiplist,所以复杂度为O(log(n))。 

但是如果仅仅是查找元素的话可以直接使用hash,其复杂度为O(1) ,

其他的range操作复杂度一般为O(log(n)),

当然如果是小于64的时候,因为是采用了ziplist的设计,其时间复杂度为O(n)。

 集合中最大的成员数为 232 - 1 (4294967295, 每个集合可存储40多亿个成员)。



Redis 有序集合命令

下表列出了 redis 有序集合的基本命令:

序号命令及描述
1ZADD key score1 member1 [score2 member2]
向有序集合添加一个或多个成员,或者更新已存在成员的分数
2ZCARD key
获取有序集合的成员数
3ZCOUNT key min max
计算在有序集合中指定区间分数的成员数
4ZINCRBY key increment member
有序集合中对指定成员的分数加上增量 increment
5ZINTERSTORE destination numkeys key [key ...]
计算给定的一个或多个有序集的交集并将结果集存储在新的有序集合 key 中
6ZLEXCOUNT key min max
在有序集合中计算指定字典区间内成员数量
7ZRANGE key start stop [WITHSCORES]
通过索引区间返回有序集合指定区间内的成员
8ZRANGEBYLEX key min max [LIMIT offset count]
通过字典区间返回有序集合的成员
9ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT]
通过分数返回有序集合指定区间内的成员
10ZRANK key member
返回有序集合中指定成员的索引
11ZREM key member [member ...]
移除有序集合中的一个或多个成员
12ZREMRANGEBYLEX key min max
移除有序集合中给定的字典区间的所有成员
13ZREMRANGEBYRANK key start stop
移除有序集合中给定的排名区间的所有成员
14ZREMRANGEBYSCORE key min max
移除有序集合中给定的分数区间的所有成员
15ZREVRANGE key start stop [WITHSCORES]
返回有序集中指定区间内的成员,通过索引,分数从高到低
16ZREVRANGEBYSCORE key max min [WITHSCORES]
返回有序集中指定分数区间内的成员,分数从高到低排序
17ZREVRANK key member
返回有序集合中指定成员的排名,有序集成员按分数值递减(从大到小)排序
18ZSCORE key member
返回有序集中,成员的分数值
19ZUNIONSTORE destination numkeys key [key ...]
计算给定的一个或多个有序集的并集,并存储在新的 key 中
20ZSCAN key cursor [MATCH pattern] [COUNT count]
迭代有序集合中的元素(包括元素成员和元素分值)


 zset内部的排序功能是通过「跳跃列表」数据结构来实现的,它的结构非常特殊,也比较复杂。这一块的内容深度读者要有心理准备。

因为zset要支持随机的插入和删除,所以它不好使用数组来表示。我们先看一个普通的链表结构。



我们需要这个链表按照score值进行排序。这意味着当有新元素需要插入时,需要定位到特定位置的插入点,这样才可以继续保证链表是有序的。通常我们会通过二分查找来找到插入点,但是二分查找的对象必须是数组,只有数组才可以支持快速位置定位,链表做不到,那该怎么办?

想想一个创业公司,刚开始只有几个人,团队成员之间人人平等,都是联合创始人。随着公司的成长,人数渐渐变多,团队沟通成本随之增加。这时候就会引入组长制,对团队进行划分。每个团队会有一个组长。开会的时候分团队进行,多个组长之间还会有自己的会议安排。公司规模进一步扩展,需要再增加一个层级——部门,每个部门会从组长列表中推选出一个代表来作为部长。部长们之间还会有自己的高层会议安排。

跳跃列表就是类似于这种层级制,最下面一层所有的元素都会串起来。然后每隔几个元素挑选出一个代表来,再将这几个代表使用另外一级指针串起来。然后在这些代表里再挑出二级代表,再串起来。最终就形成了金字塔结构。

想想你老家在世界地图中的位置:亚洲-->中国->安徽省->安庆市->枞阳县->汤沟镇->田间村->xxxx号,也是这样一个类似的结构。



「跳跃列表」之所以「跳跃」,是因为内部的元素可能「身兼数职」,比如上图中间的这个元素,同时处于L0、L1和L2层,可以快速在不同层次之间进行「跳跃」。

定位插入点时,先在顶层进行定位,然后下潜到下一级定位,一直下潜到最底层找到合适的位置,将新元素插进去。你也许会问那新插入的元素如何才有机会「身兼数职」呢?

跳跃列表采取一个随机策略来决定新元素可以兼职到第几层,首先L0层肯定是100%了,L1层只有50%的概率,L2层只有25%的概率,L3层只有12.5%的概率,一直随机到最顶层L31层。绝大多数元素都过不了几层,只有极少数元素可以深入到顶层。列表中的元素越多,能够深入的层次就越深,能进入到顶层的概率就会越大。

这还挺公平的,能不能进入中央不是靠拼爹,而是看运气。