redis数据结构_字符串

redis没有使用C语言的传统字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作redis的默认字符串表示。

1.1、SDS定义

1
2
3
4
5
6
7
8
struct sdshdr{
//buf 已经占用的空闲的长度
int len;
//buf 中剩下的空闲长度
int free;
//数据空间
char buf[];
};

1.2、SDS与C字符串的区别

1.2.1、获取字符串长度更快

  • C语言是strlen时间复杂度是O(N);
  • redis直接返回len就行了。时间复杂度为O(1);

1.2.2、杜绝缓冲区溢出

  • C语言中的strcat(s1,’abcd’),如果s1字符串长度固定,且已经满了,那么缓冲区就溢出啦。
  • redis可以在链接的时候,先根据free判断能不能装下,不能则就拓展空间。

1.2.3、减少修改字符串带来的内存重新分配次数

  • C语言中字符串数组,每次加长字符串需要重新分配空间,不然缓冲溢出;截取字符串需要free不需要的空间,不然会内存泄漏。
  • redis使用空间预分配,如果需要扩展空间的时候,会使得新增后的空间中(小于1M),使用一半空间,空余一半空间,即len=free;比如修改后len=13,那么free也会=13,SDS的实际buf长度为13+13+1=27字节(额外1字节为’\0’)。
  • redis使用空间预分配,如果redis对SDS修改后len大于1M,那么free会等于1M。比如你的len=20M,那么free=1M,SDS的buf大小为20M+1M+1byte。
  • redis惰性空间释放,如果SDS中字符串缩短,那么redis不会把多余的空间释放,而是保存起来下次使用。比如保存”hello”,那么len=5,free=0,当buf变成保存”hi”,那么len=2,free=3。这样以后buf增长的时候,如果free够的话就不用新增了。
  • redis惰性空间释放,SDS提供相应的API,让我们在有需要的时候真正释放未使用的空间,所以不用担心惰性空间会造成浪费。

1.2.4、二进制安全

  • C字符串中的字符只能符合某种编码(比如ASCII),所以它只能保存文本数据,而不能保存图片、音频、视频、压缩文件这样的数据。
  • SDS是二进制安全的,把所有的数据都当成二进制保存,这样可以保存文本、图片、视频什么的。
  • C字符串以’\0’为结尾,比如hello\0world,这样保存数据读取出来只能读取出hello,因为\0是字符串结尾。
  • SDS读取的时候,是以len为结尾的,只要没有读取到len个字节,就没有结尾。

1.2.5、兼容部分C字符串函数

  • SDS可以使用一部分C的字符串函数,比如strcat。这样可以重用<string.h>而不用重复造车轮。
文章目录
  1. 1. 1.1、SDS定义
  2. 2. 1.2、SDS与C字符串的区别
    1. 2.1. 1.2.1、获取字符串长度更快
    2. 2.2. 1.2.2、杜绝缓冲区溢出
    3. 2.3. 1.2.3、减少修改字符串带来的内存重新分配次数
    4. 2.4. 1.2.4、二进制安全
    5. 2.5. 1.2.5、兼容部分C字符串函数
,