《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的空间扩展至所需大小。 继续阅读《Redis设计与实现》学习笔记-简单动态字符串