Redis简单动态字符串

»Redis

Redis没有使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串(simple dynamic string, SDS)的抽象类型，并将SDS作为Redis的默认字符串表示。

目录：

Redis的定义

struct sdshdr{
    // 记录buf数组中已使用的字节数量
    // 等于SDS所保存字符串长度
    int len;

    // 记录buf数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

SDS的空间分配策略：每当对SDS进行修改的时候，会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，会自动将SDS的空间进行扩充。

SDS特点

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

因为C字符串不记录自身长度信息，所以需要遍历整个字符串才能获得长度。而SDS可以之间查看len属性获得长度信息。

(2) 杜绝缓冲区溢出

使用C会假定用户在执行字符串拼接的时候已经为字符串准备好了空间。而当空间不足的时候就会造成益处。

而SDS会先检查空间是否足够，如果不够则自动扩充。

(3) 减少修改字符串时带来的内存重分配次数

SDS通过未使用空间(即free的长度)来避免修改字符串长度需要经常进行内存重分配的操作。首先，SDS会使用一种空间预分配的机制。当程序对SDS修改并需要扩展的时候，程序不仅会为SDS扩展需要的空间，即修改len的长度，而且还会分配free的长度，当SDS的长度小于1M的时候，预分配的free的长度等于len的长度，当SDS的长度大于1M的时候，预分配的free的长度等于1M。

同时当需要缩短SDS长度的时候，程序并不立即使用内存重分配来回收缩短后多出的字节，而是使用free属性来记录多出的字节，等待将来使用。

(4) 二进制安全

Redis的buf数组保存的是字节而不是字符，从而保证了二进制安全。数据在写入的时候是什么样，读取的时候就是什么样。

(5) 兼容部分C字符串函数

SDS优点

SDS对比C字符串：