数据结构
简单动态字符串SDS
可以认为在Redis中所有的东西最终都是字符串。Redis是C语言实现的，但是Redis没有直接使用C语言中的字符串，C语言字符串是字符数组实现的，存在很多问题：
1、获取字符串的长度需要运算，时间复杂度达到O(n)。
2、非二进制安全，无法保存\0字符（被识别成结束标识）。
3、不可修改。
Redis构建了一种新的字符串结构，称为简单动态字符串SDS，SDS本质是一个结构体：
uint8 len：无符号整形，8bit，所以这种SDS允许最长的字符串长度是255-1（结束标识）
flags：用来标识SDS的类型，因为有多种不同长度的SDS（sdshdr8、sdshdr16...）。
len和alloc都不计算结束标识所占的1个长度。
读取时不是以\0结束标识作为结束条件，而是读取len个字符，保证了二进制安全，而且可以很容易获取字符串长度。
所以SDS包含头和字符串本身，头存储字符串长度、申请的内存大小和SDS类型。
动态扩容
IntSet整数集合
整数集合，基于整数数组实现，有序不重复。
为了方便查找，redis会将所有整数按照升序依次保存在contents数组中。
若加入的整数超出大小限制，则IntSet会自动升级编码（先扩容，后添加，改头部）。
自动升级编码
升级过程中，倒序依次将数组中的元素拷贝到扩容后的正确位置，扩容完成后添加新的元素。修改encoding，length+1。
底层采用二分查找插入排序保证有序，所以数据量很大的时候查询很慢；并且数组是连续内存空间，只适合存储小数据量，小数据量的时候查询效率较高。
Dict哈希表
redis键与值的映射关系正是通过Dict来实现的。联想到HashMap，数组+Entry链表，根据key做hash运算，计算出数组角标。
Dict也是这样实现的，哈希表（dictht）储存了一个dictEntry指针类型的数组的首地址，数组存储指向dictEntry的指针，哈希节点DictEntry，存储键值对。
size永远是2^n，used可以大于size（形成链表甚至红黑树）。
union联合体，表示v可以是四个数据类型中的任意一个，*key和 *val表示指向SDS字符串。
添加键值对时，redis首先根据key计算出hash值h，然后利用h&sizemask计算元素在数组中存放的索引。新加入的Entry加入到链表队首（因为添加到队首最方便）。
此外还有一个dict，主要是功能性的拓展，与rehash有关。
ZipList压缩列表（直接看下文基本数据类型进行了解）
连续内存空间，内存占用低，但存储上限低，适合数据量不多的情况下使用。
QuickList快速列表（直接看下文基本数据类型进行了解）
SkipList跳表（直接看下文基本数据类型进行了解）
排序，有序
RedisObject
上述每种底层数据结构最终会被封装为一个RedisObject的结构体，也叫Redis对象。
共占用16byte（0.5+0.5+3+4+8），即每个redis对象的头部占用16字节。
所以String用起来是最简单的，但是每一个String都需要一个头部，导致许多内存用来记录头信息。
所以记录大量数据的时候，不推荐使用String，除非只能用String保存。
encoding是编码方式，包括上述的底层数据结构。
五种基本数据类型的编码
String
三种编码方式：
1、其基本编码方式是RAW，基于简单动态字符串（SDS）实现，存储上限为512mb。
2、如果存储的SDS长度不超过44，则会采用EMBSTR编码，此时object head与SDS合并成一段连续空间，总内存大小不超过64字节。创建对象只需申请一次内存（只需要调用一次内存分配函数），效率更高。所以使用字符串时，尽可能保证字符串大小不超过44（一个字符占一个字节）。
3、如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码∶直接将数据保存在RedisObject的ptr指针位置（刚好8字节，可以存储任意类型的整数)，不再需要SDS了。
List
要求可以从首、尾操作列表中的元素。
使用QuickList的编码方式：LinkedList（双向链表） + 多个ZipList（压缩列表）
RedisObject的指针指向一个QuickList，QuickList中存储了指向首尾节点的指针，每一个QuickList节点指向一个ZipList，压缩深度为1，即首尾不做压缩，中间全部压缩。
Set
要求单列集合，无序性、互异性（唯一性），极高的查询效率。
两种编码方式：
1、Dict哈希表，查询快。
让Dict的dictEntry的key存储元素（唯一性），而value统一为null。（联想到HashSet）
但存在弊端：每个dictEntry都是独立的内存空间，所以内存占用多。
2、IntSet
当Set集合存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries（512）时，Set会采用IntSet编码，以节省内存（连续内存空间）。
ZSet（SortedSet）
每个元素由score和member组成，member唯一，要求可以根据member查询对应分数，并且有序（后添加的member会覆盖同样member的score值）
两种编码方式：
1、ZipList
当元素数量不多时，Dict和SkipList更耗内存。因此ZSet还会采用ZipList结构来节省内存，不过需要同时满足两个条件：
①元素数量小于zset_max_ziplist_entries（默认128）
②元素大小都小于zset_max_ziplist_value（默认64字节）
ZipList本身没有排序功能，而且没有键值对的概念，因此需要通过一定方式编码：
- ZipList内存连续，因此score和element是紧挨在一起的两个entry，element下一个就是score。
- score越小越接近队首，score越大越接近队尾，按照score值升序排列。（ZRANGE命令）
2、Dict + SkipList
Dict不能排序，SkipList不能存储键值对，两者互补。但是该实现存在很多指针，内存占用高。
Hash
要求键值存储、能根据键获取值，与ZSet类似（键值对调），但不需要排序。ZSet的键是member，值score要求是数字；hash的键和值都是任意值。
因此可以考虑和ZSet相同的实现，因为不需要排序，所以将与排序有关的SkipList去掉，只使用Dict。
1、ZipList
Hash结构默认采用ZipList编码，用以节省内存。ZipList中相邻的两个entry分别保存field和value。
2、Dict
ZipList内存空间连续存储上限低。当数据量较大时，Hash的编码方式会转为Dict，触发条件有两个：
- ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
- ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）
dictEntry的key存储field，val存储value。
