Redis-SDS

简单动态字符串（SDS）

SDS定义

​ 在C语言中字符串是以空字符结尾的字符数组

在redis中SDS的实现与C语言类似但是没有直接使用C语言的字符串类型 伪代码如下：

SDS {
	//字符串长度
	int len;
	//数组中剩余长度
	int free;
	//字节数组 用于保存字符串
	//结尾为'/0'可以方便找到插入位置
	char[] buf[]
}

SDS与C区别

• C语言字符串获取长度时间复杂度为O(n)SDS直接获取len复杂度为O（1）

• C语言在扩容或产生缓冲区溢出问题 SDS会先检查空间是否足够如果不足够会进行扩容

C字符串	SDS
获取长度复杂度为O（N）	获取长度复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串N次必然执行N次内存分配	最多执行N次内存分配
只能 保存文本数据	可以保存文本和二进制数据
可以只用所有<string.h>库中的函数	部分使用

SDS的空间分配策略

• 空间预分配策略

  • 在进行修改时判断是否足够不够的话 会扩容一倍 如修改之后为10字节 会扩容到10+10+1 字节
  • SDS长度大于1MB每次修改会增加1MB+1字节
  • 使得增长N次字符串最多增长N次

• 惰性空间释放

  • 在SDS缩短时会不会真正的释放空间而是增加free 方便下次增加使用
  • 如果需要真正的释放需要调用相关API