《Redis设计与实现》学习笔记-简单动态字符串

Redis没有直接使用传统的c字符串,而是自己构建了SDS(simple dynamic string)简单动态字符串。并将SDS作为Redis的默认字符串使用。

SDS与传统C字符串有以下区别

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

C字符串并不记录自身长度,所以要获取一个c字符串长度必须遍历整个字符串并进行计算。所以获取一个字符串长度复杂度为O(N)。

SDS的len属性记录自身长度,所以获取字符串长度的复杂度为O(1).

2、杜绝缓冲区溢出

C字符串不记录自身长度,在没有分配给足够内存时增加字符串长度很容易会造成缓存溢出。

当SDS API需要对SDS进行修改时,API会先检测SDS是否满足修改所需的要求,如果不满足SDS API会自动将SDS的空间扩展至所需大小。

3、减少修改字符串长度时所需的内存重新分配次数。

C字符串每次增加或者减少都会进行一次内存重新分配。其复杂度为O(N)。

当SDS API对SDS进行扩展时不仅会扩展必需的空间,还会为SDS分配额外的未使用空间。(扩展规则:当所需空间小于1MB时,会同时分配与len相同的free空间。当所需空间大于等于1MB时,会分配1MB的未使用空间)

当SDS API 对SDS进行缩短操作时,缩短后空出来的字节,会用free属性记录,等待将来使用。

4、二进制安全

C字符串使用空字符进行结尾,并且字符串中不能包含空字符。否则会认为是字符串的结束。

SDS API会已二进制的方式处理SDS存放在buf数组里的数据。Redis不是用这个数组来保存字符,而是用它来保存一系列二进制数据。

5、兼容部分C字符串函数。

SDS API是二进制安全的,但是依然遵循着已空字符串结尾的管理;所以在SDS需要时可以重用<string.h>函数库。