为了拿捏后端打工人都要会的 Redis 数据结构，我画了 20 张图

绝地灬酷狼 2024-04-08 13:53 30阅读 0赞

**Redis 为什么那么快？**

除了它是内存数据库，使得所有的操作都在内存上进行之外，还有一个重要因素，它实现的数据结构，使得我们对数据进行增删查改操作时，Redis 能高效地处理。

因此，这次我们就来好好聊一下 Redis 数据结构，这个在面试中太常见了。

注意，Redis 数据结构并不是指 tring（字符串）、List（列表）、Hash（哈希）、Set（集合）和 Zset（有序集合），因为这些是 Redis 键值对中值的数据类型，并不是数据结构。这些数据类型的底层实现的方式，才是数据结构。

Redis 底层的数据结构一共有 6 种，如下图右边部分，它和数据类型对应关系也如下图：

![c5ec54d8833e4c23a0d02f12d5f2acdb.png][]

可以看到，有些数据类型可以由两种组成 数据结构实现，比如：

*  List 数据类型底层数据结构由「双向链表」或「压缩表列表」实现；
 *  Hash 数据类型底层数据结构由「压缩列表」或「哈希表」实现；
 *  Set 数据类型底层数据结构由「哈希表」或「整数集合」实现；
 *  Zset 数据类型底层数据结构由「压缩列表」或「跳表」实现；

好了，不多 BB 了，直接发车！

![6d5ceb4dccfc4bb999bdad323f358f14.png][]

## SDS ##

字符串在 Redis 中是很常用的，键值对中的键是字符串，值有时也是字符串。

Redis 使用 C 语言实现的，但是它没有直接使用 C 语言的 char\* 字符数组来实现字符串，而是自己封装了一个名为简单动态字符串（simple dynamic string，SDS） 的数据结构来表示字符串，也就是 Redis 的 String 数据类型的底层数据结构是什么 SDS。

既然 Redis 设计了 SDS 结构来表示字符串，肯定是 C 语言的 char\* 字符数组存在一些缺陷。

要了解这一点，得先来看看 char\* 字符数组的结构。

## C 语言字符串的缺陷 ##

C 语言的字符串其实就是一个字符数组，即数组中每个元素是字符串中的一个字符。

比如，下图就是字符串“xiaolin”的 char\* 字符数组的结构：

![8c36c28b0857418183e13a191242cec1.png][]

没学过 C 语言的同学，可能会好奇为什么最后一个字符是“\\0”？

在 C 语言里，对字符串操作时，char \* 指针只是指向字符数组的起始位置，而**字符数组的结尾位置就用“\\0”表示，意思是指字符串的结束**。

因此，C 语言标准库中字符串的操作函数，就通过判断字符是不是“\\0”，如果不是说明字符串还没结束，可以继续操作，如果是则说明字符串结束了，停止操作。

举个例子，C 语言获取字符串长度的函数 strlen，就是通过字符数组中的每一个字符，并进行计数，等遇到字符为“\\0”后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度。下图显示了 strlen 函数的执行流程：

![687595362e384fa2b6d11765b800c9b2.png][]

很明显，**C 语言获取字符串长度操作的时间复杂度是 O（N）（** ***这是一个可以改进的地方***）

C 语言的字符串用 “\\0” 字符作为结尾标记有个缺陷。假设有个字符串中有个 “\\0” 字符，这时在操作这个字符串时就会提早结束，比如 “xiao\\0lin” 字符串，计算字符串长度的时候则会是 4，如下图：

![4c8b6497dc0349a185ac32ba5fe6c6cb.png][]

还有，除了字符串中不能 “\\0” 字符外，用 char\* 字符串中的字符必须符合某种编码（比如ASCII）。

这些限制使得 C 语言的字符串只能保存文本数据，**不能保存像图片、音频、视频文化这样的二进制数据（** ***这也是一个可以改进的地方*** **）**

C 语言标准库中字符串的操作函数是很不安全的，对程序员很不友好，稍微一不注意，就会导致缓冲区溢出。

举个例子，strcat 函数是可以将两个字符串拼接在一起的。

c //将 src 字符串拼接到 dest 字符串后面 char \*strcat(char *dest, const char* src);

C 语言的字符串是不会记录自身的缓冲区大小的，所以 strcat 函数假定程序员在执行这个函数时，已经为 dest 分配了足够多的内存，可以容纳 src 字符串中的所有内容，而一旦这个假定不成立，就会**发生缓冲区溢出将可能会造成程序运行终止，（** ***这是一个可以改进的地方***）。

而且，strcat 函数和 strlen 函数类似，时间复杂度也很高，也都需要先通过遍历字符串才能得到目标字符串的末尾。然后对于 strcat 函数来说，还要再遍历源字符串才能完成追加，对字符串的操作效率不高。

好了， 通过以上的分析，我们可以得知 C 语言的字符串 不足之处以及可以改进的地方：

*  获取字符串长度的时间复杂度为 O（N）；
 *  字符串的结尾是以 “\\0” 字符标识，而且字符必须符合某种编码（比如ASCII），只能保存文本数据，不能保存二进制数据；
 *  字符串操作函数不高效且不安全，比如可能会发生缓冲区溢出，从而造

[c5ec54d8833e4c23a0d02f12d5f2acdb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/c4491a49fa254b4882c8d12a167b5cf6.png
[6d5ceb4dccfc4bb999bdad323f358f14.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e83824339882497799eb11268b71151b.png
[8c36c28b0857418183e13a191242cec1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/e47f804a159347dcb1263b72b57d78f9.png
[687595362e384fa2b6d11765b800c9b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/d5aaa6dd890140b8a9f8e23294d4dcfc.png
[4c8b6497dc0349a185ac32ba5fe6c6cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/256f325d242b45598cc9a547829d88ae.png