写点什么

Redis 面试题:基本数据类型与底层存储结构

  • 2022 年 3 月 21 日
  • 本文字数:2437 字

    阅读完需:约 8 分钟

最近在整理有关 redis 的相关知识,对于 redis 的基本数据类型以及其底层的存储结构简要的进行汇总和备注(主要为面试用😂

Redis 对外提供的基本数据类型主要为五类,分别是

  • STRING:可以存储字符串、数字

  • LIST:列表,链表的每个节点存储一个字符串对象

  • HASH:包含键值对的无需散列表

  • SET:无序集合,集合中包含的是不重复的集合对象

  • ZSET:有序集合,是有一对一对字符串成员-浮点数分值所构成的有序映射,排序规则由分值大小所决定

以上是我们在使用 Redis 的时候经常见到的五种数数据结构,这五种数据结构在底层存储上又有着千丝万缕的联系;例如字符串对象作为一个最基本的存储对象,其在上午五种数据结构中均有应用,那么具体在 Redis 底层数据结构中是如何构造这五种数据结构的,本文将对底层存储做深入解析。

文章中所描述的数据结构大都基于 2.9 版本,如有描述不对还请留言指正,万分感谢🍻

一、STRING

字符串对象根据保存值的类型、长度不同,可以分为三种存储结构

  • 如果存储的是整数值(可以用 long 表示),则底层通过如下结构进行存储,其中 type 代表当前对象为 STRING 对象,encoding 表示当前对象的编码格式,ptr 的属性保存是真实的值;

举例:

  • 如果存储的是字符串且字符串长度超过 39 字节,则底层通过如下结构进行存储,其中 type 代表当前对象为 STRING 对象,encoding 表示当前对象的编码格式,ptr 为指针指向一个 SDS(shshdr:简单动态字符串对象)来保存具体的值;

举例:

  • 如果存储的是字符串且字符串长度未超过 39 字节,则底层通过如下结构进行存储(需要一块连续的内存空间),其中 type 代表当前对象为 STRING 对象,encoding 表示当前对象的编码格式,ptr 为指针指向一个 SDS(shshdr:简单动态字符串对象)来保存具体的值;

举例:

  • 存储结构差异

  • embstr 需要一块连续的内存空间,因此其效率上比 raw 方式要高

  • emstr 在内存分配以及内存释放时只需要一次接口,而 raw 方式需要两次(因为存在 redisObject 和 shshdr 两个对象)

  • embstr 为只读对象,任何对 embstr 编码对象的修改都会导致对象的编码格式变为 raw

  • int/embstr 编码格式的字符串对象在满足一定条件后会自动转为 raw 编码格式

小编另外还整理了腾讯,阿里,京东等一线大厂面试题及答案整理,因篇幅有限,需要集锦的朋友可以点击 面试题资料 免费获取。

  • 字符串对象常用的命令


二、LIST

列表对象根据存储数据的长度以及存储数据元素个数的不同,可以分为两种存储结构:

  • 如果列表对象保存的所有字符串对象值的长度均未超过 64 字节且列表对象保存元素数量小于 512 个的时候,就采用 ziplist(压缩列表)格式存储

  • 如果列表对象保存的所有字符串对象值的长度有超过 64 字节或者列表对象保存元素数量大于等于 512 个的时候,就采用 linkedlist(双端链表)格式存储

  • 存储结构差异

  • 压缩列表是有一系列特殊编码的连续内存块组成的顺序型数据结构,而双端链表则不需要连续的内存块

  • 压缩列表的每个节点是由三部分组成(previous_entry_length/encoding/content),其中 previous_entry_length 是记录前一个节点的长度,以便程序可以通过任意节点的指针计算出前一个节点的起始位置;而双端链表则必须通过头尾节点进行遍历获取

  • 由于 previous_entry_length 属性会随着前一个节点的字节长度不同而存储 1 或者 5 字节,如果新增的头结点长度大于 254 字节,会导致当前头结点的 previous_entry_length(假设当前节点的 previous_entry_length 为 1)的长度无法保存新节点的长度,此时程序会对原头节点进行内存空间重新分配,最坏的情况是新增的头结点导致原列表中的所有元素全部重新分配;而双端链表则不会存在该问题;因此在使用列表对象时要考虑连锁更新的问题;

三、HASH

哈希对象根据存储键值对数据长度以及键值对数量,可以分为两种存储结构:

  • 如果 hash 对象保存的所有键值对的字符串长度小于 64 直接且键值对数量小于 512 个,采用 ziplist(压缩列表)编码存储

key-value 总是以成对的方式存在,存储顺序类似于栈,先添加的键值对会存在列表的前面,后添加的会在列表的尾部;

  • 如果 hash 对象保存的键值对的字符串长度有超过 64 字节或者键值对数量大于等于 512 个,将采用 hashtable 编码存储

  • 上述存储格式会随着存储的内容变化进行编码格式转变,转变只能从 ziplist 转换为 hashtable

四、SET

集合对象根据存储数据的长度以及存储数据元素类型的不同,可以分为两种存储结构:

  • 如果列表对象保存的所有元素均是整数型且保存元素数量不超过 512 个的时候,就采用 intset 编码存储

  • 如果列表对象保存的元素有不是整数型或者保存元素数量超过 512 个的时候,就采用 hashtable 编码存储

  • 上述存储格式会随着存储的内容变化进行编码格式转变,转变只能从 intset 转换为 hashtable

  • 在实际使用过程中,需要提前规划好存储数据内容,尽量不要出现编码格式转换

五、ZSET

有序集合对象根据数据元素数量以元素成员长度,可以分为两种存储结构:

  • 如果有序集合对象保存的元素数量小于 128 个且有序结合对象保存的元素成员的长度都小于 64 字节,就采用 ziplist(压缩列表)编码存储

使用压缩列表的有序结合中每个对象由两个节点构成,第一个节点保存元素的具体值,第二个节点保存元素的分值;默认情况元素是按照分值从小到大排序;

  • 如果有序集合对象保存的元素数量>=128 个或有序结合对象保存的元素成员的长度存在>=64 字节,就采用 skplist(跳跃表【详细请参见:算法-跳跃表原理与实现】)和 dict 编码存储

为了兼顾查找与范围查找,有序集合需要同时使用跳跃表与字典

  1. 字典可以保证 O(1)复杂度直接根据指定 key 查找成员值

  2. 跳跃表可以在 O(logN)的复杂度下完成范围查找,远远优于字典的 O(NlogN)

在底层存储上,针对相同的数据对象以及分值,跳跃表与字典会通过指针进行共享,因此不会产生较多的内存浪费

六、总结

Redis 对外提供的是上述五种数据类型,但是在底层构造这五种数据类型时,底层实际上使用了包括“简单动态字符串”、“链表”、“字典”、“跳跃表”、“整数集合”、“压缩列表”来构造

根据存储数据的类型、长度以及数量,不同存储格式之间可以进行动态转换,有的存储结构体现是查询速度,有的存储接口体现的空间占用


用户头像

Linux服务器开发qun720209036,欢迎来交流 2020.11.26 加入

专注C/C++ Linux后台服务器开发。

评论

发布
暂无评论
Redis面试题:基本数据类型与底层存储结构_redis_Linux服务器开发_InfoQ写作平台