redis学习之一SDS

发布于今天 14:41

redis里的SDS数据类型
redis没有直接使用C语言里的字符串表示，而是自己构建名为简单动态字符串(simple dynamic string,SDS)的类型。在使用redis存储键值对时，不管值是什么类型，键的类型都是SDS，如果值是字符串类型时使用的就是SDS。

SDS的定义：

struct sdshdr {
    //记录buf数组中已使用字节的数量，也就是SDS字符串所保存字符串的长度
    int len;
    //记录buf数组中未使用字节的数量
    int free;
    //字节数组，用于保存字符串
    char buf[];
};

这个是在网上找的图，这里buf是char数组，我觉得应该是'R'|'e'|'d'|'i'|'s'|'\0'|才对，因为改不了在这里说明一下。

free属性值为0，表示这个SDS没有分配任何未使用空间。如果这个值不为0，则在'\0'后面则会分配有空的区域，其长度为free的值。
len属性值为5，表示这个SDS保存了一个五字节长的字符串。
buf属性一个char数组，前五个字节分别保存了'R'/'e'/'d'/'i'/'s'，最后一个字节则保存了表示空字符的'\0'。
SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节不计算在SDS的len属性里。

SDS较C语言字符串的优点

常数复杂度获取字符串长度。因为有len属性记录着属性已使用字符串长度，所以在使用STRLEN命令获取长度的时候复杂度为O(1)；而C语言字符串获取的时间复杂度为O(n)。
避免缓冲区溢出。SDS在进行修改或拼接前会检查空间是否满足修改所需长度，如果不够会进行扩容；而C语言没有长度检查会有溢出的可能。
减少内存重分配次数。C语言在在进行字符串的增长或缩短操作时，需要对应的进行内存申请与释放，不然会有溢出或泄漏的可能；而内存的重分配是一个较耗时的操作，SDS采用了空间预分配与惰性空间释放这两种优化策略。
二进制安全。C语言如果遇到空字符串时会被认为是字符串的结束，这使得其只能保存文本数据而像图片、视频文件等是没办法存储的；而SDS会以处理二进制的方式来处理存放在buf数组里的数据

用表格总结下：

C字符串SDS获取字符串长度时间复杂度为O(n)获取字符串长度时间复杂度为O(1)有缓冲区溢出风险无溢出风险修改字符串N次时一定需要执行多次内存生分配修改字符串N次时最多需要执行多次内存生分配只能存文本文本、图片、视频文件都可以存储

Recommend