您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis Set 用了两种数据结构来存储,到现在才知道

时间:2023-04-27 13:36:52  来源:微信公众号  作者: 码哥字节

Sets 无序集合,他的功能就好像你熟悉的 JAVA 中的 HashSet 一样。集合是通过散列表实现的,所以添加、删除、查找元素的时间复杂度是 O(1)。

1. 是什么

Sets 是 String 类型的无序集合,集合中的元素是唯一的,集合中不会出现重复的数据。

Java 的 HashSet 底层是用 HashMap 实现,Sets 的底层数据结构也是用 Hashtable(散列表)实现,散列表的 key 存的是 Sets 集合元素的 value,散列表的 value 则指向 NULL。

不同的是,当元素内容都是 64 位以内的十进制整数的时候,并且元素个数不超过 set-max-intset-entries 配置的值(默认 512)的时候,会使用更加省内存的 intset(整形数组)来存储。

图片

图2-15

使用场景

当你需要存储多个元素,并且要求不能出现重复数据,无需考虑元素的有序时,就可以使用 Sets 来存储,这样能利用我对单个元素操作 O(1) 时间复杂度带来的性能优势。

并且 Sets 还支持在集合之间做交集、并集、差集操作,比如当你遇到如下场景,需要统计多个集合元素的聚合结果。

  • 统计多个元素的共有数据(交集)。
  • 统计两个集合其中的一个独有元素(差集统计)。
  • 统计多个集合的所有元素(并集统计)。

常见的使用场景。

  1. 社交软件中共同关注,通过交集实现。
  2. 每日新增关注数,只需要对近两天的总注册用户量集合取差集即可。
  3. 打标签:比如微信收藏功能,你可以为自己收藏的每一篇文章打标签,这样你可以快速的找到被添加了某个标签的所有文章。

2. 修炼心法

关于散列表结构我会在专门的章节介绍,先看 intset 结构,结构体定义在源码 intset.h中。

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;
  • length,记录整数集合存储的元素个数,其实就是 contents 数组的长度。
  • contents,真正存储整数集合的数组,是一块连续内存区域。每个元素都是数组的一个数组元素,数组中的元素会按照值的大小从小到大有序排列存储,并且不会有重复元素。
  • encoding,编码格式,决定数组类型,一共有三种不同的值。
  • INTSET_ENC_INT16,表示 contents 数组的存储元素是 int16_t 类型,每 2 字节表示一个整数元素。
  • INTSET_ENC_INT32,表示 contents 数组的存储元素是 int32_t 类型,每 4 字节表示一个元素。
  • INTSET_ENC_INT64,表示 contents 数组的存储元素是 int64_t 类型,每 8 字节表示一个元素。

图片

图2-16

MySQL:“如果在一个 int16_t 类型的整数集合中插入一个 int64_t 类型的值会怎样?”

这个问题问得好,下次可以继续保持。

这种情况会触发整数集合升级,也就是集合的所有元素都会转换成 int64_t 类型,步骤如下。

  1. 根据新元素的类型,以及集合元素的数量,包括新添加的元素在内,计算新的空间大小,对底层数组空间扩容,进行空间重新分配。
  2. 将数组原有的元素都转换成新元素类型,把转换后的元素按照从大到小的顺序放到正确的位置上,需要保证数组元素的有序性。
  3. 修改 encoding 的值,length + 1。

所以每次向整形数组集合添加新元素都可能会引起升级,升级又会对原始数据进行类型转换,时间复杂度是 O(N)。

MySQL:“如果删除刚刚添加的 int64_t 类型元素,会执行降级操作么?”

整形数组不支持降级操作。

MySQL:“Sets 是无序集合,为何存储整形数字的场景下 contents 数组元素需要有序?”

为了查询元素速度,数组有序我就能使用二分法来提高查询效率。insetFind() 函数返回值等于 0 表示集合中没有目标数据,反之 1 存在目标数据。方法的内部会调用 intsetSearch() 函数使用二分法来实现。

static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
    int64_t cur = -1;
    // 省略一些检查代码

    while(max >= min) {
        mid = ((unsigned int)min + (unsigned int)max) >> 1;
        cur = _intsetGet(is,mid);
        if (value > cur) {
            min = mid+1;
        } else if (value < cur) {
            max = mid-1;
        } else {
            break;
        }
    }
 // 修改 pos 指针
    if (value == cur) {
        if (pos) *pos = mid;
        return 1;
    } else {
        if (pos) *pos = min;
        return 0;
    }
}

pos 指针的作用有两个,如果查找到目标值, pos 记录目标值的位置;查找不到目标值,pos 记录的就是这个目标值插入到 intset 的位置。

3. 出招实战:共同好友

三国天下有限公司开发了一个名叫“三国恋”的社交 App,想要实现共同好友功能,这个场景就能使用集合交集来实现。为每个用户创建一个 Sets 集合,账号名作为集合的 key,集合 value 存储该账号的好友。

如下指令构建刘备和曹操的好友集合。

SADD user:刘备 赵子龙 张飞 关羽 貂蝉
SADD user:曹操 貂蝉 夏侯惇 典韦 张辽

想要知道两个人的共同好友,也就是两个集合的交集,只需要使用 SINTERSTORE指令。

SINTERSTORE user:曹刘好友 user:刘备 user:曹操

命令执行后,刘备与曹操两个集合的交集数据就存储到了“user:曹刘好友”集合中。使用 SMEMBERS 查看曹操与刘备的共同好友。

redis> SMEMBERS user:曹刘好友
1) "貂蝉"

好家伙,他们都喜欢貂蝉,你喜不喜欢呢?

 

图片



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  Search: Redis  点击:(12)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  Search: Redis  点击:(18)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  Search: Redis  点击:(40)  评论:(0)  加入收藏
Redis 实现多规则限流的思考与实践
市面上很多介绍redis如何实现限流的,但是大部分都有一个缺点,就是只能实现单一的限流,比如1分钟访问1次或者60分钟访问10次这种,但是如果想一个接口两种规则都需要满足呢,我们的...【详细内容】
2024-01-03  Search: Redis  点击:(109)  评论:(0)  加入收藏
Redis Sentinel的监控和自动化处理Redis节点故障恢复机制
Redis Sentinel是一个分布式的监控系统,它可以监控多个Redis节点的健康状态,并在节点发生故障时自动进行故障转移和恢复。Redis Sentinel通过选举机制选择一个主节点,并将其他...【详细内容】
2023-12-25  Search: Redis  点击:(81)  评论:(0)  加入收藏
用 SpringBoot+Redis 解决海量重复提交问题
前言 一:搭建redis的服务Api 二:自定义注解AutoIdempotent 三:token创建和检验 四:拦截器的配置 五:测试用例 六:总结前言:在实际的开发项目中,一个对外暴露的接口往往会面临很多...【详细内容】
2023-12-20  Search: Redis  点击:(53)  评论:(0)  加入收藏
Redis 除了用作缓存还能干吗?
今天我们来聊聊 Redis 的使用案例。Redis 是一种内存键值数据库。它支持多种数据结构,如 String, Hash, List, Set 和 SortedSet。图片01 缓存Redis 的最常用的用例是缓存,以...【详细内容】
2023-12-11  Search: Redis  点击:(119)  评论:(0)  加入收藏
Redis 也支持全文搜索?这也太强了
在 2021 年我就了解到 RediSearch 这个项目,并已经把它用于我的开源项目 newbee-mall-pro 中。就我的使用体验来说,简单场景下,用来平替 Elasticsearch 的使用场景已经足够。像...【详细内容】
2023-12-11  Search: Redis  点击:(251)  评论:(0)  加入收藏
Redis 如何保证数据不丢失?
前段时间表妹收到了小米秋招补录的面试邀请,一面还算顺利,很快就通过了,但在看二面面试录屏的时候,我发现了一个问题,有一道面试题回答的不是很好,也就是我们今天要聊的这个问题:Re...【详细内容】
2023-11-27  Search: Redis  点击:(159)  评论:(0)  加入收藏
关于 Redis ,这里有你不知道的知识
前言本篇文章不是一篇具体的教程,阿粉打算记录一下自己对Redis的一些思考。说来惭愧,阿粉刚接触Redis的时候只是简单地使用了一下,背了一些面试题,就在简历上写下了Redis这个技...【详细内容】
2023-11-24  Search: Redis  点击:(257)  评论:(0)  加入收藏
▌简易百科推荐
Redis 不再 “开源”,未来采用 SSPLv1 和 RSALv2 许可证
Redis 官方于21日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause...【详细内容】
2024-03-27  dbaplus社群    Tags:Redis   点击:(12)  评论:(0)  加入收藏
Redis“叛逃”开源,得罪了几乎所有人
内存数据库供应商Redis近日在开源界砸下了一块“巨石”。Redis即将转向双许可模式,并实施更为严格的许可条款。官方对此次变更的公告直截了当:从Redis 7.4版本开始,Redis将在Re...【详细内容】
2024-03-25    51CTO  Tags:Redis   点击:(10)  评论:(0)  加入收藏
如何使用 Redis 实现消息队列
Redis不仅是一个强大的内存数据存储系统,它还可以用作一个高效的消息队列。消息队列是应用程序间或应用程序内部进行异步通信的一种方式,它允许数据生产者将消息放入队列中,然...【详细内容】
2024-03-22  后端Q  微信公众号  Tags:Redis   点击:(18)  评论:(0)  加入收藏
Redis不再 “开源”
Redis 官方今日宣布修改开源协议 &mdash;&mdash; 未来所有版本都将使用 “源代码可用” 的许可证 (source-available licenses)。具体来说,Redis 将不再遵循 BSD 3-Clause 开...【详细内容】
2024-03-21  OSC开源社区    Tags:Redis   点击:(9)  评论:(0)  加入收藏
在Redis中如何实现分布式锁的防死锁机制?
在Redis中实现分布式锁是一个常见的需求,可以通过使用Redlock算法来防止死锁。Redlock算法是一种基于多个独立Redis实例的分布式锁实现方案,它通过协调多个Redis实例之间的锁...【详细内容】
2024-02-20  编程技术汇    Tags:Redis   点击:(49)  评论:(0)  加入收藏
手动撸一个 Redis 分布式锁
大家好呀,我是楼仔。今天第一天开工,收拾心情,又要开始好好学习,好好工作了。对于使用 Java 的小伙伴,其实我们完全不用手动撸一个分布式锁,直接使用 Redisson 就行。但是因为这些...【详细内容】
2024-02-19  楼仔  微信公众号  Tags:Redis   点击:(40)  评论:(0)  加入收藏
工作中Redis有哪些好用的运维工具
工作中使用 Redis 时,如果大家公司没有专业运维,可能开发人员就会面临这些运维的工作,包括 Redis 的运行状态监控,数据迁移,主从集群、切片集群的部署和运维等等。本文我就从这三...【详细内容】
2024-02-06  waynaqua    Tags:Redis   点击:(56)  评论:(0)  加入收藏
批量执行Redis命令的四种方式!
前言在我们的印象中Redis命令好像都是一个个单条进行执行的,如果有人问你如何批量执行Redis命令,你能回答的上吗,或者说能答出几种方式呢?最容易想到的是Redis的一些批量命令,例...【详细内容】
2024-01-17  小许code  微信公众号  Tags:Redis命令   点击:(60)  评论:(0)  加入收藏
Redis 实现多规则限流的思考与实践
市面上很多介绍redis如何实现限流的,但是大部分都有一个缺点,就是只能实现单一的限流,比如1分钟访问1次或者60分钟访问10次这种,但是如果想一个接口两种规则都需要满足呢,我们的...【详细内容】
2024-01-03  架构精进之路  微信公众号  Tags:Redis   点击:(109)  评论:(0)  加入收藏
一站式Redis解决方案
Redis是一个高效的内存数据库,它支持包括String、List、Set、SortedSet和Hash等数据类型的存储,在Redis中通常根据数据的key查询其value值,Redis没有模糊条件查询,在面对一些需...【详细内容】
2024-01-01  大雷家吃饭    Tags:Redis   点击:(66)  评论:(0)  加入收藏
站内最新
站内热门
站内头条