目录一、题目二、ZSet 简单使用三、ZSet 结构四、跳跃表五、场景案例一、题目 ZSet能用在哪些场景?跳表查找的过程,时间复杂度 二、ZSet 简单使用 举个例子,fruit-price 是一个有序集合键,这个有序
ZSet能用在哪些场景?跳表查找的过程,时间复杂度
举个例子,fruit-price 是一个有序集合键,这个有序集合以水果名为成员,水果价钱为分值,保存了 130 款水果的价钱:
Redis>ZADD fruit-price 5 "banana"
redis>ZADD fruit-price 6.5 "cherry"
redis>ZADD fruit-price 8 "apple"
redis> ZRANGE fruit-price 0 2 WITHSCORES
1) "banana"
2) "5"
3) "cherry"
4) 6.5
5) "apple"
6) "8"
redis> ZCARD fruit-price
(integer)130
ZSet 结构即支持单个元素查询,又支持范围查询,是如何实现的呢?
Redis 中有两种数据结构来支持 ZSet 的功能,一个是字典 dict ,一个是 zskipList; 字典保存着从 member 到 score 的映射,跳跃表按 score 从小到大保存所有集合元素
先看下 ZSet 在代码中的定义:
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
dict 各种编程语言中都有实现。可以保证 O(1) 的时间复杂度; 我们继续看 zskiplist 的定义:
typedef struct zskiplist {
struct zskiplistnode *header, *tail;
unsigned long length;
int level;
} zskiplist;
zskiplist 是 Redis 对 skiplist 做了变种,skiplist 就是我们常说的跳表;
跳跃表的特点
查找过程
举例说明
假设链接包含 1-10,共 10 个元素。我们要找到第 9 个,需要从 header 遍历,共 9 次才能找到:
一次只能比较一个数,最坏的情况下时间复杂度是 O(n),如果我们一次可以比较 2 个元素就好了:
一次查找 2 个的话,我们只找了 5 次就找到了。所以就有了类似下面的结构,在链表上增加一层减少了元素个数的 “链表”:
如果增加两层 “链表”,只查找 3 次就可以找到:
即便是我们找元素 8,也只需要遍历 1 -> 4 -> 7 -> 8,共 4 次查询;
这样查找过程就非常类似于一个二分查找,使得查找的时间复杂度可以降低到 O(log n)
ZskipList 插入过程:
从上面 Skiplist 的创建和插入过程可以看出,每一个节点的层数(level)是随机出来的,而且新插入一个节点不会影响其它节点的层数。 因此,插入操作只需要修改插入节点前后的指针,而不需要对很多节点都进行调整。这就降低了插入操作的复杂度
Redis 初始化的时候,只判断存储的元素长度是否大于 64 个字节。大于 64 个字节选择 Zkiplist,否则 Ziplist。当执行增删改查的方法,根据是 ziplist 还是 zkiplist 选择不同的实现。只需要记住 zset,在两种情况下使用 ziplist:
保存的元素个数不足 128 个;单个元素的大小超过 64 byte;
ziplist 编码的有序集合使用紧挨在一起的压缩列表节点来保存,第一个节点保存 member,第二个保存 score。ziplist 内的集合元素按 score 从小到大排序,score 较小的排在表头位置
为什么采用跳跃表
1、信息统计
假设我们有某个班级所有学生的语文成绩,想统计、查询区间范围、查询单个学生成绩、满足高性能读取这些需求, Redis 的 zset 结构无疑是最好的选择。Redis 提供了丰富的 api。示例
ZADD yuwen 90 s01 89 s03 99 s02 74 s04 97 s05
以 yuwen 为 key 分别存储了 s01 到 s06 共计 6 名学生的分数,我们可以查询任一学生的成绩:
ZSCORE yuwen s03
可以按照排序返回指定区间内的所有元素
ZRANGE yuwen 1 2 withscores
可以访问指定分数区间内的所有元素
ZRANGEBYSCORE yuwen 90 100 withscores
可以统计指定区间内的个数
ZCOUNT yuwen 80 90
2、排行榜
到此这篇关于Redis中ZSet的具体使用的文章就介绍到这了,更多相关Redis ZSet使用内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!
--结束END--
本文标题: Redis中ZSet的具体使用
本文链接: https://www.lsjlt.com/news/33386.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-29
2024-04-28
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0