这篇文章主要介绍了Redis中数据结构是什么,具有一定借鉴价值,感兴趣的朋友可以参考下,希望大家阅读完这篇文章之后大有收获,下面让小编带着大家一起了解一下。
在实际开发,Redis
使用会频繁,那么在使用过程中我们该如何正确抉择数据类型呢?哪些场景下适用哪些数据类型。而且在面试中也很常会被面试官问到Redis数据结构方面的问题:
Redis为什么快呢?
为什么查询操作会变慢了?
Redis Hash rehash过程
为什么使用哈希表作为Redis的索引
当我们分析理解了Redis
数据结构,可以为了我们在使用Redis
的时候,正确抉择数据类型使用,提升系统性能。【相关推荐:Redis视频教程】
Redis
底层数据结构Redis
是一个内存键值key-value
数据库,且键值对数据保存在内存中,因此Redis
基于内存的数据操作,其效率高,速度快;
其中,Key
是String
类型,Redis
支持的 value
类型包括了 String
、List
、 Hash
、 Set
、 Sorted Set
、BitMap
等。Redis
能够之所以能够广泛地适用众多的业务场景,基于其多样化类型的value
。
而Redis
的Value
的数据类型是基于为Redis
自定义的对象系统redisObject
实现的,
typedef struct redisObject{ //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现数据结构的指针 void *ptr; ….. }
redisObject
除了记录实际数据,还需要额外的内存空间记录数据长度、空间使用等元数据信息,其中包含了 8 字节的元数据和一个 8 字节指针,指针指向具体数据类型的实际数据所在位置:
其中,指针指向的就是基于Redis
的底层数据结构存储数据的位置,Redis
的底层数据结构:SDS
,双向链表、跳表,哈希表,压缩列表、整数集合实现的。
那么Redis底层数据结构是怎么实现的呢?
我们先来看看Redis
比较简单的SDS
,双向链表,整数集合。
SDS
、双向链表和整数集合SDS
,使用len
字段记录已使用的字节数,将获取字符串长度复杂度降低为O(1),而且SDS
是惰性释放空间的,你free
了空间,系统把数据记录下来下次想用时候可直接使用。不用新申请空间。
整数集合,在内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销,其特点为内存紧凑节省内存空间,查询复杂度为O(1)效率高,其他操作复杂度为O(N);
双向链表, 在内存上可以为非连续、非顺序空间,通过额外的指针开销前驱/后驱指针串联元素之间的顺序。
其特点为节插入/更新数据复杂度为O(1)效率高,查询复杂度为O(N);
Hash
哈希表哈希表,其实类似是一个数组,数组的每个元素称为一个哈希桶,每个哈希桶中保存了键值对数据,且哈希桶中的元素使用dictEntry
结构,
因此,哈希桶元素保存的并不是键值对值本身,而是指向具体值的指针,所以在保存每个键值对的时候会额外空间开销,至少有增加24个字节,特别是Value
为String
的键值对,每一个键值对就需要额外开销24个字节空间。当保存数据小,额外开销比数据还大时,这时为了节省空间,考虑换数据结构。
那来看看全局哈希表全图:
虽然哈希表操作很快,但Redis
数据变大后,就会出现一个潜在的风险:哈希表的冲突问题和 rehash
开销问题,这可以解释为什么哈希表操作变慢了?
当往哈希表中写入更多数据时,哈希冲突是不可避免的问题 , Redis 解决哈希冲突的方式,就是链式哈希,同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接,如图所示:
当哈希冲突也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。
为了解决哈希冲突带了的链过长的问题,进行rehash
操作,增加现有的哈希桶数量,分散单桶元素数量。那么rehash
过程怎么样执行的呢?
Rehash
为了使rehash
操作更高效,使用两个全局哈希表:哈希表 1 和哈希表 2,具体如下:
将哈希表 2 分配更大的空间,
把哈希表 1 中的数据重新映射并拷贝到哈希表 2 中;
释放哈希表 1 的空间
但由于表1和表2在重新映射复制时数据大,如果一次性把哈希表 1 中的数据都迁移完,会造成 Redis
线程阻塞,无法服务其他请求。
为了避免这个问题,保证Redi
s能正常处理客户端请求,Redis
采用了渐进式 rehash
。
每处理一个请求时,从哈希表 1 中依次将索引位置上的所有 entries 拷贝到哈希表 2 中,把一次性大量拷贝的开销,分摊到了多次处理请求的过程中,避免了耗时操作,保证了数据的快速访问。
在理解完Hash
哈希表相关知识点后,看看不常见的压缩列表和跳表。
压缩列表,在数组基础上,在压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。
优点:内存紧凑节省内存空间,内存中分配一块地址连续的空间,数据元素会挨着存放,不需要额外指针带来空间开销;查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。
跳表 ,在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位,如下图所示:
比如查询33
特点:当数据量很大时,跳表的查找复杂度为O(logN)。
综上所述,可以得知底层数据结构的时间复杂度:
数据结构类型 | 时间复杂度 |
---|---|
哈希表 | O(1) |
整数数组 | O(N) |
双向链表 | O(N) |
压缩列表 | O(N) |
跳表 | O(logN) |
Redis
自定义的对象系统类型即为Redis
的Value
的数据类型,Redis
的数据类型是基于底层数据结构实现的,那数据类型有哪些呢?
String
、List
、Hash
、Sorted Set
、Set
比较常见的类型,其与底层数据结构对应关系如下:
数据类型 | 数据结构 |
---|---|
String | SDS(简单动态字符串) |
List | 双向链表 压缩列表 |
Hash | 压缩列表<br/>哈希表 |
Sorted Set | 压缩列表<br/>跳表 |
Set | 哈希表<br/>整数数组 |
数据类型对应特点跟其实现的底层数据结构差不多,性质也是一样的,且
String
,基于SDS实现,适用于简单key-value
存储、setnx key value
实现分布式锁、计数器(原子性)、分布式全局唯一ID。
List
, 按照元素进入List
的顺序进行排序的,遵循FIFO(先进先出)规则,一般使用在 排序统计以及简单的消息队列。
Hash
, 是字符串key
和字符串value
之间的映射,十分适合用来表示一个对象信息 ,特点添加和删除操作复杂度都是O(1)。
Set
,是String
类型元素的无序集合,集合成员是唯一的,这就意味着集合中不能出现重复的数据。 基于哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)。
Sorted Set
, 是Set
的类型的升级, 不同的是每个元素都会关联一个 double 类型的分数,通过分数排序,可以范围查询。
那我们再来看看这些数据类型,Redis Geo
、HyperLogLog
、BitMap
?
Redis Geo
, 将地球看作为近似为球体,基于GeoHash 将二维的经纬度转换成字符串,来实现位置的划分跟指定距离的查询。特点一般使用在跟位置有关的应用。
HyperLogLog
, 是一种概率数据结构,它使用概率算法来统计集合的近似基数 , 错误率大概在0.81%。 当集合元素数量非常多时,它计算基数所需的空间总是固定的,而且还很小,适合使用做 UV 统计。
BitMap
,用一个比特位来映射某个元素的状态, 只有 0 和 1 两种状态,非常典型的二值状态,且其本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型 ,优势大量节省内存空间,可是使用在二值统计场景。
在理解上述知识后,我们接下来讨论一下根据哪些策略选择相对应的应用场景下的Redis
数据类型?
Redis
数据类型策略在实际开发应用中,Redis可以适用于众多的业务场景,但我们需要怎么选择数据类型存储呢?
主要依据就是时间/空间复杂度,在实际的开发中可以考虑以下几个点:
数据量,数据本身大小
集合类型统计模式
支持单点查询/范围查询
特殊使用场景
当数据量比较大,数据本身比较小,使用String
就会使用额外的空间大大增加,因为使用哈希表保存键值对,使用dictEntry
结构保存,会导致保存每个键值对时额外保存dictEntry
的三个指针的开销,这样就会导致数据本身小于额外空间开销,最终会导致存储空间数据大小远大于原本数据存储大小。
可以使用基于整数数组和压缩列表实现了 List
、Hash
和 Sorted Set
,因为整数数组和压缩列表在内存中都是分配一块地址连续的空间,然后把集合中的元素一个接一个地放在这块空间内,非常紧凑,不用再通过额外的指针把元素串接起来,这就避免了额外指针带来的空间开销。而且采用集合类型时,一个 key 就对应一个集合的数据,能保存的数据多了很多,但也只用了一个 dictEntry
,这样就节省了内存。
Redis
集合类型统计模式常见的有:
聚合统计( 交集、差集、并集统计 ): 对多个集合进行聚合计算时,可以选择Set
;
排序统计(要求集合类型能对元素保序): Redis
中List
和 Sorted Set
是有序集合,List
是按照元素进入 List
的顺序进行排序的,Sorted Set
可以根据元素的权重来排序;
二值状态统计( 集合元素的取值就只有 0 和 1 两种 ):Bitmap
本身是用 String
类型作为底层数据结构实现的一种统计二值状态的数据类型 , Bitmap通过 BITOP 按位 与、或、异或的操作后使用 BITCOUNT 统计 1 的个数。
基数统计( 统计一个集合中不重复的元素的个数 ):HyperLogLog
是一种用于统计基数的数据集合类型 ,统计结果是有一定误差的,标准误算率是 0.81% 。需要精确统计结果的话,用 Set 或 Hash 类型。
Set
类型,适用统计用户/好友/关注/粉丝/感兴趣的人集合聚合操作,比如
统计手机APP每天的新增用户数
两个用户的共同好友
Redis
中List
和 Sorted Set
是有序集合,使用应对集合元素排序需求 ,比如
最新评论列表
排行榜
Bitmap
二值状态统计,适用数据量大,且可以使用二值状态表示的统计,比如:
签到打卡,当天用户签到数
用户周活跃
用户在线状态
HyperLogLog
是一种用于统计基数的数据集合类型, 统计一个集合中不重复的元素个数 ,比如
统计网页的 UV , 一个用户一天内的多次访问只能算作一次
Redis
中List
和 Sorted Set
是有序集合支持范围查询,但是Hash
是不支持范围查询的
消息队列,使用Redis
作为消息队列的实现,要消息的基本要求消息保序、处理重复的消息和保证消息可靠性,方案有如下:
基于 List 的消息队列解决方案
基于 Streams 的消息队列解决方案
基于List | 基于Strems | |
---|---|---|
消息保序 | 使用LPUSH/RPOP | 使用XADD/XREAD |
阻塞读取 | 使用BRPOP | 使用XREAD block |
重复消息处理 | 生产者自行实现全局唯一ID | Streams自动生成全局唯一ID |
消息可靠性 | 使用BRPOPLPUSH | 使用PENDING List自动留存消息 |
适用场景 | 消息总量小 | 消息总量大,需要消费组形式读取数据 |
基于位置 LBS 服务,使用Redis
的特定GEO
数据类型实现,GEO
可以记录经纬度形式的地理位置信息,被广泛地应用在 LBS 服务中。 比如:打车软件是怎么基于位置提供服务的。
Redis
之所以那么快,是因为其基于内存的数据操作和使用Hash
哈希表作为索引,其效率高,速度快,而且得益于其底层数据多样化使得其可以适用于众多场景,不同场景中选择合适的数据类型可以提升其查询性能。
感谢你能够认真阅读完这篇文章,希望小编分享的“Redis中数据结构是什么”这篇文章对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,更多相关知识等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。