Redis是一款使用广泛的开源的内存数据库，性能优异，官方单机读写QPS接近10W，那么Redis是如何做到的，除了优秀的架构，底层数据结构的优化也起到了很大的作用，本文就分析下Redis的底层数据结构是如何设计的。
首先，Redis常用的数据类型有字符串、哈希表、列表、集合、有序集合，无论什么结构的键值对都存于字典中，而字典不仅用于键值对的存储，也用于哈表表的结构实现。
一、字典：
字典的实现方法在/redis-7.0/src/dict.c的方法中，其本质就是通过数组实现的散列表，在redis-server启动中，整个数据库会先初始化一个空的字典，用于存储整个数据库的键值对。
1、数据结构:
字典采用了C语言的数组作为字典的容器，数组的下标都是整型，所以redis中针对所有的键值都转化为字符串，然后通过哈希函数转化为整型，为了将整型更好的散列到哈希表中，在哈希数组的外层在创建一个结构体，这个结构体中带了一个 sizemask掩码，数值是数组size - 1，通过跟掩码 进行 & 运算，可以得到求模的结果。字典解决哈希冲突采用的是链表法，作为每一个字典的槽，当然也是一个独立的结构体，有键值，和一个联合体代表着具体数据的类型，还有一next指针，指向下一个槽。
2、冲突解决：
针对哈希冲突的链表插入采取的是头插法，这样不用再去遍历整个链表。Redis采用的是单进程单线程操作，所以不会有并发的冲突，每次在插入之前先根据键值进行查询，如果已经存在则修改，否则则插入。字典的初始化长度是 4 ，每次扩容都是 扩大一倍。
3、扩容：
考虑到扩容在最外层再嵌套一个结构体 struct dict
其中有几个字段
dictht hash_table[2] 一个哈希表的数组。
rehashidx rehash 标识，默认是-1，代表没有进行rehash操作，不是-1时代表正进行rehash 操作， 存储的值表示ht[0]的rehash 操作进行到了哪个索引值。
这里描述下字典扩容的过程，首先申请当前hash 容量一倍的内存，并把内存地址复制给ht[1]，并给字典打上进行进行rehash 的标识，rehash idx = 0，这个期间，新增的字段都到 hash_table[1] 中，而修改、删除、查找则要在hash_table[0] hash_table[1]中进行检查再决定对哪个hash表操作。
rehash 调用函数 dictRehash，依次把 ht[0]中的键重新hash 放入到新的哈希表中，并删除老的哈希表对应的字段，rehash 结束后，清空老哈希表，对调ht[0]和ht[1]的值，并把rehashidx重新标为-1，redis rehash 采用的是分而治之的方法，当执行增删改查的时候，先判断是否正在进行rehash 操作，如果是，调用dictRehashStep只对一个节点进行rehash，除了这个操作之外，服务空闲的时候，也会进行批量的rehash操作。 100个节点进行rehash 只需要1ms。除此之外，在字典rehash时，发生了字典遍历，维护一个字典指纹，如果在迭代中字典发生变化，退出执行，并提示安全迭代器，中断rehash 操作，直到遍历完成。
扩容时机：
二、压缩列表
压缩列表（ziplist）就是一个字节数组。是为了节约内存而设计的一种线性数据结构。刚开始默认的长度是固定的，也就是初始化的数组有几个值已经是固定的，其中的信息包括压缩列表的字节长度 4个字节，所以最多有 2^32 - 1 ，压缩列表尾元素相对于压缩列表起始地址的偏移量，且压缩列表的元素个数，占用两个字节，压缩列表存储的元素，可以是字节数组或者是整数，列表的结尾，占用一个字节恒为OXFF。
存储元素的类型的结构为：
previous_entry_length + encoding + content 分别为 前一个元素的字节长度 + 编码 + 内容，前一个字节长度，占一个或者5个字节，当长度小于254时，用一个字节表示，否则用5字节。
encoding代表着当前内容的信息，endoding占用字节数不固定，可能占用1、2、5个字节，第一个字节的前两位 可能是 00 01 10 11 分别代表着 6bit 位用来表示长度的字节数组，14位，32位 ，整数。根据后面的字节可以得知content占用字节的大小。
previous_entry_length 存在的意义就是可以让压缩列表从尾到头进行遍历。如果当前的元素的首地址是P，那么P-previous_entry_length 就是以一个元素的首地址。为了获取任一元素，需要对压缩列表进行复杂的解码，解码后的结果被缓存起来。插入元素的时候，先将内容进行编码，然后重新计算空间，因为是数组所以不能动态分配空间，需要重新申请内存，然后计算需要插入数据的偏移量，然后将原来数组的内容复制到新的数组。加入原来的数组是 10字节，新的元素计算之后是3字节，那么新的数组空间不一定是13字节，原因是，插入元素后一个 元素的previous_entry_length可能又1字节变为5字节。
三、quicklist
List数据结构是quicklist，quicklist 是由 ziplist 充当节点 的一个双向链表。如果 ziplist 节点过多，quicklist退化成双向链表，过少退化成ziplist，极端情况就是只有一个ziplist，所以，quicklist是在空间和速度 实现的折中方案。所以quicklist 结构体，有头节点，尾节点，所有元素的和，节点的个数，并指明每个节点的最大数量或者空间大小。
为了进一步降低空间，redis采用LZF压缩算法，将数据分为多个片段，每个片段有 解释字段+数据 两部分进行组成。基本思想是，数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据。插入元素，查看那个节点能否插入，可以直接调用ziplist的插入，否则新建节点，再插入。
四、动态字符串SDS：
动态字符串是用于存储字符串和整型数据的，首先这个字符串一定是二进制安全的，所以肯定是要进去长度信息的
struct sds{
int len; //buf 中已占用的字节数
int free;//buf可用字节数
char buf[];//柔性数组 存放数据
}
但是这个结构体太浪费空间了，哪怕一个字节的字符串，也要占用两个int，redis 5.0之后根据字符串的长度进行了结构体的划分，长度小于32位的字符串，结构体中只有两个字段，unsigned char flags 底三位存储类型，高5位存储长度。
char buf[]//存放实际内容
这样仅仅多了一个字节 就能完成一个二进制安全的字符串存储。上面说的存储类型就是根据头部长度类型区分的，上面占用一个字节，还有，占用 2 、4、8字节的情况。
那么占用2字节的结构体如下：
struct adshdr8{
uint8_int len;
uint8_int allloc;
unsigned char flags;
char buf[];
}
同理，只需要改变 len 和 alloc的类型即可，uint16 /32/64等，不过此时flags的高5位只能是预留的。
五、跳跃表
有序集合的底层实现是跳跃表，其实实现有序集合可以采用数组，链表，平衡树等。但是数组不便于插入和删除，链表的查询效率低，平衡树和红黑树效率高，但是结构复杂。
redis采用了跳跃表的方案，跳跃表是建立在一个有序链表上的，但是为了增加查找速度，在一个链表上建立多层顺序链表，而同一个位置的每层数据都是相同的，即用空间来换时间。每一层最终指向的都是NULL，层高最高是64 最低是 1，创建节点的 层高是随机生成的，1-64， 值越大概率越低，插入节点时也需要随机生成一个层高，然后找到要 插入的位置，调整跳跃表的高度，然后调整后退指针，后退指针只能指向 当前节点最底层的前一个节点。
总结一下，所有的字段都存在字典中， String 字符串使用的动态字符串数据结构，Hash 哈希表使用的是字典，List 列表使用的是 quicklit ，Set 集合如果都是整数的时候使用的是整数集合（整数集合的结构体，也是一个柔性数组，但是多了两个字段，一个是编码类型，即int16 int32 int64 和元素数量），如果不全是整数 采用字典。