通过阅读《Redis设计与实现》黄健宏（机械工业出版社 ISBN9787111464747）一书，对Redis的设计有了更深刻的认识，在此整理下关键的知识点。
一、基本数据结构
1.简单动态字符串(SDS:simple dynamic string）
//数据结构
struct sdshdr {
//sds保存的字符串长度
int len;
//记录buf数组中未使用字节的数量:重要作用就是冗余部分字节，避免扩容时频繁申请内存带来的开销
int free;
//字节数组，保存真正的字符串
char buf[];
}
2.Redis的链表实现
//节点:双向链表
typedef struct listNode {
//前置节点
struct listNode * prev;
//后置节点
struct listNode * next;
//节点的值
void * value;
}listNode;
//list结构：记录头、尾指针，以及长度计数器len，便于操作链表
typedef struct list {
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表节点数量
unsigned long len;
//节点值复制函数
void *(*dup)(void *ptr); //使用函数指针便于扩展，不同的业务指定自己的实现
//节点值释放函数
void (*free)(void *ptr);
//节点值对比函数
void (*match)(void *ptr, void *key);
} list;
3.Redis的字典实现
Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对
//哈希表结构
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值，总是等于size-1。对数据的哈希值和sizemask作运算，确定数据应该存放在table的哪个索引上
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
} dictht;
//哈希表节点
typedef struct dictEntry {
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
} v;
//指向下个哈希表节点，形成链表,解决哈希冲突问题
struct dictEntry *next;
} dictEntry;
//dict结构
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht ht[2];//包含2项的数组，每个都是哈希表。字典使用ht[0],而ht[1]只在rehash的时候使用
//rehash索引,不在rehash状态时为-1
int rehashindex;
} dict;
typedef struct dictType {
//计算哈希值的函数
unsigned int (*hashFunction)(const void *key);
//复制键的函数
void *(*keyDup)(void *privdata, const void *key);
//复制值的函数
void *(*valDup)(void *privdata, const void *obj);
//对比键的函数
void (*keyCompare)(void *privdata, const void *key1, const void *key2);
//销毁键的函数
void (*keyDestructor)(void *privdata, void *key);
//销毁值的函数
void (*valDestructor)(void *privdata, void *obj);
} dictType;
对哈希表自动扩展的条件（负载因子=已保存节点数/哈希表大小）：
1)服务器当前没执行BGSAVE或者BGREWRITEAOF命令，且哈希表负载因子大于等于1
2）服务器在执行BGSAVE或BGREWRITEAOF命令，且哈希表负载因子大于等于5
4.跳跃表skiplist(用于实现有序集合和集群节点中的内部数据结构)
//跳跃表节点
typedef struct zskiplistNode {
//层,每个节点保存了该节点所分布的层次，以及在该层对应的前序指针，和层级之间的跨度
struct zskiplistLevel {
//前进指针,指向表尾方向，节点在该层的前进指针
struct zskiplistNode *forward;
//跨度,与下一层级的跨度
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
} zskiplistNode;
//zskiplist结构
typedef struct zskiplist {
//表头节点和表尾节点
struct zskiplistNode *header, *tail;
//表中节点的数量
unsigned long length;
//表中层数最大的节点的层数
int level;
} zskiplist;
一个五层带zskiplist的跳跃表
5.整数集合
//intset数据结构
typedef struct intset {
//编码方式
uint32_t encoding;//取值范围：INTSET_ENC_INT16,INTSET_ENC_INT32,INTSET_ENC_INT64
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];//实际类型以encoding的属性为准
} intset;
6.压缩列表ziplist
当一个[列表的列表项|哈希类型的键值对]很少，并且值要么都是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表作为[列表类型|哈希类型]的底层实现，节约内存
压缩列表整体结构
zlbytes:4字节空间，记录整个压缩列表的内存字节数
zltail:4字节空间，离起始地址的偏移量，无需遍历列表即可定位表尾地址
zllen:2字节空间，记录节点数，小于65535时数据准确，等于65535时存的已经不准确，需要遍历节点计算得出
entryX:列表节点，长度由内容决定
zlend:1字节，特殊值OxFF（255），标记列表末端
单个节点的结构
previous_entry_length:记录前一节点的长度。如果前一节点长度小于254字节，则此属性长度为1字节，记录了前一节点的长度；如果前一节点长度大于等于254字节，则该属性长度为5字节，其中第一字节为OxFE（254，为啥不是OxFF？因为这是结尾的特殊值），后续4字节保存具体的前一字节的长度
encoding:记录了content属性保存的数据类型和长度
content：节点的值
为节约内存而开发的顺序型数据结构
添加新节点或者删除节点，都可能导致连锁更新（连续空间依次被重新分配）
二、五种对象
以上的数据结构是Redis对象的具体底层实现，而Redis的五种对象类型（字符串、列表、哈希、集合、有序集合）是由一种或多种底层实现组合而成。
//对象的主要属性
typedef struct redisObject{
//类型
unsigned typpe:4;//REDIS_STRING,REDIS_LIST,REDIS_HASH,REDIS_SET,REDIS_ZSET
//编码
unsigned encoding:4;
//指向底层实现数据结构的指针
void *ptr;
//...其他
} robj;
encoding记录了对象使用的编码
每种对象可能有多种不同的编码（节约内存）
通过encoding属性设置对象使用的编码，提升了Redis的灵活性和效率，优化对象在不同场景下的效率
当同一个对象因为属性变化导致类型会发生变化时，Redis会自动更新对象的编码类型
1.字符串对象
可以是int、embstr或者raw类型编码
2.列表对象
可以是ziplist或者linkedlist编码
其中，满足以下两个条件的场景下会用ziplist编码：
其他场合下用linkedlist编码
另：使用ziplist编码的对象，当以上两条件不再满足时，会自动编码转换成linkedlist
3.哈希对象
可以是ziplist或者hashtable
4.集合对象
可以是intset或者hashtable
5.有序集合对象
可以是ziplist或者skiplist
typedef struct zset {
zskiplist *zsl;
dict *dict;
} zset;
6.其他