- 详细介绍Redis用到的数据结构
- 简单动态字符串
- SDS和C字符串的区别
- 总结
- 链表
- 字典
- 哈希表
- 字典
- 哈希算法
- 解决键冲突
- rehash(重点)
- 渐进式rehash
- 跳跃表
- Redis中跳跃表的实现
- 跳跃表节点结构
- 跳跃表总体结构
- 整数集合(intset)
- 整数集合具体实现
- 数组升级
- 数组降级？没有降级，一旦升级就不会降级
- 数组升级的好处
- 压缩列表
简单动态字符串各位，稍安勿躁，讲解五种基本数据类型前，我们先来这些数据类型用到的数据结构，防止后面懵逼,本文所用源码来源：Redis源码链接，版本使用6.2
我们都知道Redis是用C写的，但Redis中并没有直接使用C语言传统的字符串(以空字符结尾的字符数组)，而是自己构建了一种名为简单动态字符串(simple dynamic string，简称SDS)的结构，并用作Redis的默认字符串。在Redis中，C字符串只会用作字符串字面量，一些不会对字符串发生修改的地方，比如说打印日志等等。
Redis中SDS的定义：
typedef char *sds;
struct __attribute__ ((__packed__)) sdshdr5 { // 对应的字符串长度小于 1<<5
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
uint8_t len; //目前字符串的长度
uint8_t alloc; //已经分配的总长度
unsigned char flags; //flag用3bit来标明类型
char buf[]; //柔性数组，以' '结尾
};
struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
SDS和C字符串的区别
- C字符串中使用n+1个字符数组表示n个长度的字符串，并且数组的最后一个总是‘ ’，表示该字符串结尾了。
- C字符串获取长度时，需要遍历一遍字符串，时间复杂度为O(N),而SDS获取字符串长度时，只需要从SDS结构中取出len字段便可以，时间复杂度为O(1)
- C字符串为其增加一段字符串时，如果没有为其分配足够的空间，则会造成缓冲区溢出；而使用我们的SDS时，则SDS会自动检查是否容量足够，不够的话就扩容，所以使用我们的SDS时不需要手动扩容，也就不会发生缓冲区溢出
- 减少字符串带来的内存重分配次数,在C中，每次添加字符串都需要对数组扩容，删除字符串也需要内存重新分配。而SDS通过提前分配和惰性释放可以很好的改善内存重分配次数
提前分配：当SDS剩余空间不足时，Redis不但会给它分配足够的空间，还会给它分配多余的空间，如果下次增加字符串时，则可以使用这部分空余的空间，减少内存重分配
惰性释放:在删除一些字符时，Redis并不会立即释放空间，这样的话可以为将来的增加操作减少内存重分配的次数；于此同时，在Redis真正需要空间时，Redis也会释放掉这部分空间，不会内存泄露 - 二进制安全：C字符串中不能包含一些空字符，否则可能会被认为是字符串结尾导致字符串截断，所以不能保存一些图片视频的二进制数据。而SDS并不是通过空字符来判断结束的，不会对内容进行任何处理，可以保存二进制数据
- 兼容部分C字符串函数：Redis也会在结尾加上多余的一个‘ ’，使得某些情况可以使用C字符串的函数，减少自己实现重复功能
由于Redis数据库的特性，会频繁的增删查改，保存一些二进制数据，而原来的C字符串并不能高性能的完成这些事，所以Redis才自己封装了SDS
链表Redis定义的结构
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
这是双端链表最基础的定义，下图是示意图：
虽然使用多个listnode便可以组成链表的话，但Redis使用list结构来持有链表，操作更加方便
typedef struct list {
//表头结点
listNode *head;
//表尾结点
listNode *tail;
//结点复制函数
void *(*dup)(void *ptr);
//结点释放函数
void (*free)(void *ptr);
//结点对比函数，通过这三个函数可以为结点值设置不同的函数，从而包含各种不同类型的值，实现多态
int (*match)(void *ptr, void *key);
//结点的数量
unsigned long len;
} list;
总体结构如下：
在字典中，一个键（key）可以和一个值（value）进行关联（或者 说将键映射为值），这些关联的键和值就称为键值对；
Redis的字典底层使用哈希表来实现，一个哈希表中有多个哈希表结点，一个哈希表结点保存了字典中的一个键值对
哈希表Redis中源码表示：
typedef struct dictht {
//哈希表数组，里面是一个dictEntry结构
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值，总是等于size-1
unsigned long sizemask;
//已经存在结点的数量
unsigned long used;
} dictht;
//哈希表结点
typedef struct dictEntry {
//键
void *key;
//值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
//下一个节点，使其形成链表
struct dictEntry *next;
} dictEntry;
以上两个结构总体为：
Redis中字典结构源码表示：
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//两个哈希表，作用后面说
dictht ht[2];
//当rehash不进行时，值为-1
long rehashidx;
int16_t pauserehash;
} dict;
type和privdata是针对不同类型的键值对，为多态而创建的
ht[2]两个哈希表是为了rehash而设计的，一般只使用ht[0]这个哈希表，ht[1]只会在对ht[0]进行rehash的时候使用
rehashidx它记录了目前rehash的进度，为-1时则说明不进行rehash
不进行rehash下的字典示意图：
当插入一个键值对时，需要用哈希算法算出对应的索引值，并把它插入其中(具体就不再多说什么，不了解的可以去查看数据结构这门课程)
Redis计算哈希值和索引的方法：
#使用字典设置的哈希函数，计算键key 的哈希值 hash = dict->type->hashFunction(key); #使用哈希表的sizemask 属性和哈希值，计算出索引值 #根据情况不同， ht[x] 可以是ht[0] 或者ht[1] index = hash & dict->ht[x].sizemask;
Redis使用MurmurHash2算法来计算键的哈希值，这种算法最大的优点就是当输入有规律的数时，也能平均散列到数组中
解决键冲突Redis使用链地址法解决键冲突
rehash(重点)随着操作的进行，哈希表的键值对会逐渐增多或者减少，为了让哈希表的负载因子保持在一个合理的范围区间，就必须对哈希表进行扩展或者收缩。而扩展或者收缩，我们需要执行rehash(重新散列)来完成一次操作
rehash执行步骤如下：
- 为字典的ht[1]分配空间，大小取决于ht[0]和所执行的扩展或者收缩操作。
- 将ht[0]的所有键值对rehash到ht[1]上(rehash指的是重新计算哈希值和索引，重新散列到ht[1]这个哈希表中)
- 移动完成后，释放ht[0]的空间，将ht[1]改为ht[0]，并为ht[1]重新创建一个空的哈希表，为下一次rehash准备
如果数据量比较多时，一次性移动我们的hash表，那么时间会比较久，就有可能造成redis服务停止。所以执行rehash时，并不是一次完成的，而是渐进式完成的
渐进式rehash步骤如下：
- 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
- 在字典中维持一个rehashidx，也就是上面的字典结构的属性，将其值设置为0，表示rehash工作开始
- 在rehash期间，程序除了执行指定的操作外，还会将索引为rehashidx的数据移动到ht[1]相当于将ht[0]里的数据删除，在ht[1]里面增加，当rehashidx这个索引的数据全部移动完成时，则将rehashidx值加1，直到全部完成
- 完成后，将rehashidx的值表示为-1，并将ht[1]设置为ht[0].
在渐进式rehash期间，字典进行的删除，更新，查找会在两张哈希表上进行。比如查找，redis会先在ht[0]查找，找不到才会到ht[1]上面查找
而字典进行的插入操作，则只会在ht[1]表里执行。这样的话，ht[0]表里的数量只减 不增，也减少了重复插入的操作
跳跃表在Redis中，有两个地方用到了跳跃表，一个是实现有序集合类型，一个是在集群节点中作内部数据结构
跳跃表节点在/src/server.h/中zskiplistNode结构定义：
typedef struct zskiplistNode {
//成员对象
sds ele;
//分值
double score;
//回退指针
struct zskiplistNode *backward;
//跳表层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned long span;
} level[];
} zskiplistNode;
zskiplistLevel跳表层：
上图的L1,L2就表示的是跳表层，每个层有两个属性。 forward表示前进指针，用它来遍历后面的元素。span表示跨度：上图连线上的数字就是这个跨度，两个元素离的越远，跨度就越大；而这个跨度的作用就是计算我们的rank(排位) ，在遍历一个元素时，就他路径上的跨度全部加起来就是它的rank。比如查找下面的o3这个节点时，rank就为3
backward回退指针：
每个节点只有一个回退指针，所以每次只能回退到前一个节点，而不能跳来跳去；回退指针用于从后向前遍历
score分值：是一个double类型的浮点数，跳表中所有元素都是按分值来排序的。
ele成员对象：是一个sds的字符串对象。成员对象必须是唯一的，而分值可以是相同的。分值相同时，按成员变量的字典序排序
一个跳跃表有多个跳跃表节点。通过zskiplist来持有这些节点。
Redsi中zskiplist结构的定义如下：
typedef struct zskiplist {
//表示表头结点和表尾节点
struct zskiplistNode *header, *tail;
//节点数量
unsigned long length;
//最大层数
int level;
} zskiplist;
看到上面这张图应该就可以明白每个字段表示的含义了吧！表头那个节点并不计算在内。准确的来说，表头节点虽然都有对应的属性，但是我们是不会用到的，只是后面插入，删除时更加方便
整数集合是Redis用来保存整数值的集合，保证集合中不会出现重复的元素
整数集合具体实现typedef struct intset {
//编码方式
uint32_t encoding;
//集合数量
uint32_t length;
//保存元素的数组
int8_t contents[];
} intset;
encoding编码方式表示数组用什么类型来保存
length集合数量保存了集合中的数量
contents[]集合数组虽然是类型是int8_t，但是实际取决于encoding编码方式。数组内是大小有序的，从小到大，不含重复值
当对数组中添加新元素时，如果新添加的元素类型大于原来的数组的类型，则需要对数组进行升级。
升级步骤如下：
- 按新的类型扩展原有数组大小，并为新元素分配空间
- 将原来的数组元素转换为新的元素类型，并且保存有序
- 将新添加的元素加入数组
大致流程如下：
数组降级？没有降级，一旦升级就不会降级 数组升级的好处因为新添加的类型是大于原有数组类型的，所以新添加的元素一定大于或者小于原有数组里的元素，每次插入也一定是插到头或者尾
1. 更加方便
C语言中要保存两种不同类型的元素就必须使用两个类型数组来保存
而Redis则使用数组升级来避免了使用两个数组，更加方便，且不用担心类型错误
2. 节约内存
要让一个数组保存不同的类型，最简单就是直接定义一个最大的数组类型，但是这样会占用不必要的空间
而Redis则只是在必要的时候才升级数组，尽量节约了内存
明天写
