[redis] 数据结构与对象--简单动态字符串SDS

秒速五厘米 2024-03-25 11:01 5阅读 0赞

在Redis里，C字符串常常用于无需对字符串值进行修改的地方。需要被修改的字符串使用SDS（简单动态字符串）。此外SDS还被用在AOF缓冲区和客户端状态中的输入缓冲区的实现。

本文学习记录主要包括以下两点：SDS的定义、SDS和C字符串的区别。

## 一、SDS的定义 ##

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

> 初始化时，len=5，free=0，buf数组中存有五个字符r e d i s 和空字符'\\0'。空字符'\\0'是额外分配1字节的，不计入字符串长度len中。

## 二、SDS相对于C字符串的优点 ##

总的来说，SDS优于C字符串在如下几个方面：

*  获取字符串长度的时间复杂度为O(1)

*  杜绝了缓冲区的溢出

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

*  二进制安全

*  SDS兼容部分C字符串函数

### 1. SDS只需常数时间复杂度即可获取长度 ###

C字符串获取长度虚呀遍历，遇到空字符'\\0'结束。SDS只需要访问len属性即可。设置和更新len属性是SDS的API在执行的时候完成的。

### 2. 杜绝缓冲区的溢出 ###

这跟SDS的空间分配策略有关（下一节）在C语言中，若两个字符串在内存中紧邻，对前一个字符串进行修改可能会导致后一个字符串被覆盖。

### 3. 减少了修改字符串时内存重分配的次数 ###

每次对增长或者缩短一个C字符串，程序都要对其数组进行一次内存重分配，不仅消耗资源，还有产生缓冲区溢出或者内存泄漏的风险。SDS通过未使用空间接触了字符串长度与底层数组之间的关联。SDS通过未使用空间实现了两种优化策略：空间预分配、惰性空间释放

#### （1）空间预分配 ####

*  修改SDS时，先检查未使用空间是否足够，如果足够，则直接使用；如果不够，则执行以下内存重分配策略。

*  若SDS修改后，len小于1MB，那么程序分配未使用空间大小free=已使用空间大小len。此时SDS的buf数组实际长度为len + free + 1字节，其中len == free。

*  若SDS修改后，len大于等于1MB，那么程序分配未使用空间大小free=1MB。此时SDS的buf数组实际长度为len + free + 1字节，其中free = 1MB

#### （2）惰性空间释放 ####

*  用于优化SDS的缩短操作，当需要缩短字符串时，不是立即重新分配内存来回收空间，而是使用free属性将这些字节的数量记录起来，用于将来使用。

### 4. 二进制安全 ###

*  C字符串遇到空字符'\\0'就是结束，SDS中有种特殊字符串是以空字符'\\0'为分割的。

*  SDS的所有API都是以处理二进制的方式处理buf数组里的数据，也就是说buf数组里存的是一系列二进制数据（buf数组又称为字节数组）

*  比如redis-cli进入命令行，set中文字符串后，取出来的是一串16进制字符。而redis-cli --raw进入命令行才能拿到中文。

### 5. 兼容部分C字符串函数 ###

SDS以空字符'\\0'结尾，可以重用<string.h>的一部分字符串函数。

## 三、总结 ##

![0ded2f4608264b1a84e4596c9d56fba6.jpeg][]

[0ded2f4608264b1a84e4596c9d56fba6.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8162c793fc8b49c99c4c887c1ec9119b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，5人围观）

还没有评论，来说两句吧...

相关阅读

相关【Redis】动态字符串SDS

[CSDN话题挑战赛第2期][CSDN_2] 参赛话题：[面试宝典][Link 1] 文章目录前言源码数据安全动态总结

川长思鸟来/ 2024年04月06日 13:44/ 0 赞/ 28 阅读

相关 [redis] 数据结构与对象--简单动态字符串SDS

在Redis里，C字符串常常用于无需对字符串值进行修改的地方。需要被修改的字符串使用SDS（简单动态字符串）。此外SDS还被用在AOF缓冲区和客户端状态中的输入缓冲区的实现。

秒速五厘米/ 2024年03月25日 11:01/ 0 赞/ 6 阅读

相关 Redis内部数据结构详解之简单动态字符串(sds)

> 本文所引用的源码全部来自Redis2.8.2版本。 > > Redis中简单动态字符串sds数据结构与API相关文件是：sds.h, sds.c。 > 转载请注明，本文

痛定思痛。/ 2023年10月17日 15:53/ 0 赞/ 89 阅读

相关 Redis源码解析-SDS简单动态字符串

前言 -------------------- SDS是Redis基础数据结构之一，不同于C字符串（以/0结尾，无法保证二进制安全），SDS为Redis定义的一种抽象类

小咪咪/ 2022年12月23日 00:38/ 0 赞/ 152 阅读

相关 Redis数据结构之简单动态字符串

一：简单动态字符串的结构 1：SDS结构体 struct sdshdr { //buf已占用的空间长度 //等于SDS所保存的字符

绝地灬酷狼/ 2022年10月23日 14:27/ 0 赞/ 171 阅读

相关 Redis中的数据结构与对象（简单动态字符串）

一、简单动态字符串 > 1、简介 > 2、SDS的定义 > 3、SDS与C字符串的区别 > 4、SDS特性 1.1 简介 Redis没有直接使用C

素颜马尾好姑娘i/ 2022年10月13日 12:35/ 0 赞/ 149 阅读

相关 Redis数据结构之简单动态字符串

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.cap

柔情只为你懂/ 2022年09月09日 00:23/ 0 赞/ 161 阅读

相关 Redis数据结构-简单动态字符串

一、前言 Redis没有直接使用C语言传统的字符串表示（以空字符结尾的字符数组，以下简称C字符串），而是自己构建了一种名为简单动态字符串（simple dynamic s

不念不忘少年蓝@/ 2022年09月03日 10:15/ 0 赞/ 126 阅读

相关 Redis(一):简单动态字符串(SDS)

简单动态字符串(Simple Dynamic String) Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符串)，而是自己构建了一种命名为简单

朴灿烈づ我的快乐病毒、/ 2022年05月25日 09:37/ 0 赞/ 141 阅读

相关 Redis数据结构——简单动态字符串-SDS

1、SDS简介： redis没有使用C语言传统的字符串表示（以空字符结尾的字符数组），而是自己构建了一种名为简单动态字符串（SDS）的抽象类型，并将SDS用作re

╰+哭是因爲堅強的太久メ/ 2021年09月23日 16:06/ 0 赞/ 293 阅读