Sds （Simple Dynamic String，简单动态字符串）
简单动态字符串实现
struct sdshdr {
// buf 已占用长度
int len;
// buf 剩余可用长度
int free;
// 实际保存字符串数据的地方
char buf[];
};
Redis的简单动态字符串使得编程更加简单。原有的c的字符串的api是不安全的，因为在使用字符数组以后，需要跟踪内存的分配。在使用之前，需要预分配空间，否则会有缓冲区溢出。用完一个字符串需要回收，否则会有内存泄漏。
Redis的简单动态字符串在每一次创建一个新的string时，不会按照实际大小分配，而是预分配更多的内存，当字符串截断时，也不是立刻回收内存，而是减少len值，增加free值。字符串插入时，先看free够不够，不够再分配。这样减少了内存分配回收的次数，效率更高。对应的策略叫做：空间预分配 和 惰性回收。
使用了以上sds数据类型，为编程带来的好处有五点：
-
获取长度变为了O1的操作。
-
杜绝了缓冲区溢出。
-
减少了字符串改变造成的空间分配次数。
-
二进制安全。
-
兼容部分C字符串函数
链表
双端链表结构
typedef struct list {
// 表头指针
listNode *head;
// 表尾指针
listNode *tail;
// 节点数量
unsigned long len;
// 复制函数
void *(*dup)(void *ptr);
// 释放函数
void (*free)(void *ptr);
// 比对函数
int (*match)(void *ptr, void *key);
} list;
双端链表节点结构
typedef struct listNode {
// 前驱节点
struct listNode *prev;
// 后继节点
struct listNode *next;
// 值
void *value;
} listNode;
Redis 实现了自己的双端链表结构。
双端链表主要有两个作用：
- 作为 Redis 列表类型的底层实现之一；
- 作为通用数据结构，被其他功能模块所使用；
双端链表及其节点的性能特性如下：
- 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 O(1) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
- 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 O(1) ；
- 链表带有记录节点数量的属性，所以可以在 O(1) 复杂度内返回链表的节点数量（长度）；
网友评论