引言
前期我们了解了Redis的诞生背景，今天我们来探索下它的数据结构，一步步走近它的世界。
字符串类型
redis中使用SDS（simple dynamic string）,自己构建的一种名为简单动态字符串的抽象类型来表示字符串，区别于C语言字符串，以下简称C字符串。
1、SDS的定义
struct sdshdr {
// 记录buf数组中已经使用字节的数量，等于SDS所保存字符串的长度
int len;
// 记录buf数组中未使用字节的长度
int free;
// 字节数据，用于保存字符串
char buf[];
}
2、SDS与C字符串的区别、
1、C字符串获取长度的复杂度为O(N)，SDS获取字符串长度的复杂度为O(1)。保证了redis获取字符串的长度不会成为瓶颈；
2、C字符串底层实现是一个N+1个字符长的数组，每次字符串长度发生改变，都意味着要对数组进行一次重新分配，且容易造成缓冲区溢；
3、SDS则会进行空间预分配：自身长度不够的情况下，当拼接字符串后长度小于1M，SDS的buf长度自动扩大1倍加1（空格），长度大于1M，每次扩展空间为加1M。
同时SDS有惰性空间释放的特征，当缩短字符串的时候，SDS会利用free记录未使用的空间，以备将来扩展使用；
4、二进制安全：C字符串除了字符串末尾之外，中间不可以包含空格，意味着它只能存放文本数据，而不能像SDS一样 ，支持图片、音频、视频、压缩文件这样的二进制数据。
链表
1、链表的定义
// 每一个链表节点都使用adlist.h/listNode结构来表示
typedef struct listNode {
// 前置节点
struct listNode * prev;
// 后置节点
struct listNode * next;
// 节点的值
void *value;
}
typedef struct list {
// 表头节点
listNode * head;
// 表尾节点
listNode * tail;
// 链表所包含的节点数量
unsigned long len;
// 节点值复制函数
void *(*dup) (void *ptr);
// 节点值释放函数
void (*free) (void *ptr);
// 节点值对比函数
int (*match) (void *ptr, void *key);
}
特点：
1、双端链表：获取某节点的前置节点和后置节点的复杂度都是O(1)；
2、无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点；
3、带表头指针和表尾指针：通过list结构的head和tail，获取链表的表头节点和表尾节点的复杂度都是O(1)；
4、带链表长度计数器：获取链表中节点数量的复杂度是O(1)；
5、多态：链表节点使用void*指针来保存节点的值，并且可以通过list节点的dup、free、matct三个属性为节点值设置类型特定的函数，所以链表可以用来保存各种不同类型的值。
哈希
是一个Mapmap，指值本身又是一种键值对结构，如 value={{field1,value1},......fieldN,valueN}}
1、结构定义
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值，总是等于 size -1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
}
typedef struct dictEntry {
// 健
void *key;
// 值
union {
void *val;
uint64_tu64;
int64_ts64;
}
// 指向下一个哈希表节点，形成链表
struct dictEntry *next;
}
next属性可以将多个哈希值相同的键值对链接在一起，以此来解决键冲突
2、rehash(渐进式)
负载因子 = 哈希表已保存节点数量 / 哈希表大小；
load_factor < 0.1，程序对hash表执行收缩操作；
当服务器目前没有在执行BGSAVE或者BGREWRITEAOF，并且load_factor > =1;或则服务器目前正在在执行BGSAVE或者BGREWRITEAOF，并且load_factor > =5，hash扩容
集合
特点
集合类型也是用来保存多个字符串的元素，但和列表不同的是集合中
1. 不允许有重复的元素；
2.集合中的元素是无序的，不能通过索引下标获取元素；
3.支持集合间的操作，可以取多个集合取交集、并集、差集。
有序集合
1、数据结构
typedef struct zskiplistNode {
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
// 后退指针
struct zskiplistNode *backward;
// 分值
double score;
// 成员对象
rodj *obj;
} zskiplistNode
2、特点
有序集合和集合有着必然的联系，保留了集合不能有重复成员的特性，区别是，有序集合中的元素是可以排序的，它给每个元素设置一个分数，作为排序的依据。
（有序集合中的元素不可以重复，但是score 分数 可以重复，就和一个班里的同学学号不能重复，但考试成绩可以相同）
网友评论