关于后端:Redis数据结构二之SDS和双向链表

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

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

以下是本篇笔记目录：

1. SDS

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

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 字符串区别的总结：

在之后的的 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 属性示意链表蕴含的节点数量。

如果想获取更多相干文章，可扫码关注浏览：