简介：
Redis是一个key-value存储系统，在各种系统中的使用率越来越高，大部分原因是因为其高性能的特性。Redis拥有非常多的优势，读写性能高--100000次/s以上的读速度，80000次/s以上的写速度；Redis的所有操作都是单线程原子性的，支持丰富的特性，如支持订阅-发布模式，通知，设置key过期特性。
String(SDS)
上边设置key=msg，value=hello world的键值对，它们的底层存储是：键（key）是字符串类型，其底层实现是一个保存着“msg”的SDS。值（value）是字符串类型，其底层实现是一个保存着“hello world”的SDS。
SDS的结构
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
使用SDS的好处：
1.防止在改变某个字符串时缓冲区溢出。
2.减少扩展或收缩字符串带来的内存重分配次数
空间预分配，惰性空间分配
链表（list的实现方式之一）
链表是list的实现方式之一。当list包含了数量较多的元素，或者列表中包含的元素都是比较长的字符串时，Redis会使用链表作为实现List的底层实现。此链表是双向链表：
typedef struct listNode{
struct listNode *prev;
struct listNode * next;
void * value;
}
list结构
typedef struct list{
//表头节点
listNode * head;
//表尾节点
listNode * tail;
//链表长度
unsigned long len;
//节点值复制函数
void *(*dup) (void *ptr);
//节点值释放函数
void (*free) (void *ptr);
//节点值对比函数
int (*match)(void *ptr, void *key);
}
下面是list的数据结构图
字典
在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。
Redis本身的K-V存储就是利用字典这种数据结构的，value类型的哈希表也是通过这个实现的。
下面是哈希表的定义:
typedef struct dictht {
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码，用于计算索引值
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}
下面是dictEntry的数据结构
typeof struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}
struct dictEntry *next;
}
我们会发现这样会存在hash冲突，解决的办法是采用链地址法来解决hash冲突。
Redis在dictht的基础上，又抽象了一层字典dict.
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privedata;
// 哈希表
dictht ht[2];
// rehash 索引
in trehashidx;
}
扩充Rehash：随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过 rehash（重新散列）操作来完成。其实现方式和hashmap略有不同，因为dict有两个hash表dictht，所以它是通过这两个dictht互相进行转移的。
渐进式Rehash：在实际开发过程中，这个rehash 操作并不是一次性、集中式完成的，而是分多次、渐进式地完成的。采用渐进式rehash 的好处在于它采取分而治之的方式，避免了集中式rehash 带来的庞大计算量。详细步骤如下：
1.为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2.维持一个索引计数器变量rehashidx,并将它的值设置为0，表示rehash的开始。
3.在rehash进行期间，每次对字典执行CURD操作时，程序除了执行指定的操作以外，还会将ht[0]中的数据rehash到ht[1]表中，并且将rehashidx加一
4.当ht[0]中所有数据转移到ht[1]中时，将rehashidx设置成-1，表示rehash结束。
跳跃表
Redis 只在两个地方用到了跳跃表，一个是实现有序集合键（sorted Sets），另外一个是在集群节点中用作内部数据结构。
其实跳表主要是来替代平衡二叉树的，比起平衡树来说，跳表的实现要简单直观的多。跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速查找访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 ——查找、删除、添加等操作都可以在O（logn）期望时间下完成。
Redis 的跳跃表 主要由两部分组成：zskiplist（链表）和zskiplistNode （节点）
typedef struct zskiplistNode{
//层
struct zskiplistLevel{
//前进指针
struct zskiplistNode *forward;
//跨度
unsigned int span;
} level[];
//后退指针
struct zskiplistNode *backward;
//分值
double score;
//成员对象
robj *obj;
}
typedef struct zskiplist {
//表头节点和表尾节点
structz skiplistNode *header,*tail;
//表中节点数量
unsigned long length;
//表中层数最大的节点的层数
int level;
}zskiplist;
1.层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。level数组的每个元素都包含：前进指针：用于指向表尾方向的前进指针，跨度：用于记录两个节点之间的距离.
2.后退指针：用于从表尾向表头方向访问节点
3.分值和成员：跳跃表中的所有节点都按分值从小到大排序（按照这个进行排序的，也就是平衡二叉树（搜索树的）的节点大小）。成员对象指向一个字符串，这个字符串对象保存着一个SDS值（实际存储的值）
此文是对《redis设计与实现》总结
