Redis远程字典服务器(8)—— zset类型详解
与你日常 2024-10-10 15:07:07 阅读 83
目录
一,基本情况
二,常用命令
2.1 zadd
2.2 zcard,zcount
2.3 zrange,zrevrange,zrangebyscore
2.4 zpopmax,bzpopmax
2.5 zpopmin,bzpopmin
2.6 zrank,zrevrank,zscore
2.7 zrem,zremrangebyrank,zremrangebyscore
2.8 zincrby
2.9 zinterstore,zunionstore
三,内部编码
四,应用场景
4.1 排行榜系统
一,基本情况
Zset,叫做“有序集合”
Set(集合):唯一性,无序性(孙行者,行者孙,者行孙 ==> 同一只猴 )List(列表):有序性,可重复(孙行者,行者孙,者行孙 ==> 不同的猴)Zset(有序集合):这里的“有序”,单指 “升序/降序 ”
问题:那么排序的顺序是啥?
解答:我们给 zset 中的 member 同时引入了一个属性 => 分数(score),浮点类型,进行排序的时候,就是按照此处的分数大小来进行 “ 升序/降序 ”的,如下图:
注意: “升序/降序”只是为了解释“有序”这个词的广泛性,实际上zset内部还是按照“升序”来排列的
zset也是一个集合,所以member仍然要求是唯一的,score可以重复,因为 zset主要还是用来存member的,score只是辅助
数据结构
| 是否允许重复元素 | 是否有序 | 有序依据 | 应用场景 |
---|---|---|---|---|
list(列表) | 是 | 是 | 索引下标 | 时间轴,消息队列等 |
set(集合) | 否 | 否 | 标签,社交等 | |
zset(有序集合) | 否 | 是 | 分数 | 排行榜系统,社交等 |
二,常用命令
2.1 zadd
ZADD key [NX | XX] [GT | LT] [CH] [INCR] score member [score member
...]
zadd作用是往集合中添加或修改元素和分数,首先指定key,方括号为可选选项,score为添加的分数,member为添加的值,其中 member 和 score 称为是一个“pair”类型,类似于C++里的std:pair,类似于键值对,但又不是键值对,因为对于有序集合来说,是既可以通过member找到score,也可以通过score找到member的。
C++的pair使用可以参考:C++——map和set的基本使用_c++中关联式容器-CSDN博客
然后是对于方括号里面选项的解释:
NX:当member不存在的时候,添加新member,如果member存在什么都不做XX:当member存在的时候,更新member的值,如果member不存在什么都不做不加 NX|XX 时:如果当前member不存在,此时就会达到“添加新member”的效果,如果当前member已经存在,就会更新分数LT:在要更新分数的前提下,如果新分数比旧分数小,就更新成功,否则不更新,不会阻止添加新memberGT:在要更新分数的前提下,如果新分数比旧分数大,就更新成功,否则不更新,不会阻止添加新memberCH:“ C ” 是“ change ”的缩写,作用是指定返回值要返回什么信息,本来zadd返回的是新增元素的个数,添加CH选项后返回被修改的元素个数INCR:作用是能针对现有的member的score进行运算
问题:之前的Hash,Set,List 很多时候,添加一个元素的时间复杂度都是O(1),但为什么Zset是O(logN)?
解答:因为zset是有序结构,所以新增元素时需要计算合适的位置再添加,当然之所以是logN不是N,也是利用了有序这样的特定。
但是也有分数相同的情况,所以当分数相同时,再按照元素自身的字典序来排列,分数不同仍然按照分数来排
下面是zadd的使用:
但是上面的只能显示member,不显示score,所以我们可以在后面加上“ withscores ”选项使其显示分数:
我们也可以使用zadd修改对应member的分数:
如果修改的分数影响到了之前的顺序,就会自动移动元素的位置,从而保持原有的升序顺序不变:
最后我们使用以下zadd的选项,NX|XX 作用和之前一样,这里就不介绍了:
注意:
LT和GT选项要在高版本的Redis才会有,但是使用起来也非常简单C++中的std:set也可以存pair,同时也是有序的,但是和Redis的set最大的不同是,std:set不能修改,只能添加或者删除
2.2 zcard,zcount
ZCARD key
ZCOUNT key min max
zcard作用是获取zset里元素的个数zcount作用是找出score符合区间[min, max]的member的个数,以返回值显示,[min, max]是闭区间:
上面的是闭区间,如果我们想排除边界值,需要用括号,但是这里的写法有点奇怪,如下图:
问题:一般来说,一个好的设计,是符合直觉的,因为这样学习和使用成本就越低;但是像这个添加括号就明显不符合直觉,那么为什么不改呢?
解答:既然已经这样设定了,只能将错就错,遵守这样的规则了,因为需要考虑兼容性,只要新的Redis一改,大量的代码直接就不能用了,需要大量的修改,成本是非常非常高的,会导致大量的服务器直接罢工
C++最近火起来的原因,就是因为C++兼容C,而当代大多数的热门操作系统都是用C写的而且其实为了解决IPv4地址不足的问题,我国早就开始高IPv6了,而且几近成熟,但是仍然没有大量推广,就是因为这玩意儿是和设备绑定的,要换IPv6,就需要摒弃IPv4的设备,引入IPv6的设备,这其实是一件非常耗时烧钱耗精力的事情,需要长期慢慢推进
zcount的时间复杂度是 O(logN)
问题:假设是先根据min和max找到对应的元素,如果要进行一个遍历,是不是就知道这里的元素个数了呢?
解答:那样的话时间复杂度就是O(N)了,就不是O(logN)了,根据找min和max就是O(logN)了,再加上遍历就是O(logN + M)了,M是区间中元素的个数,N是整个有序集合的个数
实际上Zset内部,会记录每个元素当前的 “排行” / “次序”,查询到元素,就直接知道了元素所在的“次序”,就可以直接把max对应的元素次序和min对应的元素次序做减法即可。
注意:zcount的min和max是支持分数的,所以可以写成浮点数,而且其中还有两个特殊值:inf表示无穷大,-inf表示负无穷大:
负无穷大不是无穷小,无穷小应该指的是无限接近于0的数
2.3 zrange,zrevrange,zrangebyscore
zrange作用是查看指定的一对下标构成的区间的值,前面已经用过很多次了zrevrange,z后面的三个字母“ rev ”其实是“ reverse ”的缩写,意思为“ 逆序 ”,所以zrevrange作用是按照分数降序进行遍历的前面两个都是按照下标区间来找元素的,zrangebyscore作用是按照分数来找元素的,和zcount类似:
注意:zrangebyscor已经标记成“废弃”,可能在Redis 6.2.0 之后废弃,并且功能会合并到zrange中
2.4 zpopmax,bzpopmax
zpopmax key [count]
BZPOPMAX key [key ...] timeout
zpopmax作用是删除并返回分数最高的count个元素,就是 topK 问题,如果存在多个分数相同的元素,同时为最大值,zpopmax仍然只删除其中一个 咱们这里的“有序集合”也可以视为一个“优先级队列”,有的时候,也需要一个带有“阻塞功能”的优先级队列,就可以用bzpopmax实现阻塞功能,timeout表示超时时间,其他的具体使用和细节再list的blpop和brpop已经讲解过,这里不再赘述:Redis远程字典服务器(6) —— list类型详解-CSDN博客
引出:zpopmax的时间复杂度是O(logN + M),其中N是有序集合的元素个数,M表示coun他,要删除的元素个数;此处zpopmax删除最大的元素,由于集合是有序的,最大值相当于最后一个元素,也就相当于“尾删”
问题:既然是尾删,那为什么不把这最后一个元素的位置特殊记录下来,省去了查找的过程,后续删除不就可以O(1)了吗?
解答:可以做到,但是Redis没有这么做,而且实际上,在Redis源码中,针对有序集合,确实是记录了“尾部”这样的特定位置,但是实际删除的时候,是直接调用了一个“通用的删除函数”,给定一个member的值,进行查找,找到位置在删除
所以是存在优化空间的,但是优化一般是要先找到性能瓶颈的,再针对性的优化
bzpopmax的效果和blpop一样,这里就不展示了:Redis远程字典服务器(6) —— list类型详解-CSDN博客
2.5 zpopmin,bzpopmin
ZPOPMIN key [count]
BZPOPMIN key [key ...] timeout
zpopmin就是和zpopmax反过来的,删除最小的count个元素:
此处zpopming和zpopmax的逻辑是一致的,bzpopmin也是一样的,删除的时候是使用的通用的删除函数,所以有了查找的过程,时间复杂度是O(logN + M) ,M是要删除的个数,所以可以不记,最后的时间复杂度可以为O(logN)
2.6 zrank,zrevrank,zscore
zrank作用是获取指定元素的排名,这个“排名”就是“下标”zrevrank作用也是获取member的下标,但是是反着算的zscore作用是查询指定member的分数
zrank:
zrank得到的下标是从前往后(升序)算的。
zrevrank:
zscore:
问题:zscore明明也有“根据member找score”的查询操作,为什么它的时间复杂度是O(1)?
解答:此处可以认为是Redis对查询操作做了特殊优化,付出了额外的空间代价,针对这里进行优化到了O(1)的,因为Redis的设计者发现这个查询操作是“高频”的,所以做了针对性的优化
2.7 zrem,zremrangebyrank,zremrangebyscore
zrem作用是删除指定的member,时间复杂度尾O(logN * M),N是整个zset的元素个数,M是指定的member的个数zremrangebyrank作用是范围式删除,通过在命令后面带上一个范围,对这个范围进行删除,是闭区间zremrangebyscore作用也是范围式删除,上面的是指定下标,这个就是指定score的范围删除
这三个命令结合解释能很快理解和使用,就不进行演示了~
后面两个命令的时间复杂度都是O(logN + M)
2.8 zincrby
zincrby key increment member
作用是对指定member的score进行一个加法的操作,可以通过加负数来实现减法的效果
这个命令的效果和zadd的INCR选项效果是一样的
2.9 zinterstore,zunionstore
在学习set类型的时候,我们直到集合操作还有交集,并集,差集,对应的命令是sinter,zunion,zdiff,那么zset有序集合有没有呢?有是有,因为这几个命令是从Redis 6.2 版本才开始支持的,咱们现在是5版本,暂时不涉及
暂时zset还是提供了两个命令求集合间操作的:
zinterstore destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
zunionstore destination numkeys key [key ...] [WEIGHTS weight [weight ...]] [AGGREGATE SUM|MIN|MAX]
zinterstore作用是求交集,结构保存到另一个key中zunionstore作用是求并集,结构保存到另一个key中
下面解释下选项:
destination:最后的结果存储到哪个key对应的zset中numkeys:就是一个整数,描述了后续有几个key参与集合间运算,加入这个的原因是因为后面还有其他的选项,Redis解析命令的时候,需要知道有多少个key参与运算,避免选项和key混淆(此处的设定很像HTTP协议报头的“Content-Length”,描述了正文的长度,避免了“粘包问题”) weights:权重,咱们这个集合是有序集合,带有分数,所以现在好几个有序集合做操作,它们的地位不一定对等;权重相当于一个系数,会乘以当前的分数,具体使用可以观看后面的截图aggregate:zset求交集时,不仅仅只考虑member,它还有score,如果member相同,score不同,所以需要一个选项来处理score,就三种方式:“SUM求和”,“MIN取小的值”,“MAX取大的值”,通过这三种方式对score合并
zinterstore:
然后我们可以带上权重,可以写成小数:
最后的AGGREGATE的对score三种操作都很简单,这里就不演示了~
zunionstore:求并集和求交集步骤一样:
对于zinterstore的时间复杂度:
N表示输入若干个有序集合里面元素最少的个数K表示有序集合的个数M表示最终结果的有序集合元素的个数
这个东西取决于Redis的源码咋写的,我们暂时不考虑~
表达式太复杂了,我们可以简化以下得到近似值:
首先K不会很多,近似看作1再化简以下,可以认为N和M是接近的(不严谨,只是近似来看),可以化简为O(M) + O(M * logM) ==> O(M * logM)
对于zunionstore的时间复杂度:
除了N变为了:参与运算的zset的个数,其他的和上面一致
三,内部编码
ziplist(压缩列表):当有序集合的元素个数小于 zset-max-ziplist-entries 配置(默认 128 个), 同时每个元素的值都小于 zset-max-ziplist-value 配置(默认 64 字节)时,Redis 会用ziplist 来作 为有序集合的内部实现,ziplist 可以有效减少内存的使用。skiplist(跳表):当 ziplist 条件不满足时,有序集合会使用 skiplist 作为内部实现,因为此时 ziplist 的操作效率会下降。
关于跳表skiplist的结构可以参考下这道题目:LCR 154. 复杂链表的复制 - 力扣(LeetCode)
要详细了解跳表,还是得结合源码来看,这里不做过多讨论
四,应用场景
4.1 排行榜系统
最关键的应用场景就是这个了,比如应用热搜,游戏积分,成绩排行等等。
关键要点就是:用来排行的“分数”是频繁变化的,因此我们就需要在实时变化的环境下高效地更新排行,所以使用zset来实现就非常简单,因为可以高效地修改“分数”,排行顺序也能自动调整(logN)
Thousands(千):1KB
million(百万):1MB
billion(十亿):1GB
对于游戏排行榜之类的,它的前后顺序就非常容易确定,但是有的排行榜就要复杂很多,比如某博热度(浏览量,点赞量,转发量,评论数),但是对于这部分,一般的大公司都有专门的团队来做这块的事情(通过一些人工智能的方式来进行计算),根据每个维度。计算得到综合得分 ==> 热度
总结:zset只是一个选择,不是说非得用zset,有些场景确实可以用到有序集合,但是不方便使用Redis,就可以考虑使用其他方式的有序集合
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。