一.SDS定义
SDS的定义:
struct sdshdr{
//记录buf数组中已使用字节的数量,等于SDS中所保存字符串的长度
int len;
//记录buf数组中未使用字节的数量.
int free;
char buf[]; 字节数组.
}
二.SDS与C字符串的区别
1.常数复杂度获取字符串的长度
- C字符串并不记录自身的长度信息,所以为了获取一个C字符串的长度,程序必须遍历整个字符串,对遇到的每个字符进行计数,直到遇到代表字符串结尾的空字符为止.这个操作的复杂度为O(N);通过使用SDS,redis将获取字符串的长度所需的复杂度从O(N)降低到O(1);
2.杜绝缓冲区的溢出
- char *strcat(char *dest,const char *src)
这个函数需要用户保证dest保证有足够的空间容纳src.如果不能保证,则造成缓冲区溢出,SDS需要对SDS进行修改时,API首先会检查SDS的空间是否满足需求,如果不满足,API自动扩充,所以说SDS不用用手动修改SDS的空间大小,就不会出现缓冲区溢出的问题.
3.空间预分配和惰性空间释放
- 对SDS修改之后,SDS的长度(len)的值小于1M，那么程序分配len大小的未使用空间.如果大于1M,每次修改后,程序分配1M的未使用空间.
- 对SDS进行字符串缩短时,只减小len,增加free，不实际释放内存,减少内存的释放次数.
三.二进制安全
- Ｃ字符串除了字符串末尾的空字符之外,中间不能有空字符,所以C字符只能保存文本数据,不能保存图片等数据.SDS是根据len来判断其字符串是否结束,所以能保存任何二进制数据.
- redis兼容C字符串，后面加空字符，是为了使用C库中的字符串操作函数.
四.总结
| C字符串 | SDS |
|---|---|
| 获取字符串长度的复杂度为O(N) | 获取字符串的长度为O(1) |
| API是不安全的,可能会造成缓冲区溢出 | API安全，不会造成缓冲区溢出 |
| 修改字符串长度N次必然执行N此内存分配 | 修改字符串长度N次最多需要执行N次内存重分配 |
| 只能保存文本数据 | 可以保存文本或者二进制数据 |
| 可以使用所有的 < string.h>中的函数 | 可以使用部分< string.h>中的函数 |