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

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis Set 用了 2 种数据结构来存储,到现在才知道

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) "貂蝉"

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


关注我,提升技术能力


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
7天前
|
XML JSON NoSQL
Redis的常用数据结构之字符串类型
Redis的常用数据结构之字符串类型
15 0
|
9天前
|
存储 缓存 NoSQL
深入解析Redis:一种快速、高效的键值存储系统
**Redis** 是一款高性能的键值存储系统,以其内存数据、高效数据结构、持久化机制和丰富的功能在现代应用中占有一席之地。支持字符串、哈希、列表、集合和有序集合等多种数据结构,适用于缓存、计数、分布式锁和消息队列等场景。安装Redis涉及下载、编译和配置`redis.conf`。基本操作包括键值对的设置与获取,以及哈希、列表、集合和有序集合的操作。高级特性涵盖发布/订阅、事务处理和Lua脚本。优化策略包括选择合适数据结构、配置缓存和使用Pipeline。注意安全、监控和备份策略,以确保系统稳定和数据安全。
53 1
|
14天前
|
存储 消息中间件 NoSQL
Redis数据类型详解:选择合适的数据结构优化你的应用
Redis数据类型详解:选择合适的数据结构优化你的应用
|
20天前
|
存储 SQL Java
bigdata-18-Hive数据结构与存储格式
bigdata-18-Hive数据结构与存储格式
21 0
|
19天前
|
存储 NoSQL 算法
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(二)
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)
34 0
|
18天前
|
存储 C语言
【数据结构】线性表的链式存储结构
【数据结构】线性表的链式存储结构
16 0
|
19天前
|
存储 NoSQL Redis
作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)(三)
作者推荐 |【Redis技术进阶之路】「原理系列开篇」揭秘高效存储模型与数据结构底层实现(SDS)
19 0
|
21天前
|
存储 NoSQL Java
Redis 数据结构操作入门
Redis 数据结构操作入门
15 0
|
10天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
28 0
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现