Redis - 简单动态字符串

Dear 丶 2022-12-19 04:59 149阅读 0赞

### 文章目录 ###

*  1. SDS结构
 *  2. SDS与C字符串的区别
 *  3. 扩展

# 1. SDS结构 #

简单动态字符串（Simple Dynamic Strings, SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。SDS兼容C语言标准字符串处理函数，且在此基础上保证了二进制安全。

struct sds{ 
    int len ;
    int free;
    char buf[];
    }

> 保存空字符的1字节空间不计算在SDS的len属性里面，并且为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作，都是由SDS函数自动完成的

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]  
其中len，free各占int的4个字节。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]

# 2. SDS与C字符串的区别 #

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

C中的字符串并不记录字符串长度，获取长度需要对数组进行遍历，其时间复杂度为O（n），而SDS在使用过程中维护这么一个长度，获取时间复杂度为O(1)。

1.  杜绝缓冲区溢出

C中的字符串相邻，溢出会覆盖另外的空间的内容。而当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。

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

通过free与提前给SDS分配一些额外的空间，减少这个重分配次数的过程。在free上增加了可操作性。

1.  SDS的API都是二进制安全的（binary-safe）

所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样。

1.  兼任部分的C字符串函数

# 3. 扩展 #

Redis 3.2后的SDS结构由1种增至5种，且对于sdshdr5类型，在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为sdshdr8。

1）SDS暴露给上层的是指向柔性数组buf的指针。

> SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针  
> SDS创建成功后，无论是sdshdr8、sdshdr16还是sdshdr32，都能通过(char\*)sh+hdrlen得到buf指针地址（其中hdrlen是结构体长度，通过sizeof计算得到）。

2）读操作的复杂度多为O(1)，直接读取成员变量；涉及修改的写操作，则可能会触发扩容。

--------------------

*后续redis系列博文均参考：书籍-《Redis设计与实现》，《Redis5 设计与源码分析》*

可参考 Redis.com

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/2f58e61c1c904e63aa772556ab3bff1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/4ddb34faa58b4c5ba4adc390bc2638e0.png