欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

redis数据类型之zset(有序列表)

程序员文章站 2022-03-06 08:13:56
...

常规操作

127.0.0.1:6379> zadd score 95 zj 			#添加 zadd keyname score value
(integer) 1
127.0.0.1:6379> zadd score 90 jj
(integer) 1
127.0.0.1:6379> zadd score 93 ly
(integer) 1
127.0.0.1:6379> zrange score 0 -1    		#按score正序列出,参数区间为排名范围
1) "jj"
2) "ly"
3) "zj"
127.0.0.1:6379> zrevrange score 0 -1		#按score倒序列出,参数区间为排名范围
1) "zj"
2) "ly"
3) "jj"
127.0.0.1:6379> zcard score					#zset元素个数
(integer) 3
127.0.0.1:6379> zscore score jj				#获取相应value的score
"90"
127.0.0.1:6379> zadd score 89.5  wxb
(integer) 1
127.0.0.1:6379> zscore score wxb
"89.5"
127.0.0.1:6379> zrank score ly				#获取相应value的排名
(integer) 2
127.0.0.1:6379> zrangebyscore score  91 95	#根据分值区间遍历zset
1) "ly"
2) "zj"
127.0.0.1:6379> zrangebyscore score -inf 91 withscores		#根据区间(-∞,91)遍历zet,同时返回分值。int 代表无穷大。
1) "wxb"  
2) "89.5"
3) "jj"
4) "90"
127.0.0.1:6379> zrem score wxb				#删除相应value
(integer) 1
127.0.0.1:6379> zrange score 0 -1
1) "jj"
2) "ly"
3) "zj"

内部实现

zset即是一个set(保证内部value的唯一性),又对每个value赋予了一个score(代表value的排序权重)。其内部数据为“跳跃链表”,更具体的来说,zset的数据结构其实为hash+"跳跃链表"来实现的。

typedef struct zset{
     //跳跃表
     zskiplist *zsl;
     //字典
     dict *dice;
} zset;

hash的键保存元素的值,hash的值则保存元素的分值;跳跃表节点的 object 属性保存元素的成员,跳跃表节点的 score 属性保存元素的分值。
这两种数据结构会通过指针来共享相同元素的成员和分值,所以不会产生重复成员和分值,造成内存的浪费。
另外,当zset元素比较小且少时,其内部实现方式为ziplist(压缩表),此时每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员,第二个节点保存元素的分值。并且压缩列表内的集合元素按分值从小到大的顺序进行排列,小的放置在靠近表头的位置,大的放置在靠近表尾的位置。

跳跃链表

跳跃链表主要用于排序,一般的链表能够快速的进行增删,但是定位能力比较弱,跳跃表就是为了将其定位能力提高,这种方式能够将定位的时间复杂度降到O(lg(n))。其原理如下:
redis数据类型之zset(有序列表)
元素,2,5,9,13,21,27,29,30,36,43.红色为其查找27的路径(即搜索路径),并且在实际存储中,2所在内存只有一个并非这里的三个,上图是为了方便理解。这样在定位中就会快速些。其具体的内存结构如下:
redis数据类型之zset(有序列表)
其中每个kv代表每个元素,即k为元素值,v为分值。每个元素的层高不一样。越高的层所包含的元素越少。
随机层数
对于每个新添加的节点,都需要调用一个随机算法给它分配一个合理的层数(此处的合理一般是通过每层被分配上的概率来控制的),如随机算法得到的层数为3,则在该节点有三层,即第一层有该节点,第二层有该节点,第三层也有该节点。
插入过程
首先搜索插入点,在此过程中将得到“搜索路径”,然后创建新节点,再为其分配一个随机层数,最后将“搜索路径”上的节点和这个新节点通过前向后向指针串起来。当随机层数大于最大层数时,更新最大层数。
删除过程
删除过程与插入过程类型,注意最后也应该更新最大层数。
更新过程
更新是指值不变修改分值的情况,此时只需删除原有值再插入新值即可(有时更新分值并不会更改元素的相对位置,此时这么操作其实时更复杂了)。

另外,当值的分值相等时,Redis排序时还会对value进行排序。这是为了避免当所有的分值都相等时,对value的查找退化为O(n)。