String
使用SDS（simple dynamic string）实现。
3.2版本前
struct sdshdr {
//长度
int len;
//剩余长度
int free;
//数据本体
char buf[];
}
3.2版本以后
主要有以下几个字段
- len 长度，有uint8_t、uint16_t、uint64_t 这几种类型
- alloc 已经分配的空间，有uint8_t、uint16_t、uint64_t 这几种类型
- unsigned char flags 表示类型，在最小长度中还会使用len的功能
- char buf[] 具体数据存储的地方
详细情况如下所示
typedef char *sds;
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];// buf[0]: z: 0101001
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
扩容策略
字符串在长度小于1M之前，扩容空间采用加倍策略，也就是保留100%的冗余空间。
当长度超过1M之后，为了避免加倍后的冗余空间过大而导致浪费，每次扩容只会多分配1M大小的冗余空间。
为什么不直接使用原生C语言的字符串
- 原生C语言字符串是通过\0结尾，想要知道字符串长度，需要通过O(n)的时间复杂度的strlen标准函数库来获取（遍历扫描），Redis是单线程的，性能需要做优化。
- redis作为开源中间件，可能接受很多类型语言的调用，其他类型语言如果将\0作为字符串的一部分提供给redis，若此时reids使用C语言原生库，则无法支持。
List
旧版本：数据量少时候用ziplist，数据量多的时候使用linkedlist
新版本：使用QuickList 参见下文
Hash（字典）
存储数据结构
zipList
当数据量比较小或者单个元素比较小时，底层用zipList存储。
hash-max-ziplist-entries 512 ziplist元素超过512，将其改为hashtable编码
hash-max-ziplist-value 64 单个元素大小超过64byte时，将其改为hashtable编码
dict
struct dict {
dictht ht[2]
}
dict结构内部包含两个hashtable，通常情况下只会使用一个hashtable。在dict扩容缩容的时候，需要重新分配hashtable，然后进行渐进式搬迁，这个时候两个hashtable存储的分别是旧的hashtable和新的hashtable。待搬迁结束后，旧的hashtable被删除，新的hashtable取而代之。hashtable的结构和java的hashmap几乎是一样的，通过链表的方式解决hash冲突，第一维是数据，第二维是链表。数据中存储的是第二维链表的第一个元素的指针。
渐进式搬迁
大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到像新的数组下面，这是一个O(n)级别的操作，会非常耗时，所以redis使用渐进式rehash小步搬迁，在hset 和hdel命令中埋伏了搬迁操作。如果客户端空闲了，没有后续命令，则redis会在定时任务中搬迁。
扩容条件
正常情况下，当hash表中的元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新组是原数组大小的2倍。不过若Redis正在做bgsave，为了减少内存页的过多分离（copy on write），Redis尽量不去扩容（dict_can_resize），但是如果hash表已经非常满了，元素的个数已经达到了第一维数组长度的5倍（dict_forece_resize_ratio），说明hash表已经过于拥挤了，这个时候就会强制扩容。
缩容条件
当hash表因为元素的主键删除变得越来越稀疏时，Redis会对hash进行缩容来减少hash表的第一维数组空间占用。缩容条件是元素个数低于数组长度的10%。缩容不会考虑Redis是否正在做bgsave
Set
intset
当set集合容纳单元素都是整数并且元素个数比较少时，使用intset来存储元素
set-max-int-set-entries 512 intset能存储的最大元素个数，超过则使用hashtable编码
图示
hashtable
与Hash相同，不过value都是null
ZSet(Sorted Set)
数据量少的时候，用ziplist实现
数据量多的时候，zset内部实现是一个hash字典加一个跳跃链表（skiplist）
ZipList（压缩列表）
设计目的是为了提高存储效率。可以用于存储字符串或整数，其中整数是按真正的二进制表示进行编码的，而不是编码成字符串序列。ziplist能以O(1)的时间复杂度在表的两端提供push和pop操作。
图示
增加元素
插入一个新元素需要realloc扩展内存，取决于内存分配器的算法和当前的ziplist，如果realloc可能需要重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可在原有的地址上进行扩容。
级联更新
由于每个entry都会有一个prerawlan，如果内容小于254，则prerawlen使用一个字节，否则就是5个字节。那么某个entry进过了修改操作从253字节变成了254字节，那么它的下一个entry的prerawlen就需要更新，从1个字节扩展到5个字节：如果这个entry的长度本来也是253字节，那么后面的entry的prerawlen字段还得继续更新。
如果ziplist里面的每个entry加好都存储了253字节的内容，那么第一个entry内容的修改就会导致后续所有entry的级联更新。
未来发展
可能会被listpack（紧凑列表）代替
quickList（快速列表）
ziplist和linkedlist的混合体
图示
每个ziplist存储多少元素
quicklist内部默认单个ziplist长度为8k字节，超出了这个字节长度，就会起一个新的ziplist。ziplist的长度由配置list-max-ziplist-size决定
压缩深度
quicklist默认的压缩深度是0，也就是不压缩。实际压缩深度由配置参数list-compress-depth决定。为了支持快读的push/pop操作，queicklist的首尾两个ziplist不压缩，此时深度为1。如果深度为2，就表示quicklist首尾第一个ziplist以及首尾第二个ziplist都不压缩。
Skiplist（跳跃链表）
类似于跳表的结构，不同点如下
图示
查找过程
类似于跳表
随机层高
对于新插入节点，都需要调用一个随机算法给他分配一个合理的层高，每层晋升概率大概是50%.
redis标准源码中晋升概率只有25%，相对官方跳跃链表更加扁平化。
插入过程
首先我们在搜索合适的插入点的过程中将[搜索路径]摸出来了，然后就可以开始创建新节点了，创建的时候需要给这个节点随机分配一个层数，再将搜索路径上的节点和这个新节点通过向前向后指针串起来。如果分配的新节点的高度高于当前跳跃列表最大高度，就要更新一下跳跃列表的最大高度。
更新过程
当我们调用zadd方法时，如果对应的value不存在，就是插入过程。如果value已经存在了，只是调整一下score值，就是更新过程。如果score值不会带来排序位置改变，那么更新就能返回。（该逻辑已经被redis官方接受）如果排序位置改变了，就需要调整位置。
调整位置
简单的策略就是先删除值，再插入这个元素，需要经过两次路径搜索。
如何计算排名
redis在skiplist的forward指针上进行了优化，给每个forward指针都增加了span属性，span是跨度的意思，表示从前一个节点沿着当前层的forward指针跳到当前这个节点中间会跳过多少个节点。redis在插入删除操作时会更新span值。这样在计算一个元素的排名时，只需要将搜索路径上进过的所有节点span值进行叠加，就可以计算出元素的最终rank值。
