先挖个坑，还没更完，有时间再补充完整 :)
底层数据结构
SDS
简单动态字符串（Simple Dynamic String）
优点：
- 常数复杂度获取字符串长度
- 防止缓冲区溢出
- 减少修改字符串的内存重分配次数（空间预分配，小于1MB时分配和len同样大小的未使用空间，大于1MB时分配1MB的未使用空间）
- 二进制安全（可以包含空字符）
- 兼容部分C字符串函数
链表
特点：
- 双端
- 无环
- 带表头指针和表尾指针
- 带链表长度计数器
- 多态
字典
-
dict（字典） -> dictht（dict hash table，也就是哈希表）-> dictEntry（哈希表节点）
-
一般字典只使用ht[0]哈希表，ht[1]只会在扩容时使用
-
rehashidx记录rehash目前的进度，如果没有在进行rehash，则值为-1
Redis使用MurmurHash2算法计算hash值
在使用链表解决哈希冲突问题时，Redis把新加入的节点放在链表的表头位置，从而加快查找速度
rehash
-
为ht[1]分配空间，大小取决于ht[0]的键值对数量
-
扩容：ht[1]的大小为第一个大于等于ht[0].used * 2的2^n
-
收缩：ht[1]的大小为第一个大于等于ht[0].used的2^n
-
-
重新计算索引值，移动元素
-
释放ht[0]，ht[1]变为ht[0]，ht[1]创建一个空表
采用渐进式rehash，将计算工作均摊到对字典的每个增删改查操作上
扩容条件：
- 没在执行BGSAVE或BGWRITEAOF命令，且负载因子大于等于1
- 正在执行BGSAVE或BGWRITEAOF命令，且负载因子大于等于5
负载因子阈值不同的原因：Redis执行这些备份命令时，创建了一个子进程，使用写时复制技术来优化效率，此时应该避免向内存中写入新的数据（写入数据会在内存中创建新的页，造成性能开销），因此将负载因子阈值调高，防止触发扩容进行大量的写操作
收缩条件：负载因子小于0.1
跳表
平均O(logN)，最坏O(N)
跳跃表节点的结构
- level[]（层数组），其中包含的元素：
- 前进指针（下一个节点的指针）
- 跨度（下一个节点和此节点的距离）
- backward（后退指针）：用于从尾部向前遍历
- score（分值）：（用于排序）
- obj：成员对象：指向字符串对象，它保存着一个SDS
层
创建新跳表节点时，根据幂次定律（power law，越大的数出现概率越小），随机生成一个介于1-32之间的值作为level数组的大小，这个大小就是层的高度
整数集合
整数集合（intset）是保存整数的集合抽象数据类型，各个项在数组中按值的大小从小到大排序
升级
如果添加的元素类型比现有的元素类型长，则需要先进行升级（upgrade）
步骤：
- 扩展数组空间大小
- 将现有元素全部转换为新类型的大小，并放至在正确的位上，保证有序性质
- 插入新元素
因为可能需要升级，所以添加的时间复杂度是O(N)
只要升级，就不会降级，没有降级机制
优点：
- 提升灵活性
- 节约内存
压缩列表
压缩列表（ziplist）是Redis为了节约内存开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构
一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或一个整数值
压缩列表节点
每个压缩列表可以保存一个字节数组或一个整数值
字节数组是以下三种长度的其中一种：
整数值是以下六种长度的其中一种：
节点结构：
previous_entry_length
长度可以是1字节或5字节，记录了前一个节点的长度
- 如果前一个节点长度小于254字节，则此属性长度为1字节，直接保存长度
- 如果前一个节点长度大于等于254字节，则为5字节，第一字节会被设为0xFE，后四个字节保存长度
可以使用此属性从表尾向表头遍历列表
encoding
保存了数据类型和长度，将两部分保存在一起，起到了压缩空间的作用
content
保存节点的值
连锁更新
节点的增加或删除，会引起previous_entry_length属性的连锁更新
底层对象
一种对象可以利用几种数据结构储存对应的数据，需要根据情况来选择
当在Redis中新建键值对时，我们至少创建了两个对象：键对象和值对象
每个对象都由一个redisObject结构表示
类型
五种类型：
- 字符串对象
- 列表对象
- 哈希对象
- 集合对象
- 有序集合对象
对于Redis键值对来说：
- 键：总是一个字符串对象
- 值：可以是五种类型中的一种
可以使用TYPE操作查看对象的类型
编码
对象实际使用的数据类型由编码决定，也就是redisObject中的encoding属性
可以使用OBJECT ENCODING操作查看对象的编码
Redis中对象类型和底层数据结构的关系：
注意：有序集合（zset）的跳跃表实现中，同时使用了跳跃表和字典！
原因：
- 跳跃表按顺序遍历很方便，但查找元素对应的分值不方便，需要O(logN)
- 字典查找元素对应的分值方便，为O(1)，但无法做到按顺序遍历
因此有序集合就将它们一起结合使用了，需要查找分值的时候使用字典；需要按顺序遍历或者范围查找的时候使用跳跃表
总结
