Redis对象底层数据结构
Redis对象底层数据结构
| 编码常量 | 编码所对应的底层数据结构 |
|---|---|
| REDIS_ENCODING_INT | long 类型的整数 |
| REDIS_ENCODING_EMBSTR | embstr 编码的简单动态字符串 |
| REDIS_ENCODING_RAW | 简单动态字符串 |
| REDIS_ENCODING_HT | 字典 |
| REDIS_ENCODING_LINKEDLIST | 双端链表 |
| REDIS_ENCODING_ZIPLIST | 压缩列表 |
| REDIS_ENCODING_INTSET | 整数集合 |
| REDIS_ENCODING_SKIPLIST | 跳跃表 |
Redis string类型转换
我们可能以为Redis在内部存储string都是用sds的数据结构实现的，其实在整个Redis的数据存储过程中为了提高性能，内部做了很多优化。整体选择顺序应该是：
整数，存储字符串长度小于21且能够转化为整数的字符串。
EmbeddedString，存储字符串长度小于39的字符串（REDIS_ENCODING_EMBSTR_SIZE_LIMIT）。
SDS，剩余情况使用sds进行存储。
embstr和sds的区别在于内存的申请和回收
- embstr的创建只需分配一次内存，而raw为两次（一次为sds分配对象，另一次为RedisObject分配对象，embstr省去了第一次）。相对地，释放内存的次数也由两次变为一次。
- embstr的RedisObject和sds放在一起，更好地利用缓存带来的优势
- 缺点：Redis并未提供任何修改embstr的方式，即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。
Redis list数据结构
Redis list数据结构底层采用压缩列表ziplist或linkedlist两种数据结构进行存储，首先以ziplist进行存储，在不满足ziplist的存储要求后转换为linkedlist列表。
当列表对象同时满足以下两个条件时，列表对象使用ziplist进行存储，否则用linkedlist存储。
- 列表对象保存的所有字符串元素的长度小于64字节
- 列表对象保存的元素数量小于512个。
Redis hash底层存储结构
Redis的哈希对象的底层存储可以使用ziplist（压缩列表）和hashtable。当hash对象可以同时满足一下两个条件时，哈希对象使用ziplist编码。
- 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
- 哈希对象保存的键值对数量小于512个
Redis的hash架构就是标准的hashtab的结构，通过挂链解决冲突问题。
Redis set底层存储
Redis的集合对象set的底层存储结构特别神奇，底层使用了intset和hashtable两种数据结构存储的，intset我们可以理解为数组，hashtable就是普通的哈希表（key为set的值，value为null）。是不是觉得用hashtable存储set是一件很神奇的事情。
set的底层存储intset和hashtable是存在编码转换的，使用intset存储必须满足下面两个条件，否则使用hashtable，条件如下：
- 结合对象保存的所有元素都是整数值
- 集合对象保存的元素数量不超过512个
zset底层存储结构
zset底层的存储结构包括ziplist或skiplist，在同时满足以下两个条件的时候使用ziplist，其他时候使用skiplist，两个条件如下：
- 有序集合保存的元素数量小于128个
- 有序集合保存的所有元素的长度小于64字节
当ziplist作为zset的底层存储结构时候，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员，第二个元素保存元素的分值。
当skiplist作为zset的底层存储结构的时候，使用skiplist按序保存元素及分值，使用dict来保存元素和分值的映射关系。
Redis为何要定义字符串为SDS
Redis是底层使用的是C语言，在C语言中没有字符串这种数据类型，字符串大都是通过字符数组实现的，但是使用字符数组有以下不足：
- 字符数组的长度都是固定，容易发生空指针异常
- 获取字符数组的长度的时候需要遍历数组，时间复杂度高
- 字符数组长度发生改变之后需要重新分配内存
- 使用\0表示结尾，在存储二进制会出现问题。
//动态字符串，数组的长度是可变的。
struct sdshdr {
unsigned int len;//记录当前串的长度。
unsigned int free;//记录剩余的有效长度。
char buf[];//真正的字符串位置。
};Redis就自己实现了SDS来解决上面的问题，SDS相对C字符串数组的优点：
- 长度达到一定标准会有相应的扩容（小于1M，free增加len，大于1M，每次增加1M），从而解决内存溢出的问题。
- 在SDS的内部定义了字符串的长度，使用时可以直接获取，复杂度O(1)，解决获取长度时间复杂度高的问题。
- SDS是空间预分配，惰性释放内存的，从而减少分配内存的次数
- SDS根据长度判断结束的位置，从而解决二进制不安全的问题。
