万字长文的Redis五种数据结构详解（理论+实战），建议收藏。

前言

Redis是基于c语言编写的开源非关系型内存数据库，可以用作数据库、缓存、消息中间件，这么优秀的东西一定要一点一点的吃透它。

关于Redis的文章之前也写过三篇，阅读量和读者的反映都还可以，其中第一篇是Redis的缓存三大问题[看完这篇Redis缓存三大问题，保你能和面试官互扯。]。

第二篇是Redis的内存管理和淘汰策略[别再问我Redis内存满了该怎么办了]和持久化[面试造飞机系列：面对Redis持久化连环Call，你还顶得住吗？]。

这是关于Redis的第三篇文章，主要讲解Redis的五种数据结构详解，包括这五种的数据结构的底层原理实现。

理论肯定是要用于实践的，因此最重要的还是实战部分，也就是这里还会讲解五种数据结构的应用场景。

话不多说，我们直接进入主题，很多人都知道Redis的五种数据结构包括以下五种：

1.  String：字符串类型
2.  List：列表类型
3.  Set：无序集合类型
4.  ZSet：有序集合类型
5.  Hash：哈希表类型

但是作为一名优秀的程序员可能不能只停留在只会用这五种类型进行crud工作，还是得深入了解这五种数据结构的底层原理。

Redis核心对象

在Redis中有一个「核心的对象」叫做redisObject ，是用来表示所有的key和value的，用redisObject结构体来表示String、Hash、List、Set、ZSet五种数据类型。

redisObject的源代码在redis.h中，使用c语言写的，感兴趣的可以自行查看，关于redisObject我这里画了一张图，表示redisObject的结构如下所示：

闪瞎人的五颜六色图

在redisObject中「type表示属于哪种数据类型，encoding表示该数据的存储方式」，也就是底层的实现的该数据类型的数据结构。因此这篇文章具体介绍的也是encoding对应的部分。

那么encoding中的存储类型又分别表示什么意思呢？具体数据类型所表示的含义，如下图所示：

图片截图出自《Redis设计与实现第二版》

可能看完这图，还是觉得一脸懵。不慌，会进行五种数据结构的详细介绍，这张图只是让你找到每种中数据结构对应的储存类型有哪些，大概脑子里有个印象。

举一个简单的例子，你在Redis中设置一个字符串key 234，然后查看这个字符串的存储类型就会看到为int类型，非整数型的使用的是embstr储存类型，具体操作如下图所示：

String类型

String是Redis最基本的数据类型，上面的简介中也说到Redis是用c语言开发的。但是Redis中的字符串和c语言中的字符串类型却是有明显的区别。

String类型的数据结构存储方式有三种int、raw、embstr。那么这三种存储方式有什么区别呢？

int

Redis中规定假如存储的是「整数型值」，比如set num 123这样的类型，就会使用 int的存储方式进行存储，在redisObject的「ptr属性」中就会保存该值。

SDS

假如存储的「字符串是一个字符串值并且长度大于32个字节」就会使用SDS（simple dynamic string）方式进行存储，并且encoding设置为raw；若是「字符串长度小于等于32个字节」就会将encoding改为embstr来保存字符串。

SDS称为「简单动态字符串」，对于SDS中的定义在Redis的源码中有的三个属性int len、int free、char buf[]。

len保存了字符串的长度，free表示buf数组中未使用的字节数量，buf数组则是保存字符串的每一个字符元素。

因此当你在Redsi中存储一个字符串Hello时，根据Redis的源代码的描述可以画出SDS的形式的redisObject结构图如下图所示：

SDS与c语言字符串对比

Redis使用SDS作为存储字符串的类型肯定是有自己的优势，SDS与c语言的字符串相比，SDS对c语言的字符串做了自己的设计和优化，具体优势有以下几点：

（1）c语言中的字符串并不会记录自己的长度，因此「每次获取字符串的长度都会遍历得到，时间的复杂度是O(n)」，而Redis中获取字符串只要读取len的值就可，时间复杂度变为O(1)。

（2）「c语言」中两个字符串拼接，若是没有分配足够长度的内存空间就「会出现缓冲区溢出的情况」；而「SDS」会先根据len属性判断空间是否满足要求，若是空间不够，就会进行相应的空间扩展，所以「不会出现缓冲区溢出的情况」。

（3）SDS还提供「空间预分配」和「惰性空间释放」两种策略。在为字符串分配空间时，分配的空间比实际要多，这样就能「减少连续的执行字符串增长带来内存重新分配的次数」。

当字符串被缩短的时候，SDS也不会立即回收不适用的空间，而是通过free属性将不使用的空间记录下来，等后面使用的时候再释放。

具体的空间预分配原则是：「当修改字符串后的长度len小于1MB，就会预分配和len一样长度的空间，即len=free；若是len大于1MB，free分配的空间大小就为1MB」。

（4）SDS是二进制安全的，除了可以储存字符串以外还可以储存二进制文件（如图片、音频，视频等文件的二进制数据）；而c语言中的字符串是以空字符串作为结束符，一些图片中含有结束符，因此不是二进制安全的。

为了方便易懂，做了一个c语言的字符串和SDS进行对比的表格，如下所示：

String类型应用
本文转载自网络，原文链接：https://mp.weixin.qq.com/s/F5Uq0V9jWHpvfb94bTmaow
本站部分内容转载于网络，版权归原作者所有，转载之目的在于传播更多优秀技术内容，如有侵权请联系QQ/微信：153890879删除，谢谢！