Redis数据库string SDS大概介绍

Redis string 笔记 简单动态字符串SDS

简介

  • Redis没有使用C语言传统的字符串(以空格结尾的字符串数组)表示,而是自己构建了一种简单动态字符串(SDS)的抽象类型,并将SDS作为Redis的默认字符串表示。
  • Redis中C字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方。当Redis需要的是一个可以修改的字符串值时,Redis会使用SDS来表示字符串值。

SDS定义

  • 在sds.h中每一个sdshdr结构体表示一个SDS值。
1
2
3
4
5
6
7
struct sdshdr
{
uint32_t len; //字符串长度
uint32_t alloc; //分配的buf长度
unsigned char flag; //sds标记 低三位用于标记sds类型 高五位未使用
char buf[]; //保存C字符串 会在末尾处加'\0'
};

SDS和字符串的区别

常数复杂度获取字符串长度

  • C字符串不记录字符串长度,获取字符串长度时需要遍历,时间复杂度O(N)。SDS记录了字符串长度,获取字符串长度时间复杂度为O(1)。

杜绝缓冲区溢出

  • C字符串不记录字符串长度,那么字符串拼接等操作不会检查缓冲区的大小,而SDS会检查缓冲区大小,如果不足会自动扩充,防止缓冲区溢出。C字符串API不安全可能会造成缓冲区溢出,SDS API是安全的。

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

  • C字符串每次增长或缩短都会牵扯到内存的重新分配和释放。SDS通过生成字符串时预分配空间、惰性释放空间对其进行优化。C字符串修改N次字符串长度必然执行N次内存分配,SDS修改字符串长度N次最多执行N次内存分配。

二进制安全

  • C字符串只能保存文本数据,不能保存用空字符分割多个单词的特殊数据结构。SDS保存的是二进制数据。

兼容部分C字符串函数

  • SDS在保存数据时总是多分配一个字节存放’\0’,让保存文本数据的SDS重用一部分C字符串库函数,避免代码重复。