摘要：本文主要介绍的数据结构简单动态字符串简称。遵守字符串以空字符串结尾的惯例，保存的空字符串一个字节空间不计算在的属性里面。添加空字符串到字符串末尾等操作，都是由函数自动完成的，所以这个空字符对于使用者来说完全是透明的。
Redis是用ANSI C语言编写的，它是一个高性能的key-value数据库，它可以作用在数据库、缓存和消息中间件。其中 Redis 键值对中的键都是 string 类型，而键值对中的值也是有 string 类型，在 Redis 中 string 类型运用还是很广泛的。本文主要介绍 string 的数据结构—— 简单动态字符串（Simple Dynamic String） 简称sds。
sds 的数据结构:
struct sdshdr { //buf 已占用的长度 int len; // buf 剩余的可用的长度 int free; // 保存字符串数据的地方 char buf[]; }结构 sdshdr 保存了 len、free 和 buf 三个属性，分别记录字符的已使用的长度，未使用的长度，以及实际保存字符串的数组。
以下是一个新建的，保存 hello world 字符串的 sdshdr 结构：
struct sdshdr { len = 5; free = 0; buf = "hello/0"; }sds 遵守 C 字符串以空字符串结尾的惯例，保存的空字符串一个字节空间不计算在 sds 的 len 属性里面。添加空字符串到字符串末尾等操作，都是由 sds 函数自动完成的，所以这个空字符对于使用者来说完全是透明的。
通过 len 属性，可以实现时间复杂度 O(1) 的长度计算。另外通过对 buf 分配一些额外的空间，并使用 free 记录未使用空间的长度，sdshdr 可以减少内存的重新分配。这是 sds 相对 c 字符串的一个优势。
Redis 是使用 C 语言开发的，而在使用最多的字符串上，Redis 没有使用 C 语言传统的字符串表示，而且使用自己构建的简单动态字符串（sds）。
在 C 语言中，字符串可以用一个 /0 结尾的 char 数组表示。比如 hello world 在 C 语言中就可以表示为"hello world/0"。数组一般初始化以后长度就已经固定了，不能支持字符串追加append和长度计算操作：
Redis 作为数据库，对于查询速度要求严格，数据修改也比较频繁，如果每次修改字符串都需要执行一次内存分配的话，都会占用大量的时间。所以 Redis 选择了 sds 而不是 C 字符串，sds 可以减少追加字符的内存分配。通过举例来说明，执行以下操作时，sds 内部的变化：
redis> set msg "hello world"OKredis> append msg " again"(integer)18redis> get msg"hello world again"首先 set 命令创建并保存hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：
struct sdshdr { len = 11; free = 0; buf = "hello world/0";}当执行 append 命令时，相对应的 sdshdr 被更新，字符串 " again" 会被追加到原来的 "hello world" 之后：
struct sdshdr { len = 17; free = 17; buf = "hello world again/0 ";}当调用 set 命令创建 sdshdr 时，Redis 没有给 sdshdr 分配多余的空间，free 属性为0。而在执行 append 操作之后，Redis 为 buf 分配了多于所需空间一倍的大小。
在执行 append 命令之后，保存 "hello world again" 共需要17 + 1 个字节，但是程序为 sdshdr 分配了 17 + 17 + 1 = 35 个字节，而后续如果在对 sdshdr 进行追加操作，只要追加的长度不超过 free 属性值，那么就不需要对 buf 进行内存重分配。
比如执行以后命令并不会引起 buf 的内存重分配，因为新追加的字符串长度小于17：
redis> append msg " again"(integer) 23对应的 sdshdr 结构如下：
struct sdshdr { len = 23; free = 11; buf = "hello world again again/0 ";}redis 内存分配可以查看源码 sds.s/sdsMakeRoomFor，sdsMakeRoomFor 函数描述了内存分配的策略，下面的该函数的伪代码：
// sdshdr:追加前的字符// addlen：追加字符串sds sdsMakeRoomFor(sdshdr, addlen) { // 多余空间大于追加空间，无序再分配内存，直接返回 if (free >= addlen) return s; // 计算新字符的长度 newlen = (len+addlen); // 如果新字符的长度小于 SDS_MAX_PREALLOC，就分配两倍新字符空间 // 如果新字符的长度大于 SDS_MAX_PREALLOC，就分配新字符空间 + SDS_MAX_PREALLOC 空间 if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; // 分配内存 newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); // 更新 free 属性 newsh.free = newlen - len; return newsh;}而对于字符的缩短操作，Redis 保存缩短后的字符串，此时并不会进行内存重分配，而是使用 free 属性记录缩短的字符长度。
Redis 的 string 类型为何使用sds而不是 C 字符串，因为sds有两点优势：
如果觉得文章对你有帮助的话，请点个推荐吧!
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/125679.html
摘要：用指令来看一个值的数据结构。对象只有同时满足下面两个条件时，才会使用压缩列表哈希中元素数量小于个哈希中所有键值对的键和值字符串长度都小于字节。采用了链地址法的方法解决了哈希冲突的问题。数据类型的底层可以是整数集或者是散列表也叫哈希表。 前言 上篇文章 Redis闲谈（1）：构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制，相信大家对redis有了初步的认识。互联网的很...
摘要：用指令来看一个值的数据结构。对象只有同时满足下面两个条件时，才会使用压缩列表哈希中元素数量小于个哈希中所有键值对的键和值字符串长度都小于字节。采用了链地址法的方法解决了哈希冲突的问题。数据类型的底层可以是整数集或者是散列表也叫哈希表。 前言 上篇文章 Redis闲谈（1）：构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制，相信大家对redis有了初步的认识。互联网的很...
摘要：用指令来看一个值的数据结构。对象只有同时满足下面两个条件时，才会使用压缩列表哈希中元素数量小于个哈希中所有键值对的键和值字符串长度都小于字节。采用了链地址法的方法解决了哈希冲突的问题。数据类型的底层可以是整数集或者是散列表也叫哈希表。 前言 上篇文章 Redis闲谈（1）：构建知识图谱介绍了redis的基本概念、优缺点以及它的内存淘汰机制，相信大家对redis有了初步的认识。互联网的很...
摘要：字符串是最基本的数据结构，首先键都是字符串类型的，而且其他几种数据结构也都是在字符串类型的基础之上构建的，因此，我认为从字符串入手来探究的数据结构是相对合理的。为了满足存储不同长度字符串的需求为了节省内存，在宏定义中定义了五种。 本文以 redis 3.2.8 版本来介绍 redis 源码。字符串是 Redis 最基本的数据结构，首先键都是字符串类型的，而且其他几种数据结构也都是在字符...
摘要：目的现在是各个系统几乎都在使用的一种分布式高可用的缓存内存中的数据结构存储系统。但是这些我们经常使用的数据结构的底层是怎么实现的。总结因为作为一个数据库存储来使，而且是一个单线程，一旦一个操作阻塞了之后之后的所有操作都会被影响。 目的 Redis现在是各个系统几乎都在使用的一种分布式高可用的缓存内存中的数据结构存储系统。可以作为数据库、缓存消息中间件、订阅发布系统等。我们都知道redi...
阅读 426·2023-04-25 19:43
阅读 3617·2021-11-30 14:52
阅读 3413·2021-11-30 14:52
阅读 3347·2021-11-30 14:49
阅读 3275·2021-11-30 14:49
阅读 3520·2021-11-29 11:00
阅读 3487·2021-11-29 11:00
阅读 3518·2021-11-29 11:00
