完整的redis底层数据结构应该是这样的，看完舒服多了：
最外面一层RedisServer，里面15个RedisDb，RedisDb里面是多个dict对象，dict里面是hashmap结构（实际上为了hash扩容，封装了2个hashmap，每次用一个），key是我们常写的get set的key，value就是 list、String、set这些对象
能用空间解决的优先用空间解决（空间换时间），能压缩的一定压缩
1.string(arraylist)
1.1 数据结构
struct SDS<T>{
T capacity; //数组容量
T len; //数组长度
byte flags; /zi/特殊标志位，不用理他
byte[] content;//数组内容
}
1、比起传统的c语言字符串，有什么优势那？ 传统的c语言字符串就是NUll（0x\0）为结束符，但是如果想要知道这个字符串的长度，就需要遍历。所以redis的字符串就在里面加了一个长度len**，用空间换取时间。**
2、默认的字符串，如果有append操作，需要分配新的数组，然后将旧的数组复制过去，redis也做了一层优化，就是预分配机制，就是一旦触发了扩容（也就是说append操作），会预分配更长的content。具体规则是1M之前翻倍扩容，>1M就是每次加1M。
3、这个泛型T也有说法，当字符串比较小的时候，T可以用byte和short来表示，真是极致优化
4、embstr和row也有说法，当redis字符串总体长度>64字节的时候，redis认为这就是个大字符串，需要单独分配，这个临界点就是44 （64-16-3-1）64是每次分配内存都是32/64这样分配，16是redisObject对象头的大小，3是sds里面不包含内容的大小，1是字符串最后的null
Redis对象头
1.2 应用
- 计数、递增、普通的字符串缓存等等
2. list（linkedlist）
2.1数据结构
3.2之前比较小时ziplist，增多时升级为linkedlist
struct{
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offest; // 最后一个元素距离起始位置的偏移量，方便定位到最后一个
int16 zllength; // 元素个数
T[] entries; // 元素内容列表
int8 zlend; // 标志压缩列表的结束，值为0xFF
}
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度 int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
这里其实也很好理解，当数据量小的时候，数组有很大的优势 1、减少指针占用的空间 2、利用cpu缓存 。但是一旦数据量上来，分配和移动数组都是一个很大的开销，所以还是链表更好。
压缩列表存在的问题：连锁更新
从上图可以看到redis的压缩链表做了一点优化，如果前一个entry的length<254字节,那当前entry的prelen就存一个字节，否则就存5个字节。如果说存在以下情况：
这个时候，如果我往e1前面插入1个大于254字节的内容，就会导致e1需要修改自己的prelen,然后引发多米诺效应，连续需要更新所有的内容。
2.2.1总结一下
压缩列表的好处和坏处
- 好处：节省内存、利用cpu缓存
- 坏处：当数据量大的时候，分配和拷贝内存都非常消耗性能、还存在连锁更新的恐怖问题
3.2之后，统一使用quicklist，quicklist的解决方法是尽量还是使用ziplist来压缩内存，但是尽量控制ziplist的长度，来规避上面说到的连锁更新的问题。但是并没有解决该问题。
2.2 应用
- 消息队列
3. hash (ziplist->dict)
3.1 数据结构
数量较少使用ziplist，达到一定大小后升级为类似Java HashMap结构.
3.1.2 ziplist压缩列表
struct{
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offest; // 最后一个元素距离起始位置的偏移量，方便定位到最后一个
int16 zllength; // 元素个数
T[] entries; // 元素内容列表
int8 zlend; // 标志压缩列表的结束，值为0xFF
}
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度 int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
说白了，就是用数组实现了类似于链表的机构，为了支持从末尾遍历，增加了tail_offset支持直接定位到尾节点，而且每个节点都存放了前一个entry长度，同样是方便从后往前寻址。但是ziplist都是紧凑存储，没有冗余空间（就是空的地方），意味着每次插入一个元素都需要realloc拓展内存，如果ziplist占据内存太大，重新分配内存和拷贝内存就会消耗很大，所以ziplist不适合存储大型字符串，存储的元素也不宜过大。
3.1.3 dict字典 （hashtable[2]）
字典是Redis服务器中出现最为频繁的复合型数据结构，除了hash结构的数据会用到字典（dict）外，整个Redis数据库的所有key和value也组成了一个全局字典，还有带过期时间的key集合也是一个字典。zset集合中存储value和score值的映射关系也是通过字典实现的。
Struct RedisDb{
dict * dict;
dict * expires
}
struct zset{
dict * dict;
zskiplist * zsl;
}
struct dict{
dictht ht[2]; //字典里面会用到2个hashmap
}
既然用了链式存储，那当链表上数据量很大的时候（也就是说hash冲突很频繁的时候），那就需要rehash
rehash过程
- 什么时候触发rehash
- 当数据量大小=哈希表大小的时候，再看一下有没有bgsave命令（也是AOF和RDB操作），如果没有就需要rehash
- 当数据量 / 哈希表大小=5的时候，强制rehash
- 怎么rehash
- 渐进式的rehash，当有新增、删除、查找或者更新操作时，就会去执行把原来hashble上的数据rehash到新的hashtable上
- 如果客户端很空闲怎么办？开启一个定时任务，来完成rehash
3.2 应用
- 分布式锁（redisson）
- 对象缓存
4. set （inset或者hash）
4.1数据结构
4.1.1 当set的数据类型为整数的时候，采用下面这种格式
struct{
int32 encoding;
int32 length;
int<T> contents;
}
4.1.2 当set内容为其他类型的时候，采用下面这种格式
struct dict{
dictht ht[2]; //字典里面会用到2个hashmap
}
这里有个很明显的问题？？？？？ 为什么set 不像hash一样去使用压缩链表，而直接去使用hash
5.zset （ziplist->skiplist）
5.1 数据结构
5.1.2 ziplist
当数据量不是很大的时候，使用的是ziplist
struct {
dict *dict;
ziplist *zip
}
5.1.3 skiplist
struct {
dict *dict;
zskiplist *zsl;
}
当数据量大的时候，还是要使用链式存储，数组一样的存储在存储动态数据的时候，遇到更新操作太操蛋了。
跳表的搜索过程：！！！
- 从顶部开始搜索，如果搜索到的内容 < 目标对象，就进入下一层搜索，如果搜索到的内容 > 目标对象，就移动到前一个节点，然后进入下一层搜索
- 假设上面搜索权重4
- 找到 level2，找到最后 9>4, 然后退回到 level2的1，1往下一层搜索
- leve1的1往后找，找到 level的5 >4, 又退回到 level1的1，1往下一层搜索
- level0的1往后找，找到4
