Redis数据结构-动态字符串
我们都知道 Redis 中保存的Key是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构。
不过 Redis 没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：
- 获取字符串长度的需要通过运算
- 非二进制安全
- 不可修改
Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS。
例如，我们执行命令：
set name 技术
那么 Redis 将在底层创建两个 SDS，其中一个是包含“name”的 SDS，另一个是包含“技术”的 SDS。
Redis 是 C 语言实现的，其中 SDS 是一个结构体，源码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct sds { int len; // 记录字符串的长度 int free; // 记录未使用的字节数 char buf[]; // 字符串的实际存储空间 } sds; // 创建一个新的 sds sds *sds_new(int init_len) { sds *s = malloc(sizeof(sds) + init_len + 1); if (!s) return NULL; s->len = 0; s->free = init_len; s->buf[0] = '\0'; return s; } // 释放 sds void sds_free(sds *s) { if (s) free(s); } // 追加字符串到 sds sds *sds_append(sds *s, const char *append) { int append_len = strlen(append); if (s->free < append_len) { s = realloc(s, sizeof(sds) + s->len + append_len + 1); if (!s) return NULL; s->free = append_len; } memcpy(s->buf + s->len, append, append_len); s->len += append_len; s->free -= append_len; s->buf[s->len] = '\0'; return s; } // 打印 sds void sds_print(const sds *s) { printf("Length: %d\n", s->len); printf("Free: %d\n", s->free); printf("String: %s\n", s->buf); } int main() { sds *str = sds_new(10); if (!str) { printf("Error: Unable to create SDS.\n"); return 1; } str = sds_append(str, "Hello, "); if (!str) { printf("Error: Unable to append to SDS.\n"); return 1; } str = sds_append(str, "world!"); if (!str) { printf("Error: Unable to append to SDS.\n"); return 1; } sds_print(str); sds_free(str); return 0; }
例如，一个包含字符串“name”的sds结构如下：
动态扩容举例
SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：
假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：
- 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；
- 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。
二进制安全
Redis可以存储各种数据类型，那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式，可能会包含一些特殊的字符，比如‘\0’等。- 前面我们提到过，C 中字符串遇到
‘\0’会结束，那 ‘\0’之后的数据就读取不上了。但在SDS中，是根据len长度来判断字符串结束的。 - 如此, 二进制安全的问题就解决了。
SDS优点
SDS 优点：
- 获取字符串长度的时间复杂度为
O(1) - 支持动态扩容, 减少内存分配次数
- 二进制安全
与C语言中的字符串的区别
SDS（Simple Dynamic String）是Redis使用的一种字符串表示方式，与C语言中的字符串有一些显著的区别：
- 动态调整大小：SDS是动态分配内存的，可以根据需要动态增加或减少其大小，而C语言中的字符串通常是静态分配的，大小在创建时就确定了，后续无法直接调整大小。
- 二进制安全：SDS允许存储任意二进制数据，而C语言中的字符串通常以NULL结尾，因此不适合存储包含NULL字符的二进制数据。
- 惰性空间释放：SDS采用惰性空间释放策略，即当SDS的内容被截断或缩短时，并不立即释放多余的内存，而是等待下一次需要扩展空间时才释放。这种策略可以减少频繁的内存分配和释放操作，提高性能。而C语言中的字符串在缩短时无法自动释放多余的内存，需要手动管理内存。
- 长度存储：SDS在内部存储了字符串的长度信息，这样可以在O(1)时间内获取字符串的长度，而C语言中的字符串需要遍历整个字符串才能确定长度。
SDS是一种更加灵活和高效的字符串表示方式，特别适合需要频繁修改和操作字符串的场景，而C语言中的字符串更适合于静态不变的情况。
