西安网站建设服务商十强,云存储wordpress,政务网站信息化建设情况汇报,装修设计公司网站排名Redis底层数据结构 一、常见数据结构的底层数据结构1、动态字符串SDS#xff08;Simple Dynamic String#xff09;组成 2、IntSet组成如何保证动态如何确保有序呢? 底层如何查找的呢? 3、Dict(dictionary)3.1组成3.2 扩容3.3 收缩3.4 rehash 4、ZipList连锁更新问题总结特… Redis底层数据结构 一、常见数据结构的底层数据结构1、动态字符串SDSSimple Dynamic String组成 2、IntSet组成如何保证动态如何确保有序呢? 底层如何查找的呢? 3、Dict(dictionary)3.1组成3.2 扩容3.3 收缩3.4 rehash 4、ZipList连锁更新问题总结特性 5、 QuickList5.1 组成5.2 底层源码结合组成示意图理解5.3 特点总结 6、SkipList它和其他传统链表不同1、元素按升序排列也是方便后续的查找2、节点可能包含多个指针跨度不一样加速查找效率跳表的来源特点总结 最后redis的对象redisObject逐层分析1、type2、encoding3、lru最后一次使用时间4、refcount5、ptr指针 二、常见数据结构1、String2、LIST3、Set无序唯一4、ZSetSortedSet5、Hash 一、常见数据结构的底层数据结构
1、动态字符串SDSSimple Dynamic String 组成
字符数组存储数据头部存储字符数量预分配内存SDS类型5个字节已被弃用。 问题来了为什么要这样设计呢为什么不用c语言的字符串呢 回答
1、保证二进制安全 2、无需遍历数组获取长度 其实c语言没有字符串是靠字符数组实现的并且以“ \0 ”作为结束标志但是如果数据中间存在结束字符会导致读取数据不全的问题所以引入len变量来保存字符数量以len作为标准去读取数据同时无需遍历数组获取长度len。3、动态扩容 预分配有啥好处嘛 在操作系统中分配内存需要内核态和用户态的转换该过程十分损耗性能所以当大于1m会分配多1m防止多次分配带来的性能损耗。
2、IntSet
组成
本质是一个动态有序的整数数组。 encoding表示编码方式数组中的数据就按照该编码方式存储。
如何保证动态
问题来了如果数据超过了编码的范围怎么办呢 回答 我们通过编码升级倒叙依次拷贝防止正序覆盖当前数据再添加新元素最后头信息length1并且编码修改为对应的编码类型。
如何确保有序呢? 底层如何查找的呢? 本质就是二分查找找到则不插入返回错误没找到则插入有序的适当位置。
3、Dict(dictionary)
3.1组成
和java中jdk1.7版本的HashMap底层数据结构十分相似由三部分组成hash表数组哈希节点entry、字典Dict 每个Dict有两个hashTable一个用于存储当前数据一个用于rehash后续详细介绍。 每个hashTabledictHT存储entry的指针以及hash表大小和entry个数其中有一个sizemask用于进行hash求索引比如nsizemask等价于n%sizesizemask1运算速率更加快。 当发生hash碰撞的时候就是key运算后索引相同则使用单向链表进行前插法添加新元素。
3.2 扩容 3.3 收缩
hashTable默认size为4怎么收缩都不能低于4。 收缩后的size为大于等于实际entry个数的最小2的n次方5-8
3.4 rehash 因为一次新增的数据太多导致rehash一次性更新到新的hashTable时长太长而影响其他业务性能所以每次执行增删改查的时候才会去更新一个索引的数据直到结束为止。
4、ZipList 为什么不使用相同内存存储entry呢 回答之所以叫压缩列表就是因为去除了链表中的指针一个指针8字节并且每个entry由实际内容决定节省了大批内存空间。 在遍历的时候无需使用链表的指针来获取前一个元素和下一个元素而是根据previous_enrty_length计算前一个entry的起始地址通过自身大小计算下一节点地址。
连锁更新问题 如果这个时候插入一个节点并且长度大于254将会导致pre_enrty_length属性由1字节变成5字节导致后面的该属性全部连锁更新为5字节。 (该情况发生概率很低)
总结特性
可以看成一种连续空间的双向链表 首尾操作简单节点之间不通过指针连接记录上一节点和本节点长度寻址节省内存如果节点数量过多导致链表过长需要逐个遍历查询效率不高增删大数据时可能发生连续更新问题
5、 QuickList
上面说到ZipList的致命缺点空间连续如果数据过多申请效率会变低查询效率也下降如何解决呢
可以通过限制ZipList的长度和entry大小对于大量的数据进行分片多个ZipList存储多个ZipList进行联系引入主角QuickList
5.1 组成
QuickList本质是一个双端链表但是每个节点指向ZipList使得ZipList们联系起来。
config get list-max-ziplist-size config get list-compress-depth 5.2 底层源码结合组成示意图理解 5.3 特点总结
是一个节点为ZipList的双端链表节点采用ZipList解决了传统链表的内存占用问题指针控制了ZipList的大小解决申请效率的问题中间节点可以进一步压缩进一步节省内存空间。
6、SkipList
上面聊了这么多链表其实都没看到怎么去解决快速查找中间节点的问题这里引入的SkipList就优化了链表中元素查找效率。
它和其他传统链表不同1、元素按升序排列也是方便后续的查找
根据score值进行排序
2、节点可能包含多个指针跨度不一样加速查找效率跳表的来源
上源码是个双向链表每个节点值是SDS整个排序考score然后就是前后指针由于增序所以多级指针体现在forword向后跨度不一所以使用数组存储。 示意图
特点总结
双向链表每个节点都含score和ele值节点按score排序score值相同则按 ele字典排序字符串每个节点可包含多级指针1-32之间指针层级越高跨度越大增删修改效率和红黑树 基本一致实现却简单
最后redis的对象redisObject 逐层分析
1、type
就是我们熟悉的5中常见类型string 、hash、list、set和zset4个bit
2、encoding
就是五种类型在数据量不同的情况下不同的编码方式4个bit
3、lru最后一次使用时间
便于统计使用情况用于统计空闲时间。24bit
4、refcount
引用计数器便于淘汰和回收。
5、ptr指针
指向真正的数据。
其实这里就可以发现 如果我们一直使用string类型去存储大量数据会浪费很多对象的头内存我们可以将其使用集合去存储进行内存的优化。
二、常见数据结构
1、String
使用的编码格式有三种 RAW EMBSTR INT
基本的编码方式是raw基于SDS动态字符串存储上限为512mb。如果存储的SDS长度小于等于44字节则采用EMBSTR 编码此时redisobj head和SDS是一段连续空间。申请内存时只需要调用一次内存分配函数设计到内核态和用户态的切换效率更高。如果存储的字符串是整数并且大小在LONG_max范围内则采用INT编码直接使用pre指针位置刚好8字节不需要SDS。
2、LIST
在3.2版本之前Redis采用ZipList和Linklist来实现List当元素小于512并且元素大小小于64字节时采用ZipList编码超过采用Linklist。3.2之后统一使用QuickList来实现。 具体QuickList请看上述中的详解。
3、Set无序唯一
为了查询效率和唯一性set采用HT编码Dict。Dict中的key用来存储元素value统一为null。当存储的数据都是整数的时候并且元素数量不超过set-max-intset-entries时set采用IntSet编码以节省空间。 如图 当元素为{51020}这时候 sadd s1 m1 会将编码方式由intset转为dict。 4、ZSetSortedSet
其中的每一个元素都需要指定一个score值和member值
根据score值排序member值唯一set都是这样的根据member查询score so底层数据结构必须满足 键值存储键唯一可排序dict 满足键值存储和根据key找valueskipList 满足可排序可以存储score和member 其实底层就是综合了他们的优点来满足需求二者都要一共两份数据空间换时间。 示意图 key存ele value存score实现ele找score 但是根据score排序。
大家可以看到当元素少的时候其实性价比不高内存消耗比较大所以 当元素不多的时候底层会采用zipList实现存储。 什么叫不多界限是啥 同时满足以下两个条件一般都是个数内存大小
元素小于128默认可以调节。每个元素小于64字节
学了zipList知道其实他本身不具备 键值存储键唯一可排序三个特点如何实现呢
zipList是连续空间因此score和ele紧挨着一起的两个enrtyele在前。score越小越接近队首按score升序排列。
5、Hash
其实学了zset发现二者很相似只不过hash不需要保证有序所以立马知道其底层就是dict但是当数据量不多则使用zipList。 hash默认是使用zipList编码节省空间相邻两个entry存的就是key 和value。 当数据量大时则转为HTdict编码触发条件有两个
元素数量超过512默认可调节大小超过64字节默认可调节 以上则是Redis底层主要的数据结构。
