亲宝软件园·资讯

展开

Redis ZSet使用

北极星小王子 人气:0

一、题目

ZSet能用在哪些场景?跳表查找的过程,时间复杂度

二、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 结构

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、排行榜

加载全部内容

相关教程
猜你喜欢
用户评论