【Redis-03】Redis数据结构与对象原理 -下篇

2023-12-31 20:42:04

?承接上篇【Redis-02】Redis数据结构与对象原理 -上篇

8. type-字符串string

在这里插入图片描述

8.1 字符串的三种encoding编码(int + embstr + raw)

  • 如果保存的是整型,并且可以用long类型标识(-9223372036854775808到9223372036854775807),encoding取值为 int
  • 如果是浮点数 + 整型(long类型无法表达) + 字符串,且长度 ≤ 44个字节,encoding 取值为 embstr
  • 如果是浮点数 + 整型(long类型无法表达) + 字符串,且长度 > 44个字节,encoding 取值为 raw
    想知道为什么是44个字节吗?点击这里可以查看https://blog.csdn.net/u013099854/article/details/115399466
    在这里插入图片描述
    在这里插入图片描述

8.1.2 embstr 和 raw两种编码

?这两种编码内部封装的都是sds,站在使用者的角度而言,没什么区别;在底层内存分配及部分操作时,还是有一些不同的,主要体现在以下几点:

  1. embstr是用于保存短字符串的优化编码方式,且embstr编码的字符串对象是只读的,对此编码进行任何的写操作,都会导致字符串变为raw的编码方式;raw是用于保存长字符串的编码方式。
  2. embstr在内存分配和内存释放的时候,只需调用一次对应的函数;而raw需要调用两次内存分配和释放的函数来完成对应的过程;
  3. embstr编码的字符串对象所有的数据都是保存在一块连续的内存里,而raw不一定。

?embstr内存连续,如下图:
在这里插入图片描述
?raw内存不连续,如下图:
在这里插入图片描述

8.1.3 编码转换

  • 整数型经过某些操作,比如append、setrange; encoding: int -> raw
  • 整数型涉及到浮点数的操作,比如incrbyfloat; encoding:int -> embstr或raw
  • 短字符串经过某些写的操作,比如append、setrange; encoding : embstr -> raw
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

9 type-集合set

在这里插入图片描述
?redis中,set的类型是借助于intset和dict来实现的,与其他结构一样,在某些条件下,set的编码类型会发生变化。我们来看下,set在哪些情况下使用intset,哪些情况下使用dict。

9.1 类型转换

  • 我们创建一个set,写入 1、 3、 5、 7 这样的整数值时,set的encoding是intset,但是如果我们写入非整数 a,就会变成 dict 类型。
  • 我们创建一个set,写入 1、 3、 5、 7 这样的整数值时,set的encoding是intset,但是如果我们写入的整数 >264-1,就会变成 dict 类型。
  • 当set的元素超过 512 个时,编码类型会从 intset转为 dict,这个值也是在redis.conf的配置文件中定义的。
    在这里插入图片描述
    ?看下面的几个例子:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

9.2 两种类型比较

?我们看下set在不同编码下的数据结构,下图分别是intset 和 dict的实现:
在这里插入图片描述
在这里插入图片描述
?在set较小的时候,使用intset可以节省内存,因为dict要维护两个哈希表,链表指针及其他大量元数据,而intset是一整块连续的内存。但是dict的平均查找效率是高于intset的,dict可以支持O(1)的时间复杂度,而intset是有序的整数集合,可以做二分查找,时间复杂度是O(log n)。

?这里需要说明一点的是,如果set使用dict作为底层实现,key是set的元素值,而 value = null。

10 type-哈希hash

在这里插入图片描述
?hash是我们在redis中存储对象比较理想的数据结构,每个对象的属性正好可以对应hash的每个field。hash的底层数据结构就是基于压缩列表和字典这两种类型实现的。

10.1 encoding的编码转换

?当hash对象可以同时满足下面2个条件时,使用的是ziplist,否则就是dict。

  • 哈希对象保存的所有键值对的键和值字符串长度都 ≤ 64个字节;
  • 哈希对象保存的键值对的数量 ≤ 512个;
    在这里插入图片描述

10.2 举例说明

  • 下面这个案例,aa是64个字节,bb是65个字节

在这里插入图片描述

  • 下面这个案例,numbers1是512个键值对,numbers2是513个键值对
    在这里插入图片描述

11 type-有序列表 sorted set

在这里插入图片描述

? Redis中的sorted set,其实是在ziplist,skiplist和dict的基础上共同构建而来的,在不同的场景下,使用的数据结构是不一样的。决定使用哪种数据结构,涉及到redis.conf中的两个配置参数,分别是 zset-max-ziplist-entries 和 zset-max-ziplist-value。

在这里插入图片描述

  • 如果有序集合中的元素数量≤128(对应的ziplist中entry的个数就是128*2=256个),并且所有元素的长度都≤64个字节的时候,就会使用ziplist作为底层的结构实现。
  • 如果有序集合中的元素数量超过128个,或者某个元素成员对象的长度超过64个字节的时候,就会使用zset的数据结构,而zset的数据结构其实就是由1个dict + 1个 zskiplist结构组成的。

在这里插入图片描述
在这里插入图片描述

11.1 使用 ziplist 的数据结构

?前面我们了解的ziplist是占用了一大块连续的内存,它的数据项都是相邻的。在数据项较少的时候,我们向有序集合中插入一条数据,ziplist上面就会插入两个entry节点,成员对象ele在前,分数score在后面,而且这些元素都是按照分值从小到大进行排序保存的。它的优势就是节省内存开销,支持从前往后或者从后往前的顺序查找。

?如果我们执行了这样一条命令,向学生有序集合中插入分数和姓名,他的类型就是ziplist:

在这里插入图片描述

?那么数据结构就是这样的
在这里插入图片描述

11.2 使用 dict + zskiplist 的数据结构

?在数据量比较多的时候,有序集合使用了 dict + zskiplist两种结构共同来实现。dict用于保存数据与分值之间的对应关系,key=成员对象,value=分值,这也是为什么数据值如果相同,后者会覆盖前者的原因。 而zskiplist用于使用分数来查找数据,也支持范围内的查找。虽然zset同时使用了字段和跳跃表,但是这两种数据结构都会通过指针来共享相同的元素和分值,所以不会产生重复的数据,也不会额外占用内存。

?如果我们执行了这样一条命令,向学生有序集合中插入分数和姓名,他的类型就是skiplist(zset):
在这里插入图片描述

11.3 编码的转换

?我现在分别写入128个元素和129个元素、长度为64和长度为65的元素,看一下他们的encoding的编码类型是什么。

在这里插入图片描述

在这里插入图片描述

?可以看到,上面两种情况的encoding编码值确实发生了变化。

?理论上,有序集合可以单独使用dict或者zskiplist来实现,但是为什么要使用两者结合呢,是因为无论单独使用哪一种,在性能上对比起同时使用两者时性能都会有所下降。下面我们看个例子:

在这里插入图片描述

?如果仅使用zskiplist,现在查找dd的排序:首先我们现在知道的是成员对象,而不是分值,所以就没有办法在O(log n)的时间复杂度下找到对应的节点,只能循环遍历,从头开始找,每循环一个对比一下 ele ?= dd,直到命中为止,时间复杂度就是O(n);

?而现在zset借助了dict,首先根据key=dd找到对应的value,这一步在哈希值冲突较小的前提下时间复杂度是O(1),而找到分值score后,借助于zskiplist的特性在O(log n)的时间复杂度下找到dd这个节点,然后再把沿途的跨度数值加起来,就是dd的排位。

在这里插入图片描述

12 type-列表list

在这里插入图片描述

12.1 编码类型

?redis中列表list就是借助于quicklist来实现的,而且只有这一种编码类型。
在这里插入图片描述

文章来源:https://blog.csdn.net/qq_35850405/article/details/135318841
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。