面试题46：为什么Redis使用SDS而不是C字符串？

首先我们先介绍一下，什么是SDS。

• SDS（simple dynamic string），简单动态字符串。是由Redis自己创建的一种表示字符串的抽象类型。C字符串是不可被修改的。但是SDS是动态可以被修改的。
• SDS的源码如下所示：

sds.h/sdshdr
 
struct sdshdr {
    // 记录buf数组中已使用的字节长度
    unsigned int len;
    // 记录buf数组中未使用的字节长度
    unsigned int free;
    // java中的char占2个字节（Unicode表示）；C语言中占1个字节（ASCII表示），由于汉字是2个字节，所以无法保存
    char buf[];
};

• 数据结构如下所示：

【说明】最后一位遵循C字符串的空字符（'\0'）结尾的规则，目的是，可以直接使用C字符串的函数。其中len计数不包含‘\0’。

【为什么Redis使用SDS而不是C字符串】

• 首先，C字符串没有记录字符长度，每次都需要遍历，所以复杂度为O(n)。 SDS的len记录了当前字符串的长度，所以获取字符串长度的复杂度为O(1)。
• 其次：C字符串无法杜绝缓冲区溢出。比如执行strcat函数时，如果没有指定足够的内存，那么拼接后会造成缓冲区溢出。 SDS在进行修改时，会先查看空间是否足够，如果不够了，那么它的API会自动的进行空间扩展。 如下所示：

• 第三：C字符串存在内存重分配的性能损耗；SDS采用空间预分配和惰性空间释放来减少性能损耗。
• 第四：C字符串只能保存文本数据，并且字符串里面不能包含空字符，否则就会被误认为是字符串结尾。 SDS则采用二进制来保存数据，并且它使用len属性来判断字符串末尾而不是空字符。所以，它不仅可以保存文本数据，也可以保存任意格式的二进制数据，如：图片、音频、视频、压缩文件这样的二进制数据。

【空间预分配】

• 如果对SDS进行修改后，SDS的长度（len的长度）小于1MB的时候，那么程序分配和len属性同样大小的未使用空间（free）。
• 如果大于1MB，那么程序会分配1MB的未使用空间（free）。
• 如下图所示：

【惰性空间释放】

• 当有缩短SDS字符串操作时，程序并不立即把空闲出来的字节释放掉，而是使用free属性将这个空闲的字节记录起来，等待将来使用。
• 如下图所示：