c++结构体转字节数组_Redis数据结构（上）
上⼀篇我们已经介绍完了Redis的内存模型，本篇我们⼀起来看⼀下Redis数据结构。Redis常⽤的数据结构有以下⼏种：
1. 简单动态字符串
2. 链表
3. 字典
4. 跳表
5. 整数集合
6. 压缩列表
7. 对象
Redis 没有直接使⽤ C 字符串(即以空字符’\0’结尾的字符数组)作为默认的字符串表⽰，⽽是使⽤了SDS。SDS 是简单动态字符串
(Simple Dynamic String)的缩写。它是⾃⼰构建了⼀种名为 简单动态字符串(simple dynamic string，SDS)的抽象类型，并将 SDS 作
为Redis的默认字符串表⽰。SDS的定义如下：
struct sdshdr{    //记录buf数组中已使⽤字节的数量    //等于 SDS 保存字符串的长度        int len;        //记录 buf 数组中未使⽤字节的数量    int free;    //字节数组,⽤于
其中，len 保存了SDS保存字符串的长度，buf[] 数组⽤来保存字符串的每个元素，free记录了 buf 数组中未使⽤的字节数量。SDS的数据
结构⽰意图如下：
buf数组的长度=free+len+1。SDS在c字符串的基础上加⼊了free和len字段，带来了很多好处：
1. 获取字符串长度时间复杂度降低
2. 避免了缓冲区溢出
3. 可以使⽤空间预分配策略
4. 存取⼆进制数据
获取字符串长度SDS是O(1)的时间复杂度，⽽ c字符串是O(n)的时间复杂度。使⽤ C 字符串的 API 时，如果字符串长度增加(如 strcat 操
作)⽽忘记重新分配内存，很容易造成缓冲区的溢出。⽽ SDS 由于记录了长度，相应的 API 在可能造成缓冲区溢出时会⾃动重新分配内
存，杜绝了缓冲区溢出。修改字符串时内存的重分配：对于 C 字符串，如果要修改字符串，必须要重新分配内存(先释放再申请)，因为如果
没有重新分配，字符串长度增⼤时会造成内存缓冲区溢出，字符串长度减⼩时会造成内存泄露。⽽对于 SDS，由于可以记录 len 和 free，
因此解除了字符串长度和空间数组长度之间的关联，可以在此 基础上进⾏优化。空间预分配策略(即分配内存时⽐实际需要的多)使得字符串
长度增⼤时重新分配内存的概率⼤⼤减⼩。惰性空间释放策略使得字符串长度减⼩时重新分配内存的概率⼤⼤减⼩。SDS 可以存取⼆进制
数据，C 字符串不可以。因为 C 字符串以空字符作为字符串结束的标，⽽对于 ⼀些⼆进制⽂件(如图⽚等)。内容可能包括空字符串，因此
C 字符串⽆法正确存取，⽽ SDS 以字符串长度 len 来作为字符串结束标识，因此没有这个问题。此外，由于 SDS 中的 buf 仍然使⽤了 C
字符串(即以’\0’结尾)，因此 SDS 可以使⽤ C 字符串库中的 部分函数。但是需要注意的是，只有当 SDS ⽤来存储⽂本数据时才可以这
样使⽤，在存储⼆进制数据时则不⾏ (’\0’不⼀定是结尾)。接下来我们说⼀下链表，链表在Redis中的应⽤⾮常⼴泛，列表(List)的底层
实现之⼀就是双向链表。此外发布与订阅、慢查询、 监视器等功能也⽤到了链表。其数据结构定义如下：
typedef struct listNode {    //前置节点    struct listNode *prev;    //后置节点    struct listNode *next;    //节点的值    void *value;}listNodetypedef struct list {    //表头节数据结构⽰意图如下：
redis支持的数据结构
Redis链表的优势如下：
1. 双端
2. ⽆环
3. 带链表长度计数器
4. 多态
链表具有前置节点和后置节点的引⽤，获取这两个节点时间复杂度都为O(1)。表头节点的 prev 指针和表尾节点的 next 指针都指向
NULL，对链表的访问都是以 NULL 结束。通过 len 属性获取链表长度的时间复杂度为 O(1)。链表节点使⽤ void* 指针来保存节点值，可以
保存各种不同类型的值。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。