当前位置:   article > 正文

Redis底层数据结构详解_redis数据结构

redis数据结构

Redis底层数据结构详解

我们知道Redis常用的数据结构有五种,String、List、Hash、Set、ZSet,其他的集中数据结构基本上也是用这五种实现的,那么,这五种是Redis提供给你的数据结构,这五种数据结构式怎么实现的,你知道么?底层的底层,你有了解过吗?
在这里插入图片描述

这些是五种数据结构底层使用的数据结构,我们可以看到,有很多底层使用了两种数据结构,比如set在元素较少,且都是数字的情况下会使用整数列表,数据增加会变成哈希表。那么这些底层的数据结构,你又了解多少呢?

这个问题我们先放一下,你有没有一个疑问,这些底层都有着不同的数据结构,那么redis整体的数据结构是什么呢?举个例子,我们现在有一个key对应的value是list类型的,对应的是一个双向链表,那么,我首先要找到这个key,才可以找到这个双向链表噻?

全局哈希表

其实,在redis中,是有一个大的哈希表的,所谓哈希表就是类似的长数组,上面每一个空间,我们都可以看做一个哈希桶。

在这里插入图片描述

每一个key经过Redis内部的hash算法之后都会算出一个位置,这个位置对应一个哈希桶。注意,这个过程可是很快的哈,O(1)的时间复杂度,因为只是计算出一个内存地址,直接寻址就可以了。然后这个key就存到了这个hash桶上面了,这个哈系桶上面保存的是引用,不是真实的对象,就好像哈希桶里面保存的是这个key家的地址(内存地址)。这样就可以用O(1)的时间复杂度完成查找操作了,因为用key去查找value的时候,只需要在经过依次hash能马上找到哈希桶,就能定位到这个键值对的内存地址了。

那么有一个问题,hash算法不能保证所有的key经过算法出来的值都不一样,就是会有哈希冲突的存在,就是两个key放到了同一个桶中,这可怎么办呢?

Redis使用了链表来解决这个问题,就是两个在一个桶中的元素,会用一个next指针连在一起,经过hash之后找到一个键值对之后,对比不是,根据next指针再找下一个比对即可。
在这里插入图片描述

那么当元素越来越多之后,一个哈希桶所对应的链表会越来越长,我们知道链表上的遍历时间复杂度是O(n),会严重影响性能,Redis这种追求快的数据库是绝对不能够容忍的,那么要怎么处理,就是rehash操作。

rehash和渐进式rehash操作

redis会在内部从新建一个长度为原始长度2倍的空哈希表,然后原哈希表上的元素重新rehash到新的哈希表中去,然后我们使用新的哈希表即可。

那么,这样还是有问题,要知道redis中存储的数据可能是成百万上千万的,我们重新rehash一次未免太耗时了吧,因为redis中操作大部分是单线程的,这个过程可能会阻断其他操作很长时间,这是不能忍受的,那么要怎么处理呢。

redis是采用了渐进式rehash的操作,就是会有一个变量,指向第一个哈希桶,然后redis每执行一个添加key,删除key的类似命令,就顺便copy一个哈希桶中的数据到新的哈希表中去,这样溪水长流的操作,不会影响什么性能,直到所有的数据都被重新hash到新的哈希表中。

那么在这个过程中,当然再有写的操作,会直接把数据放到新的哈希表中,保证旧的肯定有copy完的时候,如果这段时间对数据库的操作较少,也没有关系,redis内部也有定时任务,每隔一段时间也会copy一次。

压缩表

压缩表是一种Redis开发用来节省内存的顺序性存储的表结构,我们知道数组这种数据结构,每一个空间的大小都是一样的,这样我们存储较小元素节点的时候就会造成内存的浪费,而压缩链表可以做到每一个元素的节点的大小都不一样。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HUnkffte-1620315354916)(C:\Users\win10\AppData\Roaming\Typora\typora-user-images\image-20210506233133717.png)]

压缩列表实际上类似于一个数组,数组中的每一个元素都对应保存一个数据。和数组不同的是,压缩列表在表头有三个字段 zlbytes、zltail 和 zllen,分别表示列表长度、列表尾的偏移量和列表中的 entry 个数;压缩列表在表尾还有一个 zlend,表示列表结束。

跳表

关于跳表,我写了一篇专门的文章介绍,地址 https://yanghang.blog.csdn.net/article/details/116432604

最后附上Redis底层数据结构的查询时间复杂度

在这里插入图片描述

写在最后,推荐《Redis的设计与实践》这本书,还有蒋德钧的《Redis核心技术与实战》专栏。如果想系统的学习Redis的人,不妨看一下。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/IT小白/article/detail/157409
推荐阅读
相关标签
  

闽ICP备14008679号