Redis内部数据结构详解之简单动态字符串(sds)

　　SDS[simple dynamic string]是Redis区别于C语言的字符串存储结构，名曰简单动态字符串，redis使用该结构保存字符串，不同于c中的字符串，redis使用该结构来更方便的进行字符串的处理,需要的朋友可以参考下~~

　　详解redis数据结构之sds

　　字符串在redis中使用非常广泛，在redis中，所有的数据都保存在字典（Map）中，而字典的键就是字符串类型，并且对于很大一部分字典值数据也是又字符串组成的。以下是sds的具体存储结构：

　　从图中可以看出，sds的属性有三个：len、free和buf数组。这里len字段是用来保存sds字符串中所包含字符数目的，free字段则是用来保存buf数组中空余的部分的长度的，而buf数组则是实际用来保存字符串的。比如如下结构保存了“HelloWorld！”这个字符串：

　　该结构中存储了字符串的已用字节数和剩余可用字节数，相比于C语言的字符串结构，在动态分配空间和释放空间上提高了效率；和C字符串结构一样SDS也是采用空字符/0作为一个字符串的结尾，这样方便对C语言一些对字符串操作类库的复用，不用重复代码来开发这一环节。

　　redis使用sds结构而不用c字符串保存字符串的原因有如下几点：

　　①常数复杂度获取字符串长度

　　通过读取sds对象的len属性的值我们可以使用O(1)获取sds对象保存的字符串长度，而在c字符串中，我们必须对整个数组进行遍历从而获取字符串的长度，其时间复杂度为O(N)。

　　②杜绝缓冲区溢出

　　在c字符串中，比如char*strcat(char*dest,constchar*src)函数将src连接到dest的末尾，但是c字符串假定dest数组中有足够的空余空间来保存src数组，如果dest数组长度不够就会造成缓冲区溢出；在sds对象中也提供了类似的函数sdssdscat(sdss,constchar*t)和sdssdscatsds(sdss,constsdst)，这两个函数在调用之前会检查目标sds对象s中free属性是否能够保存要连接的字符串的长度，如果不够，就会对目标sds对象扩容，这就保证了sds对象不会造成缓冲区溢出。

　　③减少修改字符串时内存重分配的次数

　　在对sds进行修改的时候，redis可以通过“空间预分配”和“惰性空间释放”来保证后续对sds对象的频繁修改而不会造成sds对象的buf数组经常分配空间；而对于c字符串，每次对其进行修改都需要进行一次空间分配和复制操作。

　　④二进制安全

　　对于c字符串，由于其判断是否结束的标志是从字符串开始到结尾碰到的第一个“\\0”字符，这就限制了c字符串不能保存像图片、音频、视频、压缩文件等二进制保存的内容；而对于sds对象，由于判断其是否结束的标志是其len属性，也就是说无论在len长度内，buf数组中是否包含“\\0”都不影响redis判断其是否结束。

　　上面讲到了sds的空间预分配和惰性空间释放，sds通过这两种操作极大的简化了其对字符串的修改和对空间的分配工作。

　　空间预分配指的是当对一个sds对象进行结构性增加时，比如修改其内容使其增长或者连接另一个字符串到其末尾，sds会预先分配一定的空间以预防未来可能对其进行的修改。如下是redis进行空间预分配的主要代码：

　　从图中可以看出，当要添加的内容比目标sds对象的free属性要短时直接返回并将要添加的内容添加到目标sds对象的buf数组中即可；当要添加的内容比目标sds对象的free属性要长时，就会计算要添加的内容和sds对象的当前长度的和newlen，如果newlen小于SDS_MAX_PREALLOC也即1M的时候，新创建的buf数组的长度为newlen的两倍，如果newlen大于SDS_MAX_PREALLOC的时候，新创建的buf数组的长度为newlen+SDS_MAX_PREALLOC，即只多分配1M的预留空间。空间预分配保证了sds对象的空余位长度至多为扩张之后字符串长度的1倍，这也就保证了后续对sds对象的修改将尽可能少的分配空间。

　　惰性空间释放指的是当对一个sds对象进行缩短操作时，其不会直接将buf数组缩短为目标数组的长度，而是只改变sds对象的len属性的值，数组中多余的部分则保存在free属性中，这样就可以保证后续可能的对该sds对象的增长操作不需要重新分配空间。

　　最后需要进行说明的是，sds对象也和c一样使用“\\0”作为字符串的结尾的原因是redis也是使用c语言编写的，使用“\\0”结尾就可以直接使用部分c函数库中对字符串操作的函数。

　　通过上面对sds对象的说明可以发现，redis对sds对象的处理极大的减少了字符串处理中可能出现的复杂操作，并且大部分操作基本上都可以在极短的时间内完成，这就保证了redis对字符串处理的高速率。

　　小编结语：

　　更多内容尽在课课家教育！