redis数据库底层没有直接使用c的字符串表示，而是自己使用名为简单动态字符串(simple dynamic string,SDS)
SDS定义
struct sdshdr{
int len; //记录buf数组中以使用字节的数量，等于SDS所保存字符串的长度
int free; //记录buf数组中未使用字节的数量
char buf[]; //字节数组，用于保存字符串
}
示例
image.png
- free属性值为0，表示sds没有分配任何为使用空间
- len属性为5，表示这个sds保存了一个5个字节长的字符串
- buf属性表示一个char类型的数组，前五个字节保存"Redis"，而最后一个字节保存空字符'\0'
注：SDS遵循空字符结尾的好处是：SDS可以直接重用一部分c字符串函数库的函数，比如直接打印字符串printf
SDS与C字符串的区别
1. 获取字符串长度时间复杂度不同(提高获取字符串长度性能)
- 普通C字符串获取长度需要遍历整个字符串，因此复杂度为O(N)。
- SDS的len属性直接保存字符串的长度，复杂度为O(1)
2. SDS杜绝缓冲区溢出
- C:比如说，拼接字符串函数char *strcat(char *dest,const char *sec)，当dest不足够存放src所有内容时，就会产生缓冲区溢出
- SDS:SDS有自己的空间分配策略，当SDS的API对字符串操作时，API会先检查SDS的空间是否满足操作，不满足的话API会自动将SDS的空间扩展至所需大小，然后才执行操作
3. 减少修改字符串带来的内存重分配次数
- 当C需要修改字符串长度时，我们需要再次对使用内存重新分配，由于内存重新分配设计复杂的算法，并且可能执行系统调用，所以通常是比较耗时的操作
- SDS的空间预分配跟惰性空间释放会对字符串的内存分配次数进行优化
1.空间预分配
- 如果对SDS修改后，SDS的长度(len)<1MB，则程序将分配和len属性同样大小的free空间
- 如果对SDS修改后，SDS的长度(len)>1MB，则程序将分配1MB的free空间
2.惰性空间释放
- 惰性空间释放用于优化SDS缩短的操作，当SDS缩短时，程序不会立即进行内存重新分配，而是用free保存多余出来的字节，方便未来使用
4.二进制安全
- C字符串中的字符除了末尾外，不能包含空字符，否则会被识别成字符串结尾
- SDS可以用来保存二进制数据，所以SDS的API都是二进制安全(binary-safe)的，所有的SDS API 会以处理二进制方式来处理buf的数据。因此数据写入是什么样的，读取出来就是什么样的。
5.兼容部分C字符串函数
- 虽然SDS的API是二进制安全的，但其也遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，为了让保存文本数据的SDS可以重用<string.h>定义的函数
总结
| C字符串 | SDS |
|---|---|
| 获取字符串长度复杂度为O(N) | 获取字符串长度复杂度为O(1) |
| API是不安全的，可能造成缓冲区溢出 | API是安全的，不会成缓冲区溢出 |
| 修改字符串长度N次必然需要执行N次内存重新分配 | 修改字符串长度N次最多需要执行N次内存重新分配 |
| 只能保存文本数据 | 可以保存文本数据和二进制数据 |
| 可以使用所有<string.h>库中的函数 | 可以使用部分<string.h>库中的函数 |
网友评论