高效的数据结构

redis中的数据结构有2种意思：

• redis本质上是一个hashmap
• redis键值对中的值的数据类型，也就是数据的保存形式，常用的有5种：String(字符串)、List(列表)、Hash(哈希)、Set(集合)、Sorted Set(有序集合)。这几种几种对外暴露的数据结构它们的底层编码方式都是做了不同的优化的

底层数据结构一共有6种分别是简单动态字符串(SDS)、双向链表、压缩列表、哈希表、跳表和整数数组。

为什么要提供这么多的数据结构呢？

• 当然是为了追求速度，不同数据类型使用不同的数据结构速度才得以提升。每种数据类型都有一种或者多种数据结构来支撑
• redis之所以采用不同的数据结构，其实是在性能和内存使用效率之间的平衡。

数据类型和数据结构对应关系

可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。

而 List、Hash、Set 和 Sorted Set 这四种数据类型，都有两种底层实现结构。

通常情况下，我们会把这四种类型称为集合类型，它们的特点是一个键对应了一个集合的数据。

键和值用什么结构组织？

为了实现从键到值的快速访问，Redis 使用了一个哈希表来保存所有键值对。

一个哈希表，其实就是一个数组，数组的每个元素称为一个哈希桶。

一个哈希表是由多个哈希桶组成的，每个哈希桶中保存了键值对数据。

如果值是集合类型的话，作为数组元素的哈希桶怎么来保存呢？

其实，哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。

这也就是说，不管值是 String，还是集合类型，哈希桶中的元素都是指向它们的指针。

在下图中，可以看到，哈希桶中的 entry 元素中保存了key和value指针，分别指向了实际的键和值。

这样一来，即使值是一个集合，也可以通过value指针被查找到。

因为这个哈希表保存了所有的键值对，所以，我也把它称为全局哈希表。哈希表的最大好处很明显，就是让我们可以用 O(1) 的时间复杂度来快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。

你看，这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10 万个键还是 100 万个键，我们只需要一次计算就能找到相应的键。

接下来我们看下String的底层数据结构SDS简单动态字符串的结构。

SDS简单动态字符串的结构

struct  sdsher{
//记录buf中已保存字符的长度
//等于buf[]的长度
int  len;
//记录buf数组中未使用字符的数量
int free;
//字符串数组，用于保存字符串
//等于SDS所保存的字符串的长度len
char buf[];
};

可以把SDS简单动态字符串理解为是对字符串数组的封装,保存了字符串数组中已保存字符的长度和未使用字符的数量。Redis中的简单动态字符串其实是对C语言中的字符串的封装和优化。

不选择C语言中字符串的理由

为什么redis选择了简单动态字符串而不是C语言中的字符串?

理由1:非二进制安全

不是二进制安全的。从定义上来看，二进制安全是一种主要用于字符串操作函数相关的计算机编程术语。一个二进制安全功能（函数），其本质上将操作输入作为原始的、无任何特殊格式意义的数据流。对于每个字符都公平对待，不特殊处理某一个字符。

因为传统C字符串符合ASCII编码，这种编码的操作的特点就是：遇零则止 。

即，当读一个字符串时，只要遇'\0'结尾，就认为到达末尾，就忽略'\0'结尾以后的所有字符。

因此，如果传统字符串保存图片，视频等二进制文件，操作文件时就被截断了。

简单来说C语言使用\0字符来作为字符串结束符是不符合这种二进制安全的规范的。

C语言中的'\0'

C语言没有对String（字符串）这种类型的支持，它处理String时就是以字符数组的形式来存储和操作，而且编译器会为以双引号引起来的字符串内容额外增加一个NULL，记为'\0'，这个\0就是一个真实的存储字节，对应的内容就是[0000 0000]。这就是C语言对字符串的“特殊”处理。

空字符'\0'，也即结束符，对应的二进制为0000 0000(对应十进制为0)，而字符'0'对应的二进制为0011 0000(对应十进制为48)。

几种'\0'的常用用法：

1、字符数组不指定大小初始化

//字符数组str在内存中的实际存放情况为：1 2 3 '\0'
//后面的'\0'是编译器自动加上的，所以在给字符串数组赋初值的时候不用指定数组的长度.
char str[] = {"123"};
char str[] = {'123'};

实际上数组str在内存中的存放情况为: 1 2 3 \0。

以上，编译器会在数组最后自动加上'\0'结束符。

2、字符数组不指定大小，但以单引号括字符

//用单引号赋值时，会丢失'\0'。
char str[] = {'1','2','3'};

所以此时字符串数组无结束标志,打印时后面会出现乱码。

3、字符数组指定大小，长度不够情况

//最后的'\0'会丢失。
char str[3] = {'123'}

由于c语言中以'\0'作为字符串数组的结束标志，虽然'\0'不计入串长，但是要占用内存空间一个字节，所以要留出一个字节存储'\0'。

//最后的'\0'不会丢失。
char str[4] = {'123'}

4、字符数组指定大小，预留'\0'位置

char str[4] = {'1','2','3'}; 编译器会在末尾加上'\0'。

总结： 若希望字符串数组以’\0’结尾，可以写成下面的情况

//字符数组不指定大小，但以双引号括字符,系统自动添加
char str1[] = {"abc"}   
​
//字符数组不指定大小，但以单引号括字符,人工添加'\0'
char str2[] = {'a','b','c','\0'};
char str3[] = {"abc\0"};
​
//字符数组指定大小，留一个空位置给'\0'
char str4[5] = {'a','b','c','d'};
char str5[5] = {"abcd"};

注意：

1.当字符串数组中间出现'\0'时，'\0'后面的字符不再打印，因为'\0'为字符串数组的结束标志。

编译器读取到’\0’时会认为这个字符串数组已经结束。

char str1[] = {"abc\0abc"};
char str2[] = {"abc"};
printf("%s\n",str1);
printf("%s\n",str2);
//str1与str2打印的内容一样
//c语言在线编译
//https://www.bejson.com/runcode/c740/

2.当拷贝字符串数组str到str1时，结尾处的'\0'也一同拷贝

C语言中如果真的要存储\0该怎么存呢？

char str1[] = {"abc\0abc"};
printf("%s",str1);

理由2:修改导致内存重分配:消耗性能

2.频繁修改一个字符串时，会涉及到内存的重分配，比较消耗性能。（Redis中的简单动态字符串会有内存预分配和惰性空间释放）。

如果字符串实际使用长度len<1M，实际分配空间=len长度来存储字符串+1字节存末尾空字符+len长度的预分配空闲内存

如果字符串实际使用长度len>1M，实际分配空间=len长度来存储字符串+1字节存末尾空字符+1M长度的预分配空闲内存

Redis中的简单动态字符串结构，除了包含一个字符数组的属性，还包含数组的长度，数组的实际使用长度等属性，通过增加长度属性，可以保证字符串是二进制安全的，从而可以保存任意类型的数据，例如一张图片，对象序列化后的数据等等。

选择简单字符串的理由

常数复杂度获取字符串长度O(1)

C语言对字符串长度的统计完全来自遍历，从头遍历到末尾，直到发现空字符就停止，以此统计出字符串的长度，这样获取长度的时间复杂度来说是0（n）。

但是这样的计数方式会留下隐患，所以Redis没有采用C的字符串，我后面会提到。

而Redis我在上面已经给大家看过结构了，他自己本身就保存了长度的信息，所以我们获取长度的时间复杂度为O(1)。

说明：SDS为了能够使用部分C字符串函数，遵循了C字符串以空字符结尾的惯例，保存空字符的1字节不计算在SDSlen属性中，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的，可以说空字符对使用者是不可见的！

杜绝缓冲区溢出

C语言由于不记录自身长度，所以又带来一个问题：容易造成缓冲区溢出（buffer overflow）。

假设程序里有两个在内存中紧邻着的C字符串s1和s2，其中s1保存了字符串"Redis"，而s2则保存了字符串"MongoDB"：

如果接下来执行：strcat(s1, " Cluster");

将s1的内容修改为"Redis Cluster"，但粗心的他却忘了在执行strcat之前为s1分配足够的空间，那么在strcat函数执行之后，s1的数据将溢出到s2所在的空间中，导致s2保存的内容被意外地修改。

所以，SDS与C语言字符串不同，由于其记录了长度，所以在API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需要的空间，如果不满足，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行操作，因此避免了缓冲区溢出的问题！

与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API 需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。

示例，SDS的API里面也有一个用于执行拼接操作的sdscat函数，它可以将一个C字符串拼接到给定SDS所保存的字符串的后面，但是在执行拼接操作之前，sdscat会先检查给定SDS的空间是否足够，如果不够的话，sdscat就会先扩展SDS的空间，然后才执行拼接操作。 拼接前：

拼接后

1.减少修改字符串带来的内存重分配次数

上点中说到C字符串可能发生缓冲区溢出，实际上，C字符串在处理增长或者缩短操作时，程序会对这个C字符串的数组进行一次内存重分配操作。

如果程序执行的是拼接操作（append），那么在执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小----如果忘了这一步就会产生缓冲区溢出。

如果程序执行的是截断操作（trim），那么在执行这个操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间----如果忘了这一步就会产生内存泄漏。

而因为内存重分配设计复杂的算法，甚至可能需要执行系统调用，所以它通常是一个比较耗时的操作:对于一般程序而言，对于修改字符串的长度的情况可能不太频繁，所以每次修改都执行一次内存重分配也还是可以接受的。

但是Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，那么显然，如果每次都要执行一次内存重分配，开销简直惊为天人！

所以SDS对于这种情况的处理是：SDS的free属性！

SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联：在SDS中，buf数组的长度不一定就是保存的字符长度加一（这个在之前的结构体中可以看出），数组里可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。

通过free属性（未使用空间），SDS实现了空间预分配和惰性空间释放两种优化策略！

2.空间预分配:减少内存分配

空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间拓展时，程序不仅为SDS分配修改所需要的空间，还会为SDS分配额外的未使用空间，这与cache中的一些算法思想相类似，都是认为最近使用过的数据可能会被再次访问或者修改，于是便给其一个预留的未使用空间！其中，额外分配的未使用空间数量由以下公式决定：

如果对SDS进行修改之后，SDS的长度（也即是len属性的值）小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS的len属性的值等于free属性的值。

举个例子，如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间即free，SDS的buf数组的实际长度将变成13+13+1=27字节（额外的一字节用于保存空字符）。

如果对SDS进行修改之后，SDS的长度将大于等于1MB，那么程序会分配1MB的未使用空间。

举个例子，如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30MB+1MB+1byte。

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。 举个例子，对于下图所示的SDS值s来说，如果我们执行：

sdscat(s, " Cluster");

那么sdscat将执行一次内存重分配操作，将SDS的长度修改为13字节，并将SDS的未使用 空间同样修改为13字节。

在扩展SDS空间之前，SDS API会先检查未使用空间（free）是否足够，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。

如果不采用此预分配策略，当SDS需要连续增长N次时，内存重分配为N次，而应用此策略，则变成了最多N次！

3.惰性空间释放:减少内存分配

当面对字符串缩短操作：如果没有特殊操作，SDS的API需要缩短SDS保存的字符串，那么就需要使用内存重分配来回收多余的字节。

而当我们有了free属性，可以将多余字节调配给free记录下来，并等待将来使用！这也就为将来可能存在的增长操作提供了优化！

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。

举个例子，sdstrim函数接受一个SDS和一个C字符串作为参数，移除SDS中所有在C字符串中出现过的字符。 比如对于下图所示的SDS值s来说，执行：

sdstrim(s, "XY"); 移除SDS字符串中的所有'X'和'Y'

字符串移除后就会变成下图。

执行sdstrim之后的SDS并没有释放多出来的8字节空间，而是将这8字节空间作为未使用空间保留在了SDS里面，并且修改一下free属性。如果将来要对SDS进行增长操作的话，这些未使用空间就可能会派上用场。 通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。

与此同时，SDS也提供了相应的API，让我们可以在有需要时，真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

二进制安全

因为传统C字符串符合ASCII编码，这种编码的操作的特点就是：遇零则止 。

即，当读一个字符串时，只要遇'\0'结尾，就认为到达末尾，就忽略'\0'结尾以后的所有字符。

因此，如果传统字符串保存图片，视频等二进制文件，操作文件时就被截断了。

C语言中如果真的要存储\0该怎么存呢？

char str1[] = {"abc\0abc"};
printf("%s",str1);

而SDS表头的buf被定义为字节数组，因为判断是否到达字符串结尾的依据则是表头的len长度，这意味着它可以存放任何二进制的数据和文本数据，包括’\0’ 。

所以SDS的buf属性被称为字节数组——Redis保存的数据不是“字符”，而是二进制数据。

C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

虽然数据库一般用于保存文本数据，但使用数据库来保存二进制数据的场景也不少见， 因此，为了确保Redis可以适用于各种不同的使用场景，SDS的API都是二进制安全的 （binary-safe），所有SDS的API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符， 而是用它来保存一系列二进制数据。例如下图的数据保存时没有问题的，因为SDS使用len属性判断字符串结束。

二进制安全的SDS使Redis可以保存文本数据以及任意格式的二进制数据。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但它们一样遵循C字符串以空字符结尾的惯例：这些 API总会将SDS保存的数据的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，这是为了让那些保存文本数据的SDS可以重用一部分<string.h>库定义的函数。

参考链接：blog.csdn.net/weixin_4008…

C字符串和SDS对比

C字符串	SDS
获取字符串的复杂度为O(N)	获取字符串的复杂度为O(1)
API是不安全的，可能造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必然需要N次内存重新分配	修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本和二进制数据
可以使用所有<string.h>库函数	可以使用一部分<string.h>库函数

​