Redis八种数据结构简介

2024-08-30 00:44

本文主要是介绍Redis八种数据结构简介,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Redis数据结构

Redis新旧版本中一共出现过八种数据结构,分别是SDS、双向链表、压缩列表、整数集合、哈希表、跳表、quicklist、listpack。

SDS

SDS是用于存储Redis中字符串的数据结构,Redis底层使用的语言是C语言,因此字符串也是C语言的字符串。然而C语言字符串存在一些问题。

1.获取长度时间复杂度为O(N),因为C语言中没有预置的字符串数据类型,而是用一个以“/0”结尾的字符数组代替的,所以要获取字符串长度的话就需要遍历整个数组,数组长度越大消耗时间就越多。

2.无法存储二进制数据,因为C语言字符串就是以"/0"结尾的字符数组,所以如果存储二进制数据的话可能会含有/0的内容,会混淆数组结尾的/0。

3.存在缓冲区溢出的风险,因为C语言不像Java等语言有自己的自动内存管理机制(如Java的垃圾回收器),而是依靠程序员手动管理内存,因此字符数组在添加内容时就可能会导致缓冲区溢出的问题。

为了解决这些问题,Redis中的字符串在原来的基础上添加了三个元数据,分别是len、alloc、flags,分别代表长度、空间长度、SDS类型。具体来说,len记录了字符串的长度,这样在获取字符串长度的时候直接从这个字段获取就行,时间复杂度为O(1),而且由于len表明了字符串的长度,因此字符串最后一位就不是必须使用“/0”结尾,所以可以存储二进制数据;

alloc则记录了字符串的空间大小,在修改字符串的时候首先会查看alloc大小是否满足,如果不满足的话会进行扩容(小于1MB翻倍,大于1MB增加1MB),这样就能避免缓冲区溢出的问题;

flags用来表示不用类型的SDS,一共有5种类型,分别是sdshdr5、sdshdr8、sdshdr16、sdshdr32和sdshdr64。这五种类型的区别在于数据结构中的len和alloc成员变量的数据类型不同,因此字符串可以用来存放不同类型的数据而不是只能为原来的字符型。

链表

由于C语言中没有链表这一数据结构,所以Redis自己实现了一个双向链表的数据结构。对于每一个节点来说,拥有前置节点、后置节点、节点值三个属性,而链表在节点的基础上封装了头结点、尾结点、节点复制函数、节点释放函数、节点比较函数、链表节点数量等属性和方法。

对链表的属性和方法中可以看出,该链表对于获取节点的上/下一个节点、头/尾节点、节点数量等操作都非常快,而且链表节点中可以保存不同类型值。

但是也有缺陷,因为链表和数组不同,内存地址并不是连续的,所以不像数组那样可以充分利用CPU缓存加速访问;而且每添加一个节点都需要为其元数据等添加额外的内存,增加了内存的开销。

压缩列表

压缩列表相对于链表来说,内存地址是连续的,和数组一样可以充分地利用CPU缓存,提高了查询的速度,而且会针对不同长度的数据进行相应编码,这种方法能有效地节省内存开销。

在Redis中,List、Hash、Zset等数据类型在包含的元素数量较少的情况下才会使用到压缩列表存储数据。

除此之外,其他和列表不同的是,压缩列表在表头有几个默认字段,分别为zlbytes(列表占用内存的字节数)、zltail(列表尾部的偏移量,可以理解为列表的容量大小)、zllen(列表包含的节点数量)、zlend(列表的结束点)。这些字段能够帮助快速获取列表大小、高效访问尾元素、元素数量等。

压缩列表中的节点也有自己的元数据,分别为prevlen(前一个节点的长度)、encoding(当前节点的数据类型和长度)、data(当前节点的实际数据)。由此可以看出不同节点的空间大小会根据其实际的数据类型进行分配,节省了内存。

连锁更新问题:由于一个节点中有prevlen属性,记录上一个节点的大小,因此当插入节点的时候,如果插入节点的下一个节点中的prevlen长度不足以标明节点的大小的时候那么就需要更新下一个节点的大小,也就是增加其prevlen属性大小,进而也就改变了下一个节点的大小,以此类推也可能改变其他节点。

尽管压缩列表能够通过连续地址和类型分配节省内存,提供一些较为高效的数据操作,但是当其所包含的元素数量过多时,由于是一片连续的内存空间,就可能导致重新分配内存地址,导致性能下降。

哈希表

Redis中的哈希表是一个数组,每个元素指向哈希表节点,哈希表节点中除了值以外还有指向下一个哈希表节点的指针,形成单向链表,因此和Java中的hashmap类似,使用链表的结构存放hash冲突的元素。

不过这里的负载因子算法是哈希表中的节点数/哈希表大小,因此当负载因子大于等于1的时候就需要进行扩容(rehash)操作。

整数集合

当一个Set中只有整数值元素的时候就会使用整数集这个数据结构作为底层实现。

当将一个新元素添加进整数集合的时候并且这个元素的长度大于整数集合中的最大元素长度时就会触发整数集合的升级,一旦升级后就无法降级。由于添加新的元素才触发升级,所以这个机制能够节省内存资源。

跳表

Redis中唯一使用到了跳表的数据类型是Zset(Zset中使用到了跳表+哈希表两种数据结构),跳表这一数据结构能够实现范围查询。

链表查询元素效率很低,而跳表在链表的基础上实现了一种多层结构,简单来说就是按照一定的跨度(两个节点之间的距离)将原来的链表进行了分层,不同的跨度能够实现跳跃式的查询。因此,跳表中存在多级索引,占用的空间较大,但是查询效率得到提升。

quicklist

在Redis3.2后,list数据类型的底层实现由原来的双向链表或压缩列表改为了quicklist,解决了由于压缩列表无法存储大量数据的问题。

quicklist的结构和链表类似,但是将链表的每个元素改为设置一个压缩列表,并且控制每个链表节点中压缩列表的大小,这样就能利用压缩列表的优势同时避免了一个压缩列表存储大量数据的问题。

在quicklist中并不是所有元素都会进行压缩,在两端处有一些数据会频繁地进行操作(像lpush、rpush、lpop、rpop等操作都是直接访问两端节点数据),因此这部分数据可以不用进行压缩,以减少性能损耗,除此之外如果有的压缩列表中只有一个元素,那也不会为之创建一个压缩列表。

quicklist允许对数据进行压缩,原理是如果数据与之前的数据重复,则只会记录重复的位置和重复的长度。

listpack

虽然quicklist降低了连锁更新的概率和造成的影响,但是没有完全避免,因为数据结构中还是用了压缩列表,因此Redis在5.0后设计了一个新的数据结构listpack来替代压缩列表,在listpack中取消了prevlen字段,避免了因为更新而可能需要不断更新相邻节点的prevlen的隐患。

listpack头也有两个属性,分别为listpack总字节数和元素数量,在尾部有结尾标识。

每个listpack节点中有len,encoding,data三个字段,其中encoding定义元素的编码类型,data为实际存放的数据,len则是encoding+data的总长度。所以listpack节点没有记录前一个节点长度,而是只记录当前节点长度,所以向listpack中加入新元素的时候不会影响其他节点,进而避免了连锁更新问题。

由于取消了prevlen字段,listpack无法像压缩列表那样进行双向遍历,但是节省了内存,避免了连锁更新。

这篇关于Redis八种数据结构简介的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119318

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Redis中的常用的五种数据类型详解

《Redis中的常用的五种数据类型详解》:本文主要介绍Redis中的常用的五种数据类型详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis常用的五种数据类型一、字符串(String)简介常用命令应用场景二、哈希(Hash)简介常用命令应用场景三、列表(L

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

Redis中如何实现商品秒杀

《Redis中如何实现商品秒杀》:本文主要介绍Redis中如何实现商品秒杀问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录技术栈功能实现步骤步骤一:准备商品库存数据步骤二:实现商品秒杀步骤三:优化Redis性能技术讲解Redis的List类型Redis的Set

Redis如何实现刷票过滤

《Redis如何实现刷票过滤》:本文主要介绍Redis如何实现刷票过滤问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录引言一、概述二、技术选型三、搭建开发环境四、使用Redis存储数据四、使用SpringBoot开发应用五、 实现同一IP每天刷票不得超过次数六

Redis客户端工具之RedisInsight的下载方式

《Redis客户端工具之RedisInsight的下载方式》RedisInsight是Redis官方提供的图形化客户端工具,下载步骤包括访问Redis官网、选择RedisInsight、下载链接、注册... 目录Redis客户端工具RedisInsight的下载一、点击进入Redis官网二、点击RedisI