Redis数据结构二之SDS和双向链表

本文首发于公众号：Hunter后端
原文链接：Redis数据结构二之SDS和双向链表

这一篇笔记介绍一下 SDS（simple dynamic string）和双向链表。

以下是本篇笔记目录：

SDS
1. 常数复杂度获取字符串长度
2. 杜绝缓冲区溢出
3. 减少修改字符串带来的内存重分配次数
4. 二进制安全
5. 兼容C字符串函数
双向链表

1、 SDS

SDS，simple dynamic string，即简单动态字符串

SDS 在 Redis 2.9 版本中数据结构如下：

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

在这个结构中，len 表示 buf 数组中已使用字节的数量，free 表示 buf 数组中未使用字节的数量，buf 则表示是一个 char 类型的数组。

Redis 没有复用 C字符串，有以下几个方面的考虑和优点。

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

C字符串并不记录自身的长度信息，如果要获取C字符串的长度，必须遍历整个字符串然后计数。

SDS 结构中有 len 属性记录 SDS 本身的长度，可以直接获取。

2. 杜绝缓冲区溢出

因为 C字符串并不记录自身的长度信息，在执行某些操作，比如拼接字符串的时候，并不会自动查询是否拥有足够内存，那么这个操作可能就会造成缓冲区溢出的问题

而 SDS 执行相应的字符串修改时，其 API 会先检查 SDS 的空间是否需求，不满足则会进行扩展，这个空间分配策略也就是下面要讲的

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

C字符串每次进行字符串修改时，程序都需要手动进行内存重分配的操作，而 SDS 通过空间预分配和惰性空间释放两种策略对此进行了优化

空间预分配

当 SDS API 对一个 SDS 进行修改并需要对 SDS 进行空间扩展时，程序不仅会为 SDS 分配修改所需要的空间，还会为其分配额外的未使用空间

如果修改之后，SDS 的长度，也就是结构中的 len 属性小于 1MB，那么程序会额外分配同样大小的未使用空间，这个时候，len 属性和 free 属性将相同

如果修改之后，SDS 的长度，也就是结构中的 len 属性大于等于 1MB，那么程序会额外分配 1MB 的未使用空间

惰性空间释放

当需要对SDS保存的字符串进行缩短时，程序并不会重新分配内存来回收多出来的字节，而是会使用 free 属性将这些字节记录下来，以备后面使用

4. 二进制安全

C字符串保存的字符结尾都是以空字符结尾，所以字符串中间不能包含空字符，否则程序读入空字符的时候就会被认为是字符串结尾，因此C字符串只能保存文本数据，不能保存图片、音频等这样的二进制数据

而 SDS 的 API 都是以处理二进制的方式来处理 SDS 中存放在 buf 里的数据，程序不会对数据做任何限制、过滤，所以 SDS 的 API 都是二进制安全的

SDS 使用 len 属性值而不是空字符串来判断字符串是否结束

5. 兼容C字符串函数

虽然SDS的API都是二进制安全的，但是仍然遵循C字符串以空字符结尾的惯例，而且在为 buf 数组分配空间的时候总是会多分配一个字节来容纳这个空字符，所以保存文本数据的 SDS 可以重用一部分C中的函数

以下是 SDS 与 C字符串区别的总结：

C字符串	SDS
获取字符串长度复杂度为 O(N)	获取字符串长度复杂度为O(1)
API是不安全的，可能会造成缓冲区溢出	API是安全的，不会造成缓冲区溢出
修改字符串长度N次必须执行N次内存重分配	修改长度N次最多需要执行N次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用<string.h>库中函数	可以使用部分

在之后的的 Redis 版本对 SDS 的结构有过更新，将 free 属性换成了 alloc，这个属性表示的意思是分配的空间长度。和之前的 free 属性比较，其关系是 alloc = free + len

2、双向链表

C 语言没有链表这个结构，所以 Redis 自己设计了一个链表数据结构。

在 Redis 中，链表节点的结构拥有指向前置节点和后置节点的属性。

链表结构则包含链表表头节点、表尾节点、节点长度等属性，便于快速获取链表相关信息。

双向链表是列表对象的底层实现之一，什么情况下使用双向链表作为列表对象的底层实现我们之后再介绍。

以下是链表节点的结构：

typedef struct listNode{
    // 前置节点
    struct listNode *prev;
    
    // 后置节点 
    struct listNode *next;
    
    // 节点值
    struct *value;

}listNode;

在链表节点中，拥有前置节点和后置节点的指针构成双向的链表。

以下是链表的结构：

typedef struct list{
    // 表头节点
    listNode *head;
    
    // 表尾节点
    listNode *tail;
    
    // 链表包含的节点数量
    unsigned long len;
    
    ...
}list;

在链表结构中，有表头节点和表尾节点可快速定位到链表的头部和尾部，以及用有 len 属性表示链表包含的节点数量。

如果想获取更多后端相关文章，可扫码关注阅读：