Update:《Redis设计与实现》读书笔记
简单动态字符串
Redis没有直接使用C语言传统的字符串表示（以空格结尾的字符串数组），而是自己构建了一种名为简单动态字符串（SDS）的结构，并将SDS用作默认字符串表示。 SDS定义如下：
struct sdshdr {
// 保存的字符串的长度
int len;
// 未使用的字节数量
int free;
// 字节数组，用于保存字符串
char buf[];
} shshdr;
SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节空间不计算在SDS的len属性里。遵循这种惯例，使得SDS可以直接服用一部分C字符串函数。
SDS优势
- 常数复杂度获取字符串长度
- 直接读取len属性
- 杜绝栈溢出的情况
- 当对SDS进行修改时，SDS会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，会自动扩展空间至所需大小。
- 减少内存分配次数
- 空间预分配用于优化SDS的字符串增长操作，当对SDS进行修改并且需要扩展空间时，程序不仅会分配所需空间，还会为SDS分配额外的未使用空间。
- 额外空间数量
- 修改后的SDS长度小于1MB，分配的未使用空间和属性len相同。
- 修改后的SDS长度大于1MB，分配的未使用空间为1MB。
- 当SDS缩短时，不直接收回多出来的字节，而是使用free属性将这些字节的数量记录下来，等待将来使用。
链表
// 节点定义
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
// 链表定义
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点数量
unsigned long len;
// 节点值复制函数
void *(*dup) (void *ptr);
// 节点值释放函数
void *(*free) (void *ptr);
// 节点值对比函数
int (*match) (void *ptr, void *ptr);
} list;
- 双向链表
- 带表头指针和表尾指针
- 带长度计数，常数复杂度获取节点数量
字典
一种用于保存键值对的抽象数据结构，Redis的字典使用哈希表作为底层实现，一个哈希表里面可以包含多个哈希表节点，每个哈希表节点就保存了字典中的一个简直对
// 哈希表节点
typedef struct dictEntry {
// 键
void *key
// 值
union{void *val; uint64_t u64; int64_t s64;};
// 指向下个节点
struct dictEntry *next;
} dictEntry;
// 哈希表
typedef struct dictht {
// 哈希表节点数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 用于计算索引值，总是等于size-1
unsigned long sizemash;
// 哈希表节点数量
unsigned long used;
} dictht;
// 字典
typedef strcut dict {
// 类型特定函数
dictType *type;
// 私有数据
void *private;
// 哈希表
dictht ht[2];
// rehash 索引，当rehash不在进行时值为-1
int trehashidx;
} dict;
- 当要将一个新的键值对添加到字典里面是，程序需要先根据键值对的键计算出哈希值和索引值，然后根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
- 当多个键值对被分配到了同一个索引上面时，Redis采用链地址法解决冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来。
- 随着操作的进行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
跳跃表
- 跳跃表是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
跳跃表节点
// 跳跃表节点 typedef struct zskiplistNode { // 后退指针 struct zskiplistNode *backward; // 分值 double sxore; // 成员对象 robj *obj; // 层 struct zskiplistNode { // 前进指针 struct zskiplistNode *forward; // 跨度 unsigned int span; } level []; } zskplistNode; - 层：跳跃表节点的level数组可以包含多个元素，每个元素包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度。
- 前进指针：每个层有一个指向表尾方向的前进指针，用于从表头向表尾方向访问节点。
- 跨度：用于记录两个检点之间的距离。
- 后退指针：用于从表尾方向表头访问节点。
- 节点的分值：跳跃表中的所有节点都按分值从小到大排列。
跳跃表
// 跳跃表 typedef struct zskiplist { // 表头和表尾节点 structz skiplistNode *header, *tail; // 表中节点数量 unsigned long length; // 最大层数 int level; } zskiplist; - 头指针和尾指针分别指向跳跃表的表头和表尾节点，访问表头表尾的复杂度尾O(1)，通过length属性可以在O(1)复杂度返回跳跃表长度。
整数集合
- 整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
typedef struct intset { // 编码方式 uint32_t encoding; // 集合包含的元素数量 unint32_t length; // 保存元素的数组 int8_t contents[]; } intset; - length 记录了整数集合包含的元素数量。
- intset声明为int8_t类型的数组，但实际上contents数组不保存任何int8_t类型的值，真正的类型取决于encoding的值。
- 当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面。
- 扩展空间
- 类型转换
- 添加元素
- 整数集合不能降级
压缩列表
- 压缩列表是列表键和哈希键的底层实现之一。
- 压缩列表的属性
- zlbytes 记录整个压缩列表所占的内存字节数
- zltail 记录压缩列表表尾节点距离压缩列表的其实地址有多少个字节
- zllen 记录了压缩列表的节点数量
- entryx 列表节点
- zlend 用于标记压缩列表的末端
压缩列表节点
- 每个压缩列表节点可以保存一个字节数组或者一个整数值
- 每个压缩列表节点由previous_entry_length,encoding,content三部分组成
- previous_entry_length 属性以字节为单位，记录了压缩列表中前一个节点的长度
- previous_entry_length属性的长度可以为1字节或5字节
- 如果前一个节点的长度小于254字节，那么previous_entry_length占1字节
- 如果前一个节点的长度大于等于254字节，那么previous_entry_length占5字节
- encoding 记录了节点的content属性所保存数据的类型以及长度
- 1字节，2字节，5字节最高位分别为00，01，10的是字节数组编码，其余位决定数组的长度
- 1字节值的最高位以11开头的是整数编码，其余位决定整数值的类型和长度
- content 负责保存节点的值，节点的值可以是一个字节数组或者整数，值的类型和长度由节点的encoding决定
压缩列表总结
- 压缩列表是一种为了节约内存而开发的顺序型数据结构
- 压缩列表被用作列表键和哈希键的底层实现之一
- 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
- 添加新节点到压缩列表或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的纪律并不高
上面介绍了Redis的底层数据结构，Redis并没有直接使用这些数据结构来实现数据库，而是基于这些数据结构创建了一个对象系统
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序集合对象
typedef struct redisObject { // 类型 unsigned type:4; // 编码 unsigned encoding:4; // 指向底层数据结构 void *ptr; } robj;
字符串对象
- 字符串对象的编码可以是int，raw， embstr
- 如果字符串保存的是整数值，并且这个整数可以用long类型表示，那么字符串对象会讲整数值保存在字符串对象结构的ptr属性里面，并将编码设置为int。
- 如果字符串对象保存的是一个字符串值且长度大于39字节，那么字符串对象将使用一个SDS来保存这个字符串值，并将对象的编码设置为raw。
- 如果字符串对象保存的是一个字符串且长度小于等于39字节，那么字符串对象将使用embstr编码方式来保存这个字符串值。
- int编码的字符串和embstr编码的字符串对象在条件满足的请夸过下，会被转为raw编码的字符串对象。
- embstr类型一旦被修改，就会转变为raw编码的字符串对象，哪怕长度小于39字节。
列表对象
- 列表对象编码可以是ziplist或linkedlist。
- ziplist编码的列表对象底层使用压缩列表作为实现，每个压缩列表节点保存一个列表元素。
- linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点都保存了一个字符串对象，而每个字符串都保存了一个列表元素。
- 当列表对象可以同时满足一下两个条件时，列表对象使用ziplist编码
- 列表对象保存的所有字符串元素的长度都小于64字节
- 列表对象保存的元素数量小于512个
哈希对象
- 哈希对象可以是ziplist或者hashtable
- ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入压缩列表表尾，然后再将保存了值的压缩列表节点推入压缩列表表尾。
- 当哈希对象可以同时满足一下两个条件时，哈希对象使用ziplist编码
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字符
- 哈希对象保存的键值对数量小于512个
集合对象
- 集合对象的编码可以是intset或者hashtable
- intset编码的集合对象底层使用整数集合作为实现
- hashtable编码的集合对象使用字典作为底层实现
- 当集合对象同时满足以下两个条件时，使用intset编码
- 集合对象保存的所有元素都是整数值
- 集合对象保存的元素数量不超过512个
有序集合对象
- 有序集合对象的编码可以是ziplist或者skiplist
- ziplist编码的有序集合对象底层使用压缩列表实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存
- 第一个节点是元素的成员，第二个元素则保存元素的分值
- skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表
- 理论上有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现
- 为了提升速度，空间换时间
- O(1)复杂度查找成员的分值， 使用字典
- O(logN)范围查找使用跳跃表
- 同时满足以下两个条件时，对象使用ziplist编码
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素成员的长度都小于64字节