Redis 底层数据结构
动态字符串 SDS (Simple Dynamic String)
1
2
3
4
5
6
7
8
9
10
11
12
13
|
struct sdshdr {
//SDS所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组，用于保存字符串
char buf[];
};
// set msg “hello world”
// 对于 msg 来说，它的 sdshdr 这个对象的值是： len=3； free=3；buf[]= [‘m’, ‘s’, ‘g’,‘\0’]
|
SDS的核心优势
-
C语言中的字符串如果想要得到长度，需要进行遍历，意味着时间复杂度为O(n)，如果使用SDS，可以直接从len属性中获取长度O(1)
-
C语言的字符串如果进行扩展或者缩减，必须提前分配内存空间或有意识的进行空间的释放。无论是进行扩展还是缩减，都需要进行内存的重新分配。SDS不会造成缓冲区溢出的问题
-
当创建SDS对象的时候，free空间也会分配当前的字符串相同大小的空间，预防进行字符串的扩展，扩展时可以直接使用，无需进行空间分配，即空间预分配。如果存储的key是超过1MB的字符串，free就分配1MB，当需要对字符串进行缩减时，惰性空间释放
-
二进制安全问题。C语言的字符串是二进制不安全的，因为C语言空字符结尾的设计，如果一个字符串中间有空字符串，那么C语言的字符串二进制转化会遗弃第一个空字符出现的后边的所有内容。SDS则不会，SDS是二次封装的对象，能够支持二进制的安全。
C语言的空字符结尾有二进制问题，为什么SDS的buf里面还是以空字符串的结尾？
因为SDS基于C语言实现，也需要使用C语言中字符串的一些方法，所以为了兼容一部分C语言中字符串的操作，所以以空字符串结尾
链表结构
列表键的底层实现就是一个链表，链表中的每个节点都保存了一个数值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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;
// lpush list 0 1 2 "hello" 'a'
// list 就代表了我们的 typedef struct list 结构体, listNode就是底层实现的链表节点
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
}listNode;
// 为什么是 void?
// void 这里代表的是 多态
// 对于 redis 来说，由于 list 里可以存放各种类型的数值，那么，如果你要进行多种类型值的一些统一操作的话，需要使用 void 的返回值类型，这里体现了 我们 多态的一个性质。
|
列表，链表，字符串的关系示例
- list就是列表（源码时list：listNode的关系，底层实现为链表ListNode）
- SDS
- 第一个SDS：为key “list"准备，free = 4; len = 4; buf = [list\0]；，这是列表的名称，列表的key
- 第二个SDS：为a准备，以此类推，第四个SDS时给c准备的
- SDS的a b c这三个对象保存到listNode源码里边的 void *value属性中（多态）
