redis 数据结构与对象
1 动态字符串 SDS （redis中字符串值、AOF缓冲区以及客户端输入缓冲区）
2 链表 linkedlist（发布与订阅、慢查询、监视器、redis本身保存多客户端的状态信息、构建客户端输出缓冲区）
3 字典 HashTable（又称为符号表、关联数组、映射、保存键值对抽象数据结构） 是hash键的底层
4 跳跃表 skiplist（有序集合键、集群节点中用作内部数据结构）
1 字符串对象(String) int raw embstr(专门保存短字符串的一种优化编码方式)
2 列表对象(List) ziplist linkedlist
3 哈希对象(Hash) ziplist hashtable
5 有序集合对象(Zet) ziplist skiplist
1 动态字符串 SDS （redis中字符串值、AOF缓冲区以及客户端输入缓冲区）
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
1 常数复杂度获取字符串长度
2 杜绝缓冲区溢出（api 会检查SDS是否满足需求）
3 减少字符串带来的内存重分配次数
（空间预分配、小于1MB 13+13+1 大于1MB 30MB+1MB+1） 惰性空间释放
4 二进制安全 使用len来判断字符串是否结束
5 兼容部分C字符串函数
2 链表 linkedlist（发布与订阅、慢查询、监视器、redis本身保存多客户端的状态信息、构建客户端输出缓冲区）
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
/*
* 双端链表结构
*/
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;
```
3 字典 HashTable（又称为符号表、关联数组、映射、保存键值对抽象数据结构） 是hash键的底层
哈希表
hash算法采用MurmurHash算法
使用链地址法解决冲突
渐进式rehash
哈希表节点
字典
Ht[1]会在rehash的时候使用
哈希表的扩展与收缩
渐进性rehash
4 跳跃表 skiplist（有序集合键、集群节点中用作内部数据结构）
（平均O（logN））、最坏O（N）复杂度 效率可以和平衡树来媲美）
/*
* 跳跃表
*/
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
跳跃表 skiplist 就是受到这种多层链表结构的启发而设计出来的。按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到 O(logn)。
但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的 2:1 的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点 （也包括新插入的节点） 重新进行调整，这会让时间复杂度重新蜕化成 O(n)。删除数据也有同样的问题。
skiplist 为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是 为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是 3，那么就把它链入到第 1 层到第 3 层这三层链表中。
说一下跳表的缺点：
1.内存占用比红黑树大（每个节点4指针）；
2.由于插入时是随机选择level，cache友好性不够好；
https://blog.csdn.net/brillianteagle/article/details/52206261跳跃表原理与java实现
https://blog.csdn.net/DERRANTCM/article/details/79063312跳跃表Skip List的原理和实现
https://www.cnblogs.com/tong-yuan/p/skiplist.html 跳表的插入删除
5 整数集合 Intset（集合键的底层实现）
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;
6 压缩列表 ziplist（列表键和哈希键的底层实现）
`ziplist`本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数
连锁更新（cascade update）,最坏情况下需要对压缩列表执行N次空间重分配操作，而每次重分配的最坏复杂度为 $O(N)$ ,所以连锁更新的最坏复杂度为$O(n^2)
7 对象
Redis并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统
通过这五种不同的类型的对象，Redis可以在执行命令之前，根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是，我们可以针对不同的使用场景，为对象设置多种不同的数据结构实现，从而优化对象在不同场景下的使用效率。
Redis的对象系统还实现了基于引用计数技术的内存回收机制，当程序不再使用某个对象的时候，这个对象所占用的内存就会被自动释放；另外，Redis还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据键共享同一个对象来节约内存。
0字符串对象、列表对象、哈希对象、集合对象、有序集合对象
typedef struct redisObject {
// 类型
unsigned type:4;
// 编码
unsigned encoding:4;
// 对象最后一次被访问的时间
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
// 引用计数
int refcount;
// 指向实际值的指针
void *ptr;
} robj;
1 字符串对象(String) int raw embstr(专门保存短字符串的一种优化编码方式)
字符串对象的编码可以是int、raw或者embstr
- 如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示
- 如果字符串对象保存的是一个字符串，并且这个字符串值的长度大于32个字节
- 如果字符串对象保存的是一个字符串，并且这个字符串值的长度小于等于32个字节（embstr）；redisObject和sdshdr内存连续
2 列表对象(List) ziplist linkedlist
`ziplist`或者`linkedlist`
当列表对象可以同时满足以下两个条件时，列表对象使用ziplist编码：
- 列表对象保存的所有字符串元素的长度都小于64字节
- 列表对象保存的元素数量小于512个
不能满足这两个条件的列表对象需要使用linkedlist编码
3 哈希对象(Hash) ziplist hashtable
4 集合对象(Set) intset hashtable
`ziplist`或者`hashtable`
当哈希对象可以同时满足以下两个条件时，哈希对象使用`ziplist`编码：
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个
不能满足这两个条件的哈希对象需要使用hashtable编码
5 有序集合对象(Zet) ziplist skiplist
ziplist`或者`skiplist`
```c
/*
* 有序集合
*/
typedef struct zset {
// 字典，键为成员，值为分值
// 用于支持 O(1) 复杂度的按成员取分值操作
dict *dict;
// 跳跃表，按分值排序成员
// 用于支持平均复杂度为 O(log N) 的按分值定位成员操作
// 以及范围操作
zskiplist *zsl;
} zset;
当有序集合对象可以同时满足以下两个条件时，对象使用`ziplist`编码：
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素成员的长度都小于64字节
不能满足以上两个条件的有序集合对象将使用skiplist编码
## 类型检查与命令多态
两种命令类型：对任**何类型**的键和**对特定类型的键**
### 类型检查的实现
通过redisObject结构的type属性来实现
### 多态命令的实现
Redis除了会根据值对象的类型来判断键是否能够执行命令之外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令
### 内存回收
Redis在自己的对象系统中构建了一个引用计数技术实现内存回收机制
对象的整个生命周期可以划分为创建对象、操作对象、释放对象三个阶段
### 对象共享
Redis只对包含整数值的字符串对象进行共享
### 对象的空转时长
redisObject结构包含的最后一个属性为`lru`属性，该属性记录了对象最后一次**被命令**访问的时间
京公网安备 11010502036488号