Redis 面试题：基本数据类型与底层存储结构
最近在整理有关 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 编码存储
为了兼顾查找与范围查找，有序集合需要同时使用跳跃表与字典
字典可以保证 O(1)复杂度直接根据指定 key 查找成员值
跳跃表可以在 O(logN)的复杂度下完成范围查找，远远优于字典的 O(NlogN)
在底层存储上，针对相同的数据对象以及分值，跳跃表与字典会通过指针进行共享，因此不会产生较多的内存浪费
六、总结
Redis 对外提供的是上述五种数据类型，但是在底层构造这五种数据类型时，底层实际上使用了包括“简单动态字符串”、“链表”、“字典”、“跳跃表”、“整数集合”、“压缩列表”来构造
根据存储数据的类型、长度以及数量，不同存储格式之间可以进行动态转换，有的存储结构体现是查询速度，有的存储接口体现的空间占用
Linux服务器开发qun720209036，欢迎来交流 2020.11.26 加入
专注C/C++ Linux后台服务器开发。
评论