话说：Redis六种数据结构
农历七月初七是七夕节，又名乞巧节、七巧节或七姐诞。相传农历七月七日夜或七月六日夜妇女在庭院向织女星乞求智巧，故称为“乞巧”。其起源于对自然的崇拜及妇女穿针乞巧，后被赋予了牛郎织女的传说使其成为象征爱情的节日。
眼想心思梦里惊,无人知我此时情。不如池上鸳鸯鸟,双宿双飞过一生。——尤袤
引导语
此篇主要对Redis中用到的数据结构做简单的描述，包括：结构定义、组成、应用和一些特性。(Redis2.9版本、在3.2版本之前变化不大)
简单动态字符串（Simple Dynamic Strings, SDS）是Redis的基本数据结构之一，用于存储字符串和整型数据。
struct sds {
int len; //buf中已占用字节数
int free; //buf中剩余可用字节数
char buf[]; //数据空间
};
底层实现：字节数组
这样设计的优点：
常数复杂度获取字符串长度：
有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。所需的复杂度O（1），这样确保获取字符串长度不会成为Redis的性能瓶颈。
杜绝缓冲区溢出：
与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题。
减少修改字符串时带来的内存重分配次数：
通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。
二进制安全：
由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。
通过使用二进制安全的SDS，而不是C字符串，使得Redis不仅可以保存文本数据，还可以保存任意格式的二进制数据。
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。（双端链表）
typedef struct listNode {
struct listNode * prev; //前置节点
struct listNode * next; //后置节点
void * value; //节点的值
}listNode;
组成：list结构和listNode结构。
特性总结：
多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O（1）。
带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O（1）。
带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O（1）。
应用：列表键、发布与订阅、慢查询、监视器。
字典又称散列表，是用来存储键值（key-value）对的一种数据结构。
typedef struct dict{
dictType * type; //类型特定函数
void * privdata; //私有数据
dictht ht[2]; //哈希表
in trehashidx; //rehash 索引；当rehash不在进行时，值为-1
} dict;
底层实现：哈希表。
哈希值算法：MurmurHash2。
解决键冲突：
渐进rehash：
在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。
应用：数据库、哈希键底层实现之一
跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
typedef struct zskiplistNode{
//层
struct zskiplistLevel {
struct zskiplistNode *forward; //前进指针
unsigned int span; //跨度
} level[];
struct zskiplistNode * backward; //后退指针
double score; //分值
robj * obj; //成员对象
} zskiplistNode;
组成：zskiplist和zskiplistNode。
特性：
每个跳跃表节点的层高都是1至32之间的随机数。
在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的。
跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序。
应用：有序集合键、集群节点内部数据结构（slots-keys）。
整数集合（intset）是一个有序的、存储整型数据的结构。
整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
typedef struct intset {
uint32_t encoding; //编码方式
uint32_t length; //集合包含的元素数量
int8_t contents[]; //保存元素的数组
} intset;
底层实现：数组。
特性：
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
整数集合只支持升级操作，不支持降级操作。
应用：集合键底层实现之一。
压缩列表ziplist本质上就是一个字节数组，是Redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。
· zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最多有232-1个字节。
· zllen：压缩列表的元素个数，占2个字节。zllen无法存储元素个数超过65535（216-1）的压缩列表，必须遍历整个压缩列表才能获取到元素个数。
· entryX：压缩列表存储的元素，可以是字节数组或者整数，长度不限。· entry的编码结构将在后面详细介绍。
· zlend：压缩列表的结尾，占1个字节，恒为0xFF。
特性：
添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。
应用：列表键和哈希键底层实现之一。
参考《Redis设计与源码分析》