一，概述
本文主要简单介绍下redis的主要数据结构，分别是动态字符串、链表、字典、跳跃表、整数集合、压缩列表。
二，简单动态字符串
redis自己构建了一个名为简单动态字符串（simple dynamic string，SDS）的抽象类型。SDS作为redis的默认字符串，在redis的数据库里，包含字符串值的键值对在底层都是由SDS实现的。
free：bug数组中未使用字节数量。
len：SDS所保存字符串长度。
buf：char类型数组，以空字符 '\0' 结尾。
空字符的1字节，不计算入len长度，由于redis本身是有C语言编写，加空字符结尾是为了使用C语言字符串的特性，同时又比C语言字符串多了len和free属性，比如获取字符串长度，C语言需要去遍历字符串直到空字符结尾，而SDS直接获取len属性即可，复杂度仅为O(1)。
SDS相比C字符串另一个好处是，它的空间分配策略杜绝了缓冲区溢出，SDS的空间分配策略，解除了字符串长度和底层数组间的关联，也就是在SDS中，buf的长度并不一定是字符串长度。
空间预分配：用于优化SDS的字符串增长操作。
当字符串变长后，如果变更后的长度小于buf长度，那么不会重新分配内存空间，若变更后的长度大于buf长度，那么就需要内存重新分配空间，这时，若len属性的值小于1MB，那么程序分配和len属性值同样大小的未使用空间，这时len属性值和free属性值相同，即变更后的buf长度，等于len +free + 1的值；若变更后len属性值大于等于1MB，那么程序会分配1MB的未使用空间。
惰性释放空间：用于优化SDS字符串缩短操作。
当SDS缩短字符串长度时，内存并不会马上释放多余空间，而是会以free记录的形式将数量记录起来，可以等待后续扩展字符串使用。
三，链表
redis使用链表作为列表键的底层实现，除了列表键之外，发布与订阅、慢查询、监视器等功能也用到了链表。
由多个listNode组成的双端链表
代码：
typedef struct listNode{
struct listNode *prev；//前置节点
struct listNode *next；//后置节点
void *value；//节点的值
}listNode
redis使用list来持有listNode链表：
代码：
typedef struct list{
listNode *head；//表头节点
listNode *tail；//表尾节点
unsinged long len；//链表所包含的节点数量
void *(*dup) (void *ptr)；//节点值复制函数
void (*free) (void *ptr)；//节点值释放函数
int (*macth) (void *ptr,void *key)；//节点值对比函数
}list
链表特性：
1，双端：链表节点带有 prev和next指针，获取某个节点的前置节点和后置节点的复杂度为o(1)。
2，无环：表头节点指针和表尾节点指针都指向null，对链表的访问以null为终点。
3，带表头指针和表尾指针：通过list结构的head和tail，程序获得表头节点指针和表尾节点指针复杂度为o(1)。
4，带链表长度计数器：len属性对list持有的链表节点进行计数，程序获取链表节点数量复杂度为o(1)。
5，多态：链表节点使用void* 指针来保存节点值，并可通过list结构的dup，free，match三个属性节点设置特定函数。
四 字典
redis的数据库使用字典来作为底层实现，对数据库的增、删、改、查操作也是构建在对字典的操作上。
除了用来表示数据库之外，字典还是哈希键的底层实现之一，redis的字典使用哈希表作为底层实现。
哈希表：
typedef struct dictht{
dictEntry **table；//哈希表数组
unsigned long size；//哈希表大小
unsigned long sizemask；//哈希表大小掩码，用户计算索引值，总是等于size-1
unsigned long used；//该哈希表已有节点数量
}dictht
哈希表节点：
typedef struct dictEntry {
void *key;//键
union{ //值
void *val;
uint64_tu64;
int64_ts64;
} v;
struct dictEntry *next；//指向下一个哈希表节点，形成链表
}dictEntry
字典：
typedef struct dict{
dictType *type；//类型特定函数
void *privdata；//私有数据
dictht ht[2]；//哈希表
int trehashidx；//rehash索引，当rehash不在进行时，值为-1
}dict
type：是一个指向dictType结构的指针。
privdata：保存需要传给特定函数的可选参数。
ht：两个数组，一般情况下只使用ht[0]哈希表，ht[10]哈希表用作扩展备份。
哈希算法：
根据字典dict的type，计算键key的哈希值，再使用哈希表的sizemask和刚计算的哈希值，计算出索引值，使用murmurhash2算法。
rehash：
负载因子 = ht[0].used / ht[0].size ；
服务器目前没有执行bgsave或者bgrewriteaof命令，负载因子大于等于1 ，即进行rehash扩展操作。
服务器目前正在执行bgsave或者bgrewriteaof命令，负载因子大于等于5，即进行rehash扩展操作。
另，负载因子小于0.1时，进行收缩操作。
rehash不是一次性全部扩展完成，而是渐进式的，
dict里的trehashidx值，就是渐进式rehash的进度计数器，trehashidx为0时，rehash开始，在rehash期间，每次对字典执行添加、删除、查找、更新操作时，程序除了指定操作外，还会顺带将ht[0]哈希表在trehashidx索引上的所有键值对rehash到ht[1]，rehash完成后，trehashidx加1，当所有ht[0]都rehash到ht[1]后，trehashidx置为-1。
五 跳跃表
跳跃表不做多介绍，redis只有少数几个地方用到了，一个是实现有序集合键，一个是集群节点中用作内部数据结构。
header：指向跳跃表的表头节点。
tail： 指向跳跃表的表尾节点。
level：记录跳跃表内，层数最大的那个节点的层数（表头节点层数不计算内）。
length： 跳跃表长度，即跳跃表节点数（表头节点不计算内）。
六 整数集合
整数集合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合的元素数量不多时，redis就会使用整数集合作为集合键的底层实现。
保存类型可以 int16_t，int32_t，int64_t 的整数值，集合中不会出现重复元素。
typedef struct inset{
uint32_t encoding；//编码方式
uint32_t length；//集合包含的元素数量
int8_t contexts[]；//保存元素的数组
}inset
contexts[] 数组是整数集合的 底层实现，整数集合的每个元素都是contexts数组的一个数组项，各个项在数组中按值的大小从小到大排列，并且不包含重复项。
七 压缩列表
压缩列表是列表键和哈希键的底层实现之一。
当列表键只包含少量列表项，并且每个列表项要么是小整数值，要么是长度比较短的字符串，那么redis会把压缩列表当做列表键的底层实现。
当哈希键只包含少量键值对，并且每个键值对的键和值要么是小整数值，要么就是长度比较短的字符串，那么redis会把压缩列表当做哈希键的底层实现。
压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
zlbytes：记录整个压缩列表占用的内存字节数，在对压缩列表进行内存重分配或者计算zlend的位置时使用。
zltail：记录压缩列表 表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，程序无需遍历整个压缩列表就可以确定表尾节点地址。
zllen：记录压缩列表包含的节点数量，当这个属性小于uint16_max(65535)时，这个属性的值就是包含的节点数量，当大于65535时，需要真实遍历才能计算得出。
entryX：列表节点。
zlend：特殊值oxff（十进制255），标记压缩列表末端。
previous_entry_length：字节为单位，长度为1字节或5字节。当前一节点长度小于254字节，previous_entry_length为1字节；当前一节点长度大于等于254字节，previous_entry_length为5字节，属性第一个子节被设置成OxFE，之后四个字节则保存前一节点长度。
encoding：记录节点content保存的数据类型及长度
content：保存节点的值
参考文献《redis设计与实现第二版》
