请选择 进入手机版 | 继续访问电脑版

你不知道的Redis八-Redis底层数据结构解析

[复制链接]
二次方先生 发表于 2021-1-3 12:13:36 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
目次
一、Redis存储的数据的数据结构
二、Redis中键和值得数据结构
1、redis键值的数据结构
2、hash辩论
3、rehash阻塞
4、渐进式rehash
二、压缩列表
三、跳表
四、rdis使用发起
一、Redis存储的数据的数据结构

我们都只到Redis常用的数据结构为String,List,Hash,Set,Sorted Set。但这只是我们在用的时候键值对的体现形式,他们底层真正使用的数据结构为简朴动态字符串,双向链表,压缩列表,哈希表,调表和整数数组

 
可以看到,String 范例的底层实现只有一种数据结构,也就是简朴动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据范例,都有两种底层实现结构。通常情况下,我们会把这四种范例称为聚集范例,它们的特点是一个键对应了一个聚集的数据
二、Redis中键和值得数据结构

1、redis键值的数据结构

因为redis自己要求获取速度快,那么时间复杂度肯定是O1,为了实现从键到值的快速访问,Redis 使用了一个哈希表来生存所有键值对。数据结构如下

 
redis是由一个全局hash表存储所有键和值得关系。值存的为对象的所在。
2、hash辩论

既然使用hash表,那么就肯定会有hash辩论。Redis 办理哈希辩论的方式,和JAVA中的hash表办理方式一样,也是链式哈希。链式哈希也很容易明白,就是指同一个哈希桶中的多个元素用一个链表来生存,它们之间依次用指针毗连。
 

因此当Key特别大的时候,存在着链式查找的一个时间消耗。特别是当我们存在几千万key的时候,那这个时间消耗也是非常多的
 
3、rehash阻塞

为相识决hash辩论带来的链表长度太长,因此redis引入对hash的rehash利用
rehash 也就是增加现有的哈希桶数量,让逐渐增多的 entry 元素能在更多的桶之间分散生存,淘汰单个桶中的元素数量,从而淘汰单个桶中的辩论。

详细利用
Redis 默认使用了两个全局哈希表:哈希表 1 和哈希表 2。一开始,当你刚插入数据时,默认使用哈希表 1,此时的哈希表 2 并没有被分配空间。随着数据逐步增多,Redis 开始执行 rehash,这个过程分为三步:
1、给哈希表 2 分配更大的空间,比方是当前哈希表 1 巨细的两倍;
2、把哈希表 1 中的数据重新举行打散映射到hash表2中;
3、释放哈希表 1 的空间。
我们就可以从哈希表 1 切换到哈希表 2,用增大的哈希表 2 生存更多数据,而原来的哈希表 1 留作下一次 rehash 扩容备用
这个过程看似简朴,但是第二步涉及大量的数据拷贝,如果一次性把哈希表 1 中的数据都迁移完,会造成 Redis 线程阻塞,无法服务其他请求。此时,Redis 就无法快速访问数据了。
为了制止这个问题,Redis 接纳了渐进式 rehash
4、渐进式rehash

简朴来说就是在第二步拷贝数据时,Redis 仍然正常处置处罚客户端请求,每处置处罚一个请求时,从哈希表 1 中的第一个索引位置开始,顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中;等处置处罚下一个请求时,再顺带拷贝哈希表 1 中的下一个索引位置的 entries。如下图所示:
这样就巧妙地把一次性大量拷贝的开销,分摊到了多次处置处罚请求的过程中,制止了耗时利用,包管了数据的快速访问。
二、压缩列表

之前也说了,聚集范例的底层数据结构主要有 5 种:整数数组、双向链表、哈希表、压缩列表和跳表。此中,哈希表刚才已经讲过,整数数组、双向链表也比力常见。那么我们详细看下压缩列表和跳表

zlbytes:记载压缩列表占用的内存字节数,对压缩列表举行内存重分配大概盘算zlen位置时使用,占用4个字节
Zltail:记载也锁列表未节点隔断压缩列表的起始节点有多少字节,通过这个偏移量,步伐无需便利整个压缩列表就可以确定表尾节点的位置 占用4个字节
Zllen:记载列表包罗的节点数量,占用2个字节
Zllend:记载压缩列表的末了,占用1个字节
entry:压缩列表生存的数据,主要有以下属性


  • prev_len,体现前一个 entry 的长度。prev_len 有两种取值情况:1 字节或 5 字节。取值 1 字节时,体现上一个 entry 的长度小于 254 字节。虽然 1 字节的值能体现的数值范围是 0 到 255,但是压缩列表中 zlend 的取值默认是 255,因此,就默认用 255 体现整个压缩列表的竣事,其他体现长度的地方就不能再用 255 这个值了。所以,当上一个 entry 长度小于 254 字节时,prev_len 取值为 1 字节,否则,就取值为 5 字节。
  • len:体现自身长度,4 字节;
  • encoding:体现编码方式,1 字节;
  • content:生存实际数据。
如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。
三、跳表

有序链表只能逐一查找元素,导致利用起来非常迟钝,于是就出现了跳表。详细来说,跳表在链表的根本上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位。

如果我们使用上图所示的跳跃表,就可以淘汰查找所需时间为O(n/2),因为我们可以先通过每个节点的最上面的指针先举行查找,这样子就能跳过一半的节点。
比如我们想查找50,首先和20比力,大于20之后,在和40举行比力,然后在和70举行比力,发现70大于50,说明查找的点在40和50之间,从这个过程中,我们可以看出,查找的时候跳过了30。
跳跃表实在也是一种通过“空间来调换时间”的一个算法,令链表的每个结点不但记载next结点位置,还可以按照level层级分别记载后继第level个结点。此法使用的就是“先大步查找确定范围,再逐渐缩小逼近”的思想举行的查找。跳跃表在算法效率上很靠近红黑树。
四、Redis数据结构时间复杂度


 
五、Redis使用发起

第一,对于单元素利用,对于redis的使用只管使用单元素利用。这种效率一般都比力高。
第二,范围利用,是指聚集范例中的遍历利用,可以返回聚集中的所有数据,这类利用一般都比力耗时,只管制止
第三,统计利用,是指聚集范例对聚集中所有元素个数的记载,因为这些数据结构自己记载所有元素个数,时间复杂度为O(1)所以效率很高
第四,例外情况,是指某些数据结构的特殊记载,比方压缩列表和双向链表都会记载表头和表尾的偏移量。对于头插和尾插增删元素可以通过偏移量直接定位,所以时间复杂度也是O(1)。实现快速操

来源:https://blog.csdn.net/b379685397/article/details/111904696
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )