图文主要参考小林Coding的图解redis数据结构
redis为什么快
除了它是内存数据库,使得所有的操作都在内存上进⾏之外,还有⼀个重要因素,它实现的数据结构,使
得我们对数据进⾏增删查改操作时,Redis 能⾼效的处理。
数据库全景图
:::tips
redisDb 结构,表示 Redis 数据库的结构,结构体⾥存放了指向了 dict 结构的指针;
dict 结构,结构体⾥存放了 2 个哈希表,正常情况下都是⽤「哈希表1」,「哈希表2」只有在rehash 的时候才⽤,具体什么是 rehash,我在本⽂的哈希表数据结构会讲;
ditctht 结构,表示哈希表的结构,结构⾥存放了哈希表数组,数组中的每个元素都是指向⼀个哈希表节点结构(dictEntry)的指针;
dictEntry 结构,表示哈希表节点的结构,结构⾥存放了 void * key 和 void * value 指针, *key 指向的是 String 对象,⽽ *value 则可以指向 String 对象,也可以指向集合类型的对象,⽐如 List 对象、Hash 对象、Set 对象和 Zset 对象
:::
Redis 数据结构
并不是指 String(字符串)对象、List(列表)对象、Hash(哈希)对象、Set(集合)对象和 Zset(有序集合)对象,因为这些是 Redis 键值对中值的数据类型,也就是数据的保存形式,这些对象的底层实现的⽅式就⽤到了数据结构。
SDS
简单动态字符串(simple dynamic string,SDS)
C语言字符缺陷
1)结尾位置用“\0”
char * 指针只是指向字符数组的起始位置,⽽字符数组的结尾位置就⽤“\0”表示,意思是指字符串的结束
获取字符串⻓度的函数strlen ,就是通过字符数组中的每⼀个字符,并进⾏计数,等遇到字符为 “\0” 后,就会停⽌遍历
2)字符串里面不能含有“\0”字符
这个限制使得 C 语⾔的字符串只能保存⽂本数据,不能保存像图⽚、⾳频、视频⽂化这样的⼆进制数据
3)strcat会缓冲区溢出
总结
:::tips
1)获取字符串⻓度的时间复杂度为 O(N);
2)字符串的结尾是以 “\0” 字符标识,字符串⾥⾯不能包含有 “\0” 字符,因此不能保存⼆进制数据;
3)字符串操作函数不⾼效且不安全,⽐如有缓冲区溢出的⻛险,有可能会造成程序运⾏终⽌;
:::
SDS的改进
:::tips
1)len,记录了字符串⻓度。这样获取字符串⻓度的时候,只需要返回这个成员变量值就⾏,时间复杂度只需要 O(1)
2)alloc,分配给字符数组的空间⻓度。这样在修改字符串的时候,可以通过 alloc - len 计算出剩余的空间⼤⼩,可以⽤来判断空间是否满⾜修改需求,如果不满⾜的话,就会⾃动将 SDS 的空间扩展⾄执⾏修改所需的⼤⼩,然后才执⾏实际的修改操作,所以使⽤ SDS 既不需要⼿动修改 SDS 的空间⼤⼩,也不会出现前⾯所说的缓冲区溢出的问题。
3)flags,⽤来表示不同类型的 SDS。⼀共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64,后⾯在说明区别之处。
4)buf[],字符数组,⽤来保存实际数据。不仅可以保存字符串,也可以保存⼆进制数据。
:::
总结
- O(1)复杂度获取字符串⻓度:Redis 的 SDS 结构因为加⼊了 len 成员变量,获取字符串⻓度的时候,直接返回成员变量的值就⾏
- ⼆进制安全:有个专⻔的 len 成员变量来记录⻓度,所以可存储包含 “\0” 的数据
- 不会发⽣缓冲区溢出:引⼊了 alloc 和 len 成员变量,当判断出缓冲区⼤⼩不够⽤时,Redis 会⾃动将扩⼤ SDS 的空间⼤⼩,下次在操作 SDS 时,如果 SDS 空间够的话,API 就会直接使⽤「未使⽤空间」,⽽⽆须执⾏内存分配,有效的减少内存分配次数
- 节省内存空间:有个 flags 成员变量,表示的是 SDS 类型。Redis ⼀共设计了 5 种类型,分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。之所以 SDS 设计不同类型的结构体,是为了能灵活保存不同⼤⼩的字符串,从⽽有效节省内存空间。Redis 在编程上还使⽤了专⻔的编译优化来节省内存空间,即在 struct 声明了 attribute ((packed)) ,它的作⽤是:告诉编译器取消结构体在编译过程中的优化对⻬,按照实际占⽤字节数进⾏对⻬
链表
Redis 的 List 对象的底层实现之⼀就是链表
:::tips
链表优点:
-
listNode 链表节点的结构⾥带有 prev 和 next 指针,获取某个节点的前置节点或后置节点的时间复杂度只需O(1),⽽且这两个指针都可以指向 NULL,所以链表是⽆环链表;
-
list 结构因为提供了表头指针 head 和表尾节点 tail,所以获取链表的表头节点和表尾节点的时间复杂度只需O(1);
-
list 结构因为提供了链表节点数量 len,所以获取链表中的节点数量的时间复杂度只需O(1);
-
listNode 链表节使⽤ void* 指针保存节点值,并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数,因此链表节点可以保存各种不同类型的值;
链表缺陷:
- 链表每个节点之间的内存都是不连续的,意味着⽆法很好利⽤ CPU 缓存。能很好利⽤ CPU 缓存的数据结构就是数组,因为数组的内存是连续的,这样就可以充分利⽤ CPU 缓存来加速访问。
- 保存⼀个链表节点的值都需要⼀个链表节点结构头的分配,内存开销较⼤
:::
压缩列表
压缩列表的最⼤特点,就是它被设计成⼀种内存紧凑型的数据结构,占⽤⼀块连续的内存空间,不仅可以利⽤ CPU 缓存,⽽且会针对不同⻓度的数据,进⾏相应编码,这种⽅法可以有效地节省内存开销。
:::tips
压缩列表的缺陷也是有的:
- 不能保存过多的元素,否则查询效率就会降低;
- 新增或修改某个元素时,压缩列表占⽤的内存空间需要重新分配,甚⾄可能引发连锁更新的问题。
因此,Redis 对象(List 对象、Hash 对象、Zset 对象)包含的元素数量较少,或者元素值不⼤的情况才会使⽤压缩列表作为底层数据结构。
:::
:::tips
- zlbytes,记录整个压缩列表占⽤对内存字节数;
- zltail,记录压缩列表「尾部」节点距离起始地址由多少字节,也就是列表尾的偏移量;
- zllen,记录压缩列表包含的节点数量;
- zlend,标记压缩列表的结束点,固定值 0xFF(⼗进制255)。
压缩列表entry节点包含三部分内容:
- prevlen,记录了「前⼀个节点」的⻓度;
- encoding,记录了当前节点实际数据的类型以及⻓度;
- data,记录了当前节点的实际数据;
:::
连锁更新
:::tips
压缩列表新增某个元素或修改某个元素时,如果空间不不够,压缩列表占⽤的内存空间就需要重新分配。⽽当新插⼊的元素较⼤时,可能会导致后续元素的 prevlen 占⽤空间都发⽣变化,从⽽引起「连锁更新」问题,导致每个元素的空间都要重新分配,造成访问压缩列表性能的下降
:::
压缩列表的缺陷
:::tips
连锁更新⼀旦发⽣,就会导致压缩列表占⽤的内存空间要多次重新分配,这就会直接影响到压缩列表的访问性能,,压缩列表只会⽤于保存的节点数量不多的场景.
:::
quicklist
quicklist 是「双向链表 + 压缩列表」组合,因为⼀个 quicklist 就是⼀个链表,⽽链表中的每个元素⼜是⼀个压缩列表
:::tips
压缩列表会有「连锁更新」的⻛险,⼀旦发⽣,会造成性能下降。
quicklist 解决办法,通过控制每个链表节点中的压缩列表的⼤⼩或者元素个数,来规避连锁更新的问题。
因为压缩列表元素越少或越⼩,连锁更新带来的影响就越⼩,从⽽提供了更好的访问性能。
:::
结构设计
:::tips
- 在向 quicklist 添加⼀个元素的时候,不会像普通的链表那样,直接新建⼀个链表节点。⽽是会检查插⼊位置的压缩列表是否能容纳该元素,如果能容纳就直接保存到 quicklistNode 结构⾥的压缩列表,如果不能容纳,才会新建⼀个新的 quicklistNode 结构。
- quicklist 会控制 quicklistNode 结构⾥的压缩列表的⼤⼩或者元素个数,来规避潜在的连锁更新的⻛险,但是这并没有完全解决连锁更新的问题。
:::
listpack
结构设计
:::tips
listpack 头包含两个属性,分别记录了 listpack 总字节数和元素数量,然后 listpack 末尾也有个结尾标
识。图中的 listpack entry 就是 listpack 的节点了。
主要包含三个⽅⾯内容:
- encoding,定义该元素的编码类型,会对不同⻓度的整数和字符串进⾏编码;
- data,实际存放的数据;
- len,encoding+data的总⻓度;
:::
listpack 没有压缩列表中记录前⼀个节点⻓度的字段了,listpack 只记录当前节点的⻓度,当我们向 listpack 加⼊⼀个新元素的时候,不会影响其他节点的⻓度字段的变化,从⽽避免了压缩列表的连锁更新问题。
哈希表
:::tips
哈希表中的每⼀个 key 都是独⼀⽆⼆的,程序可以根据 key 查找到与之关联的 value,或者通过 key 来更新 value,⼜或者根据 key 来删除整个 key-value等等。
在讲压缩列表的时候,提到过 Redis 的 Hash 对象的底层实现之⼀是压缩列表(最新 Redis 代码已将压缩列表替换成 listpack)。Hash 对象的另外⼀个底层实现就是哈希表。
哈希表优点在于,它能以 O(1) 的复杂度快速查询数据,Redis 采⽤了「链式哈希」来解决哈希冲突
:::
rehash过程
:::tips
在正常服务请求阶段,插⼊的数据,都会写⼊到「哈希表 1」,此时的「哈希表 2 」 并没有被分配空间。
随着数据逐步增多,触发了 rehash 操作,这个过程分为三步:
- 给「哈希表 2」 分配空间,⼀般会⽐「哈希表 1」 ⼤ 2 倍;
- 将「哈希表 1 」的数据迁移到「哈希表 2」 中;
- 迁移完成后,「哈希表 1 」的空间会被释放,并把「哈希表 2」 设置为「哈希表 1」,然后在「哈希表 2」 新创建⼀个空⽩的哈希表,为下次 rehash 做准备。
:::
渐进式rehash
为了避免 rehash 在数据迁移过程中,因拷⻉数据的耗时,影响 Redis 性能的情况,所以 Redis 采⽤了渐
进式 rehash,也就是将数据的迁移的⼯作不再是⼀次性迁移完成,⽽是分多次迁移。
rehash 触发条件
rehash 的触发条件跟负载因⼦(load factor)有关系
整数集合
整数集合是 Set 对象的底层实现之⼀,Set 对象只包含整数值元素
:::tips
可以看到,保存元素的容器是⼀个 contents 数组,虽然 contents 被声明为 int8_t 类型的数组,但是实际上 contents 数组并不保存任何 int8_t 类型的元素,contents 数组的真正类型取决于 intset 结构体⾥的encoding 属性的值。⽐如:
- 如果 encoding 属性值为 INTSET_ENC_INT16,那么 contents 就是⼀个 int16_t 类型的数组,数组中每⼀个元素的类型都是 int16_t;
- 如果 encoding 属性值为 INTSET_ENC_INT32,那么 contents 就是⼀个 int32_t 类型的数组,数组中每⼀个元素的类型都是 int32_t;
- 如果 encoding 属性值为 INTSET_ENC_INT64,那么 contents 就是⼀个 int64_t 类型的数组,数组中每⼀个元素的类型都是 int64_t;不同类型的 contents 数组,意味着数组的⼤⼩也会不同。
:::
升级操作
:::tips
当我们将⼀个新元素加⼊到整数集合⾥⾯,如果新元素的类型(int32_t)⽐整数集合现有所有元素的类型(int16_t)都要⻓时,整数集合需要先进⾏升级,也就是按新元素的类型(int32_t)扩展 contents 数组的空间⼤⼩,然后才能将新元素加⼊到整数集合⾥,当然升级的过程中,也要维持整数集合的有序性。
:::
1)假设有3个类型int16_t的元素
2)现在要加入一个新元素65535,需要使用int32_t来保存
contents数组腰扩容,4*32-3-16=80
:::tips
- 如果要让⼀个数组同时保存 int16_t、int32_t、int64_t 类型的元素,最简单做法就是直接使⽤ int64_t 类型的数组。不过这样的话,当如果元素都是 int16_t 类型的,就会造成内存浪费的情况
- 整数集合升级就能避免这种情况,如果⼀直向整数集合添加 int16_t 类型的元素,那么整数集合的底层实现就⼀直是⽤ int16_t 类型的数组,只有在我们要将 int32_t 类型或 int64_t 类型的元素添加到集合时,才会对数组进⾏升级操作
- 因此,整数集合升级的好处是节省内存资源
- 不⽀持降级操作,⼀旦对数组进⾏了升级,就会⼀直保持升级后的状态。⽐如前⾯的升级操作的例⼦,如果删除了 65535 元素,整数集合的数组还是 int32_t 类型的,并不会因此降级为 int16_t 类型
:::
跳表
:::tips
Redis 只有在 Zset 对象的底层实现⽤到了跳表,跳表的优势是能⽀持平O(logN) 复杂度的节点查找
- Zset 对象在使⽤压缩列表作为底层数据结构的时候,zset对象结构的指针会指向压缩列表
- Zset对象在使⽤跳表作为底层数据结构的时候,zset对象结构的指针会指向zset结构(哈希表+跳表)
:::
:::tips
Zset 对象在使⽤跳表作为底层实现的时候,并不是指向跳表数据结构,⽽是指向了zset结构,它包含两个数据结构⼀个是跳表,⼀个是哈希表。这样的好处是既能进⾏⾼效的范围查询,也能进⾏⾼效单点查询。
:::
结构设计
跳表是在链表基础上改进过来的,实现了⼀种「多层」的有序链表
:::tips
图中头节点有 L0~L2 三个头指针,分别指向了不同层级的节点,然后每个层级的节点都通过指针连接起来:
- L0 层级共有 5 个节点,分别是节点1、2、3、4、5;
- L1 层级共有 3 个节点,分别是节点 2、3、5;
- L2 层级只有 1 个节点,也就是节点 3 。
如果我们要在链表中查找节点 4 这个元素,只能从头开始遍历链表,需要查找 4 次,⽽使⽤了跳表后,只需要查找 2 次就能定位到节点 4,因为可以在头节点直接从 L2 层级跳到节点 3,然后再往前遍历找到节点4。
可以看到,这个查找过程就是在多个层级上跳来跳去,最后定位到元素。当数据量很⼤时,跳表的查找复杂度就是 O(logN)。
:::
节点数据结构
:::tips
跨度实际上是为了计算这个节点在跳表中的排位
:::
跳表结构体
:::tips
- 跳表的头尾节点,便于在O(1)时间复杂度内访问跳表的头节点和尾节点;
- 跳表的⻓度,便于在O(1)时间复杂度获取跳表节点的数量;
- 跳表的最⼤层数,便于在O(1)时间复杂度获取跳表中层⾼最⼤的那个节点的层数量;
:::
跳表查询过程
:::tips
查找⼀个跳表节点的过程时,跳表会从头节点的最⾼层开始,逐⼀遍历每⼀层。在遍历某⼀层的跳表节点时,会⽤跳表节点中的 SDS 类型的元素和元素的权重来进⾏判断,共有两个判断条件:
- 如果当前节点的权重「⼩于」要查找的权重时,跳表就会访问该层上的下⼀个节点。
- 如果当前节点的权重「等于」要查找的权重时,并且当前节点的 SDS 类型数据「⼩于」要查找的数据时,跳表就会访问该层上的下⼀个节点。
如果上⾯两个条件都不满⾜,或者下⼀个节点为空时,跳表就会使⽤⽬前遍历到的节点的 level 数组⾥的下⼀层指针,然后沿着下⼀层指针继续查找,这就相当于跳到了下⼀层接着查找。
:::
:::tips
如果要查找「元素:abcd,权重:4」的节点,查找的过程是这样的:文章来源:https://www.toymoban.com/news/detail-788031.html
- 先从头节点的最⾼层开始,L2 指向了「元素:abc,权重:3」节点,这个节点的权重⽐要查找节点的⼩,所以要访问该层上的下⼀个节点;
- 但是该层上的下⼀个节点是空节点,于是就会跳到「元素:abc,权重:3」节点的下⼀层去找,也就是 leve[1];
- 「元素:abc,权重:3」节点的 leve[1] 的下⼀个指针指向了「元素:abcde,权重:4」的节点,然后将其和要查找的节点⽐较。虽然「元素:abcde,权重:4」的节点的权重和要查找的权重相同,但是当前节点的 SDS 类型数据「⼤于」要查找的数据,所以会继续跳到「元素:abc,权重:3」节点的下⼀层去找,也就是 leve[0];
- 「元素:abc,权重:3」节点的 leve[0] 的下⼀个指针指向了「元素:abcd,权重:4」的节点,该节点正是要查找的节点,查询结束。
:::
跳表节点层数设置
:::tips
跳表的相邻两层的节点数量最理想的⽐例是 2:1,查找复杂度可以降低到 O(logN)。
:::
怎么维持?
:::tips
Redis 则采⽤⼀种巧妙的⽅法是,跳表在创建节点的时候,随机⽣成每个节点的层数,并没有严格维持相邻两层的节点数量⽐例为 2 : 1 的情况。
具体的做法是,跳表在创建节点时候,会⽣成范围为[0-1]的⼀个随机数,如果这个随机数⼩于 0.25(相当于概率 25%),那么层数就增加 1 层,然后继续⽣成下⼀个随机数,直到随机数的结果⼤于 0.25 结束,最终确定该节点的层数。
这样的做法,相当于每增加⼀层的概率不超过 25%,层数越⾼,概率越低,层⾼最⼤限制是 64。
:::文章来源地址https://www.toymoban.com/news/detail-788031.html
到了这里,关于Redis数据结构学习笔记的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!