redis学习 -- 简单动态字符串
Redis没有使用C语言字符串的形式,通过’\0’作为结尾,而是使用了简单动态字符串(simple dynamic string)。
当Redis使用的字符串不需要修改字符串的内容的时候,可以使用C语言提供的字符串,当需要修改内容的时候就使用的是简单动态字符串。Redis键值对的操作中,都是使用的简单动态字符串的方式。
这里可以把简单动态字符串理解成一个对象,这个对象的底层保存着一个字符串。
SDS定义
在sds.h/sdshdr结构体中定义了SDS的值
struct sdshdr {
int len;
int free;
char buf[];
};
如果我们使用SDS定义一个SDS内容为“Redis”的对象,则组织结构如下图所示
- free属性值为0,表示这个SDS没有分配任何没有使用的空间。
- len属性的值是5,表示这个SDS保存了一个五字节长的字符串。
- buf属性是一个char类型的数组,数组里面保存了字符串的值,并且以’\0’结束。
SDS和C字符串的区别和优势
常数时间复杂度获取字符串长度
C字符串获取字符串长度需要遍历,耗时。
SDS记录了长度,可以在O(1)的时间复杂度获取字符串长度。
杜绝缓冲区溢出
在C语言中使用strcat(dest, src)的时候,用户自身需要保证dest的空间要大于拼接之后的内存空间。但是很多时候由于疏忽导致内存溢出。SDS解决了这个问题,使用SDS的APIsdscat的时候,他会进行检测空间大小是否能够满足拼接之后的字符串大小。如果不能,他会重新开辟一个拼接后的大度的二倍的字符串空间。
减少修改字符串时带来的内存重分配次数
C语言中,使用strcat的时候,用户需要手动开辟空间,然后使用函数进行字符串的拼接。频繁的申请空间是一个耗时的操作。但是Redis是一个数据库,很可能会有频繁的改变数据的操作,所以Redis不能容忍这种问题的出现,于是SDS的结构体中,哟一个free的属性,这个是用来记录未使用的空间的,实现了空间的预分配和惰性空间释放两种优化策略。
-
空间预分配
当使用SDS的一个API的时候,程序不仅会开辟足够容纳数据的空间,还会额外的开辟未使用的空间。
额外的未使用的空间的开辟,由如下的方式进行决定:
如果程序需要使用的SDS的len长度小于1M的话,程序会开辟和len长度一样大小的free空间。
如果修改之后的len长度大于1M的话,程序会分配free为1M的空间。
另外上面的两种方式还会多分配一个自己的空间,用于存放’\0’。
补充一点:只要当需要扩充内存空间的时候,才需要开辟。 -
惰性空间释放
当SDS需要使用API去释放空间的时候,这个时候原有字符串会修改,但是开辟的空间并没有释放掉,而是将字符串向前移动,用free记录未使用的空间大小。
二进制安全
SDS底层通过二进制的方式来保存数据。
Redis不仅可以保存文本数据,还可以保存二进制数据。
即使是文本数据,也是转化成二进制数据保存的。
兼容部分C字符串函数
虽然是通过二进制保存数据,但是为了能够兼容string的使用,保存了字符串的一些特性。
SDS API
SDS主要的API如下表
函数 | 作用 | 时间复杂度 |
---|---|---|
sdsnew | 创建一个包含C字符串的SDS | O(N),N为给定的字符串的长度 |
sdsempty | 创建一个不包含任何内容的空SDS | O(1) |
sdsfree | 释放给定的SDS | O(N),N为被释放的SDS的长度 |
sdslen | 返回SDS的已经使用空间字节数 | O(1),通过读取对象的len值直接获取 |
sdsavail | 返回SDS未使用的空间字节数 | O(1),通过读取对象的free的值获取 |
sdsdup | 创建一个SDS的副本 | O,N是给定的SDS的长度 |
stdclear | 清空SDS保存的字符串内容 | O(1),由于惰性空间释放,只改变了对象的len值 |
stscat | 将给定C字符串拼接都SDS字符串的末尾 | O(N),N为被拼接的字符串的长度 |
sdscatsds | 将给定的SDS拼接到另一个SDS字符串的末尾 | O,N为被拼接的SDS字符串的长度 |
sdscpy | 将给定的C字符串复制到SDS里面,覆盖原有的字符串 | O(N),N为被复制的C字符串的长度 |
sdsgrowzero | 用空字符串将SDS扩展到给定长度 | O(N),N为扩展新增的字节数 |
sdssrange | 保留SDS给定区间的数据,不再全进的数据会被覆盖或者是清除 | O(N),N为被保留数据的字节数 |
sdstrin | 接受一个SDS和一个C字符串作为参数,从SDS左右两端移除所有在C字符串中出现过的字符串 | O(M*N),M为SDS的长度,N为给定C字符串的长度 |
sdscmp | 对比两个SDS字符串是否相同 | O(N),N为两个SDS中较短的那个SDS的长度 |