关于redis:Redis数据结构-字符串

5次阅读

共计 1658 个字符，预计需要花费 5 分钟才能阅读完成。

Redis 在存储字符串时，没有应用 C 语言传统的字符串示意，而是本人构建了一种名为 简略动静字符串（simple dynamic string, SDS）的形象类型。

除了用来保留数据库中的字符串值之外，SDS 还被用作缓冲区：AOF 模块的 AOF 缓冲区，以及客户端状态中的输出缓冲区。

在 Redis 中 SDS 的构造如下所示：

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

其中：

len : 记录 buf 数组中已应用字节的数量，即 SDS 中所保留字符串的长度；
free : 记录 buf 数组中未应用字节的数量
buf : 字节数组，用于保留字符串。

SDS 遵循 C 语言字符串中 以空字符结尾 的常规，保留空字符串的 1 字节不计算在 SDS 的 len 中，但 会占用一个字节空间，同样也不会统计在 free 属性中。

C 语言中的字符串并不会记录本身的长度信息，所以，为了获取长度时，须要遍历整个字符串，间接遇到完结字符为止，整个操作的工夫复杂度为 O(N)；

SDS 中保留了字符串长度，在获取长度时，能够间接返回，工夫复杂度为 O(1)。

在 C 语言中，字符串所分配内存等于字符串长度 + 1，在执行批改操作时，都须要对内存重新分配。

C 语言中字符串拼接时，须要手动调配足够多的内存，而后再执行拼接操作，如果内存不够，则会产生缓冲区溢出；而如果执行缩短操作时，须要执行内存重调配来开释闲暇内存，否则就会生产内存透露；

Redis 作为数据库，且罕用于对速度要求严苛、数据频繁批改的场合，如果每次批改，都须要执行一次内存调配的话，会对性能产生影响。

所以，为了解决这个缺点，SDS 通过未应用空间（free）解除了字符串长度和底层数组长度之间的关联，在 SDS 中，buf 数组的长度 = len + free + 1。

针对字符串拼接的场景，SDS 采纳了主动分配内存和空间预调配的操作。在拼接字符串时，会先查看空间是否满足要求，如果满足要求，间接应用未应用空间，当不满足要求时，会主动将 SDS 的空间拓展至所需的大小，而后再执行拼接操作，所以不须要手动分配内存；同时，程序不仅会为 SDS 调配批改所必须要的空间，还会调配额定的未应用空间，从而缩小内存重调配次数。

内存调配额定空间，遵循肯定的规定：

如果对 SDS 进行批改后，长度小于 1 MB 的话，那么长须调配和 len 属性同样大小的未应用空间，这时，len = free；

如果批改后，长度大于等于 1 MB，程序会调配 1 MB 的未应用空间。

针对缩短须要开释内存的操作，Redis 并不会立刻执行内存重调配来回收多出的空间，而是通过 free 属性记下，期待未来应用，应答未来字符串增长操作时，能够间接应用内存。

同时，SDS 也提供了开释空间的 API，所以不必放心内存节约。

C 语言的字符串中，必须合乎某种编码（比方 ASCII），并且除了字符串的开端之外，字符串中不能蕴含空字符，否则会被误认为是字符串结尾，从而限度了只能保留文本数据，而不能保留非凡的二进制数据。

而 SDS 通过 buf 数组，保留一系列二进制数据，而且，SDS 是通过 len 属性来判断字符串结尾，而不是空字符，从而防止了不能保留空字符串的限度。

依据下面，咱们发现，SDS 中开端的空字符串，并未产生任何作用，还为它调配了一个字节的内存，这是为什么呢？

其实，SDS 这样操作，是为了保障 SDS 能够重用一部分 C 语言中字符串函数，例如 <string.h>/strcasecmp 函数，应用它来比拟两个字符串是否相等，SDS 就能够间接应用，防止了不必要的代码反复。

Redis 应用 SDS（Simple Dynamic String，简略动静字符串）作为字符串示意形式，其有三个属性：len（已应用字节的长度）、free（未应用字节的长度）、buf（字节数组）。

相比 C 语言的字符串，SDS 具备以下长处：