redis设计了SDS这一数据结构来表示字符串而不是使用c语言的字符串:字符数组
那么redis为什么要大费周章自己设计字符串呢?
答案是C语言字符串有缺陷
1.获取字符串长度,需要遍历字符数组,时间复杂度是O(N)
2.字符串结尾以"\0"表示,因此字符串内容本身不能包含"\0",因此不能保存二进制数据
3.字符串操作函数不安全,可能会造成缓冲区溢出(这个你一定知道)
我们一一详细介绍这些c语言字符串的缺陷
1.获取字符串长度性能低
由于c语言字符串就是一个以’\0’结尾的字符数组,当你需要一个字符串的长度时,你可能会调用strlen函数,那么这个函数是如何获取字符串的长度的呢?
strlen会遍历整个字符数组,一直遇到’\0’结束
这个操作的时间复杂度是O(N),对于redis来说代价太大了
redis是怎么解决获取字符串长度的问题的?
可以看到,对于redis的字符串SDS,不单有保存字符串的数组空间,还有一些额外的成员
len,记录字符串长度,使得获取字符串长度的时间复杂度降到O(1)
2.缓冲区溢出
举个例⼦,strcat 函数是可以将两个字符串拼接在⼀起。
C 语⾔的字符串是不会记录⾃身的缓冲区⼤⼩的,所以 strcat 函数假定程序员在执⾏这个函数时,已经为 dest 分配了⾜够多的内存,可以容纳 src 字符串中的所有内容,⽽⼀旦这个假定不成⽴,就会发⽣缓冲区 溢出将可能会造成程序运⾏终⽌。
Q:redis是如何解决的?
A:SDS的alloc成员,分配给字符数组的空间⻓度。这样在修改字符串的时候,可以通过 alloc - len 计算出剩余的 空间⼤⼩,可以⽤来判断空间是否满⾜修改需求,如果不满⾜的话,就会⾃动将 SDS 的空间扩展⾄ 执⾏修改所需的⼤⼩,然后才执⾏实际的修改操作,所以使⽤ SDS 既不需要⼿动修改 SDS 的空间⼤ ⼩,也不会出现前⾯所说的缓冲区溢出的问题
3.不能保存二进制数据
这个很好理解,由于’\0’代表字符串结尾,会造成读入终止,这个限制使得 C 语⾔的字符串只能保存⽂本数据,不能保存像图⽚、⾳频、视频⽂化这 样的⼆进制数据