底层数据结构：
Redis作为Key-Value存储系统，结构如下：
RedisDB结构
Redis中存在“数据库”的概念，该结构由redis.h中的redisDb定义。
当redis 服务器初始化时，会预先分配 16 个数据库； 所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中
redisClient中存在一个名叫db的指针指向当前使用的数据库
RedisDB结构体源码：
typedef struct redisDb {
int id; // id是数据库序号，为0-15（默认Redis有16个数据库）
long avg_ttl; // 存储的数据库对象的平均ttl（time to live），用于统计
dict *dict; // 存储数据库所有的key-value
dict *expires; // 存储key的过期时间
dict *blocking_keys;// blpop 存储阻塞key和客户端对象
dict *ready_keys; // 阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
dict *watched_keys; // 存储watch监控的的key和客户端对象
}RedisObject结构（重点）
在前文已经阐述了Redis 5种基础数据类型和Stream；那么这些基础类型的底层是如何实现的呢？
Redis的每种对象其实都由对象结构(redisObject)?与?对应编码的数据结构组合而成，
而每种对象类型对应若干编码方式，不同的编码方式所对应的底层数据结构是不同的。
redisObject结构信息概览
typedef struct redisObject {
// 对象类型 六种对象类型 REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合) REDIS_STREAM 。
// 当我们执行 type 命令时,便是通过读取 RedisObject 的 type 字段获得对象的类型 例如：type key 返回 string
unsigned type:4;
// 编码类型 encoding 表示对象的内部编码，占 4 位，每个对象有不同的实现编码
// Redis 可以根据不同的使用场景来为对象设置不同的编码，大大提高了 Redis 的灵活性和效率。 通过 object encoding 命令，可以查看对象采用的编码方式
unsigned encoding:4;
// 指向底层实现数据结构的指针
void *ptr;
// 对象的引用计数，显然计数0那么就是可以回收。
int refcount;
// lru 记录的是对象最后一次被命令程序访问的时间，（ 4.0 版本占 24 位，2.6 版本占 22 位）。
// 高16位存储一个分钟数级别的时间戳，低8位存储访问计数（lfu ： 最近访问次数），淘汰策略的取值
// lru----> 高16位: 最后被访问的时间
// lfu-----> 低8位：最近访问次数
unsigned lru:LRU_BITS; //LRU_BITS为24bit 记录最后一次被命令程序访问的时间
//...
} robj; redisObject # type属性
对象类型 六种对象类型 REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合) REDIS_STREAM 。
当我们执行 type 命令时,便是通过读取 RedisObject 的 type 字段获得对象的类型 例如：type key 返回 string
redisObject # encoding属性
编码类型 encoding 表示对象的内部编码，占 4 位，每个对象有不同的实现编码
Redis 可以根据不同的使用场景来为对象设置不同的编码，大大提高了 Redis 的灵活性和效率。 通过 object encoding 命令，可以查看对象采用的编码方式
redisObject # ptr 属性 指向底层实现数据结构的指针
ptr是一个指针，指向实际保存值的数据结构，这个数据结构由type和encoding属性决定。
举个例子， 如果一个redisObject 的type 属性为OBJ_LIST ， encoding 属性为OBJ_ENCODING_QUICKLIST ，那么这个对象就是一个Redis 列表（List)，
它的值保存在一个QuickList的数据结构内，而ptr 指针就指向quicklist的对象；
下图展示了redisObject 、Redis 所有数据类型、Redis 所有编码方式以及底层数据结构之间的关系（从6.0版本中梳理而来）：
redisObject #refcount属性
redisObject中有refcount属性，是对象的引用计数，显然计数0那么就是可以回收；
- 每个redisObject结构都带有一个refcount属性，指示这个对象被引用了多少次；
- 当新创建一个对象时，它的refcount属性被设置为1；
- 当对一个对象进行共享时，redis将这个对象的refcount加一；
- 当使用完一个对象后，或者消除对一个对象的引用之后，程序将对象的refcount减一；
- 当对象的refcount降至0 时，这个RedisObject结构，以及它引用的数据结构的内存都会被释放
Redis命令的类型检查和多态
那么Redis是如何处理一条命令的呢？
- 根据给定的key，在数据库字典(dict *dict )中查找和它相对应的redisObject，如果没找到，就返回NULL；
- 检查redisObject的 type属性和 执行命令所需的类型是否相符，如果不相符，返回类型错误；
- 根据redisObject的 encoding属性所指定的编码，选择合适的操作函数来处理底层的数据结构；
- 返回数据结构的操作结果作为命令的返回值。
例如执行LPOP命令：
底层数据结构详解
简单动态字符串 - sds
Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据。具有动态扩容的特点
struct sdshdr{
//记录buf数组中已使用字节的数量
int len;
//记录 buf 数组中未使用字节的数量
int free;
//字符数组，用于保存字符串
char buf[];
}SDS的优势：
1、SDS 在 C 字符串的基础上加入了 free 和 len 字段，获取字符串长度：SDS 是 O(1)，C 字符串是O(n)。buf数组的长度=free+len+1
2、 SDS 由于记录了长度，在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
3、可以存取二进制数据，以字符串长度len来作为结束标识C： \0 空字符串 二进制数据包括空字符串，所以没有办法存取二进制数据 SDS ：
一般来说，SDS 除了保存数据库中的字符串值以外，SDS 还可以作为缓冲区（buffer）,包括 AOF 模块中的AOF缓冲区以及客户端状态中的输入缓冲区。
跳表 - ZSkipList（重点）
跳跃表是有序集合（Zset）的底层实现，效率高，实现简单。
跳跃表的基本思想：
将有序链表中的部分节点分层，每一层都是一个有序链表 , 它具有二分查找的功能
跳跃表特点：
- 每层都是一个有序链表
- 查找次数近似于层数（1/2）
- 底层包含所有元素
- 空间复杂度 O(n) 扩充了一倍
对于于一个单链表来讲，即便链表中存储的数据是有序的，如果我们要想在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)。比如查找12，需要7次查找
跳跃表查找
在查找时优先从最高层开始向后查找，当到达某个节点时，如果next节点值大于要查找的值或next指针指向null，则从当前节点下降一层继续向后查找。
如果我们增加如下两级索引，那么它搜索次数就变成了3次
//跳跃表节点
typedef struct zskiplistNode {
sds ele; // 存储字符串类型数据 在redis4.0.1中直接使用sds类型表示
double score; // 存储排序的分值， 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
struct zskiplistNode *backward;//后退指针，指向当前节点最底层的前一个节点/
// 层，柔性数组，随机生成1-64的值
struct zskiplistLevel {
struct zskiplistNode *forward; //指向本层下一个节点
unsigned int span; //本层下个节点到本节点的元素个数
} level[];
} zskiplistNode;
// 链表
typedef struct zskiplist{
structz skiplistNode *header, *tail; // 表头节点和表尾节点
unsigned long length; // 表中节点的数量
int level; // 表中层数最大的节点的层数
}zskiplist;zskiplist的核心设计要点
- 头节点不持有任何数据, 且其level[]的长度为32
- 每个结点
- ele字段：持有数据，是sds(简单动态字符串)类型
- score字段：其标示着结点的得分, 结点之间凭借得分来判断先后顺序, 跳跃表中的结点按结点的得分升序排列.
- backward指针： 该指针指向结点的前一个紧邻结点.
- zskiplistLevel字段： 用以记录所有结点(除过头节点外)；每个结点中最多持有32个zskiplistLevel结构. 实际数量在结点创建时, 按幂次定律随机生成(不超过32). 每个zskiplistLevel中有两个字段
- forward字段：指向比自己得分高的某个结点(不一定是紧邻的), 并且, 若当前zskiplistLevel实例在level[]中的索引为X, 则其forward字段指向的结点, 其level[]字段的容量至少是X+1.
- span字段: 代表forward字段指向的结点, 距离当前结点的距离. 紧邻的两个结点之间的距离定义为1.
redis为什么不用平衡树或者哈希表,而是选择跳跃表
- 由于跳跃表实现简单且达到了类似效果。
- skiplist与平衡树、哈希表的比较
skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。
因此，在哈希表上只能做单个key的查找，不适宜做范围查找。
在做范围查找的时候，平衡树比skiplist操作要复杂。
在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。
如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含1.33个指针，比平衡树更有优势。
查找单个key，skiplist和平衡树的时间复杂度都为O(log n)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。
字典/哈希表 - Dict
本质上就是哈希表, 这个在很多语言中都有，对于开发人员人员来说比较熟悉
哈希表结构定义：
1、hash表的数组初始容量为4，随着k-v存储量的增加需要对hash表数组进行扩容，新扩容量为当前量的一倍，即4,8,16,32
2、索引值=Hash值&掩码值（Hash值与Hash表容量取余）
typedef struct dictht {
dictEntry **table; // 哈希表数组
unsigned long size; // 哈希表数组的大小 ，hash表的数组初始容量为4
unsigned long sizemask; // 用于映射位置的掩码，值永远等于(size-1)
unsigned long used; // 哈希表已有节点的数量,包含next单链表数据
} dictht;
哈希表是由数组 table 组成，table 中每个元素都是指向 dict.h/dictEntry 结构，dictEntry 结构定义如下：
key 用来保存键，val 属性用来保存值，值可以是一个指针，也可以是uint64_t整数，也可以是int64_t整数。
typedef struct dictEntry{
void *key;//键
union{
void *val; //值
uint64_tu64;
int64_ts64;
}v;
struct dictEntry *next; // 指向下一个哈希表节点，形成单向链表 解决hash冲突
}dictEntry
注意这里还有一个指向下一个哈希表节点的指针next，我们知道哈希表最大的问题是存在哈希冲突，如何解决哈希冲突，有开放地址法和链地址法。这里采用的便是链地址法，通过next这个指针可以将多个哈希值相同的键值对连接在一起，用来解决哈希冲突。例如：
扩容和收缩：上面提到哈希表的初始大小为4
当哈希表保存的键值对太多或者太少时，就要通过 rehash(重新散列）来对哈希表进行相应的扩展或者收缩。
具体步骤：
- 1、如果执行扩展操作，会基于原哈希表创建一个大小等于 ht[0].used*2n 的哈希表（也就是每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表）
相反如果执行的是收缩操作，每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
- 重新利用上面的哈希算法，计算索引值，然后将键值对放到新的哈希表位置上。
- 所有键值对都迁徙完毕后，释放原哈希表的内存空间。
触发扩容的条件：
1、服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于1。
2、服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且负载因子大于等于5。
ps：负载因子 = 哈希表已保存节点数量 / 哈希表大小。
什么叫渐进式 rehash？
也就是说扩容和收缩操作不是一次性、集中式完成的，而是分多次、渐进式完成的。
如果保存在Redis中的键值对只有几个几十个，那么 rehash 操作可以瞬间完成，
但是如果键值对有几百万，几千万甚至几亿，那么要一次性的进行 rehash，势必会造成Redis一段时间内不能进行别的操作。
所以Redis采用渐进式 rehash,这样在进行渐进式rehash期间，字典的删除查找更新等操作可能会在两个哈希表上进行，
第一个哈希表没有找到，就会去第二个哈希表上进行查找。但是进行 增加操作，一定是在新的哈希表上进行的
压缩列表 - ZipList
压缩列表（ziplist）是由一系列特殊编码的连续内存块组成的顺序型数据结构节省内存是一个字节数组，可以包含多个节点（entry）。每个节点可以保存一个字节数组或一个整数。
压缩列表的数据结构如下：
- zlbytes：压缩列表的字节长度
- zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量
- zllen：压缩列表的元素个数
- entry1..entryX : 压缩列表的各个节点
- zlend：压缩列表的结尾，占一个字节，恒为0xFF（255）
entryX元素的编码结构：
- previous_entry_length：前一个元素的字节长度
- encoding:表示当前元素的编码
- content:数据内容
ziplist结构体如下：
typedef struct zlentry {
unsigned int prevrawlensize; //previous_entry_length字段的长度
unsigned int prevrawlen; //previous_entry_length字段存储的内容
unsigned int lensize; //encoding字段的长度
unsigned int len; //数据内容长度
unsigned int headersize; //当前元素的首部长度，即previous_entry_length字段长 度与 encoding字段长度之和。
unsigned char encoding; //数据类型
unsigned char *p; //当前元素首地址
} zlentry;应用场景
sorted-set和hash元素个数少且是小整数或短字符串（直接使用）
list用快速链表(quicklist)数据结构存储，而快速链表是双向列表与压缩列表的组合。（间接使用）
整数集合 - IntSet
整数集合(intset)是一个有序的（整数升序）、存储整数的连续存储结构。
typedef struct zlentry {
unsigned int prevrawlensize; //previous_entry_length字段的长度
unsigned int prevrawlen; //previous_entry_length字段存储的内容
unsigned int lensize; //encoding字段的长度
unsigned int len; //数据内容长度
unsigned int headersize; //当前元素的首部长度，即previous_entry_length字段长度与 encoding字段长度之和。
unsigned char encoding; //数据类型
unsigned char *p; //当前元素首地址
} zlentry;当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内（2^64），使用该结构体存储。
intset的结构图如下：
typedef struct intset{ uint32_t encoding; //编码方式 uint32_t length; //集合包含的元素数量 int8_t contents[]; //保存元素的数组 }intset;
应用场景
可以保存类型为int16_t、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素
快表 - QuickList
后续补充
