在C语言中字符串是以空字符结尾的字符数组
在redis中SDS的实现与C语言类似但是没有直接使用C语言的字符串类型 伪代码如下：
SDS {
//字符串长度
int len;
//数组中剩余长度
int free;
//字节数组 用于保存字符串
//结尾为'/0'可以方便找到插入位置
char[] buf[]
}
SDS与C区别
-
C语言字符串获取长度时间复杂度为O(n)SDS直接获取len复杂度为O（1）
-
C语言在扩容或产生缓冲区溢出问题 SDS会先检查空间是否足够如果不足够会进行扩容
| C字符串 | SDS |
|---|---|
| 获取长度复杂度为O（N） | 获取长度复杂度为O(1) |
| API是不安全的，可能会造成缓冲区溢出 | API是安全的，不会造成缓冲区溢出 |
| 修改字符串N次必然执行N次内存分配 | 最多执行N次内存分配 |
| 只能 保存文本数据 | 可以保存文本和二进制数据 |
| 可以只用所有 | 部分使用 |
-
空间预分配策略
- 在进行修改时判断是否足够不够的话 会扩容一倍 如修改之后为10字节 会扩容到10+10+1 字节
- SDS长度大于1MB每次修改会增加1MB+1字节
- 使得增长N次字符串最多增长N次
-
惰性空间释放
- 在SDS缩短时会不会真正的释放空间而是增加free 方便下次增加使用
- 如果需要真正的释放需要调用相关API
