第一部分 数据结构与对象
第二章 简单动态字符串
Redis没有使用C语言的char数组的方式来存储字符串，而是自己定义了一个简单动态字符串结构体类型SDS(simple dynamic string),
struct sdshdr { int len;//字符串长度 int free;//剩余使用空间,也就是buf数组中未使用的字节数 char buf[];//字节数组，用于保存字符串 }
在上面例子中，使用SDS保存了字符串Redis，SDS的情况如下： ·free属性的值为0，表示这个SDS没有分配任何未使用空间。 ·len属性的值为5，表示这个SDS保存了一个五字节长的字符串。 ·buf属性是一个char类型的数组，数组的前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存了空字符'\0'。”遵从结尾使用空字符这一惯例的好处是，SDS可以直接重用一部分C字符串函数库里面的函数。
SDS 与 C字符串的区别
1.可以使用常数级别的时间复杂度获取字符串长度 因为SDS结构体使用len变量保存长度，而C语言字符串需要遍历字符数组获取长度 2.防止缓冲区溢出 因为C语言字符串不记录自身长度，拼接时是直接将字符串拼接在字符串后面，所以后面如果有其他字符串的话，会把其他字符串的内容覆盖。如果后面是不可写的内存，则会报错。如果SDS，拼接时会判断长度，长度不够会进行扩容。 3.减少修改字符串带来的内存重分配次数 对于C语言字符串，底层是一个N+1的字符数组，是用多少，分配多少，所以字符串的拼接和截断都会导致内存重分配。
对于SDS，进行扩容时，会多分配空间以减少内存重分配的次数。 当使用长度len<1MB时，分配的总空间为len+len+1，也就是剩余空间为与使用长度相同，再加上额外1字节保存空字符 当使用长度len>1MB时,分配的总空间为len+1MB+1，也就是剩余空间为1MB，再加上额外1字节保存空字符
SDS进行字符串截断时，会延迟字符串剩余空间的释放时机 字符串进行截断后，程序并不立即进行内存重分配来回收多余的字节，而是使用free变量进行记录，将空间闲置，便于以后使用，当然也可以显式调用函数对空间进行释放
4.SDS可以保存二进制数据 C字符串中的字符必须符合某种编码（比如ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
5.兼容部分C字符串函数 因为遵循C字符串以空字符结尾的惯例，所以可以使用部分C字符串函数
#####第3章 链表 因为C语言没有提供链表的实现，所以Redis自己实现了链表。 //链表的数据结构
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
//链表节点的数据结构
typedef struct listNode { struct listNode *prev;//指向前一个节点的指针 struct listNode *next;//指向后一个节点的指针 void *value;//节点保存的值 }listNode
这是一个包含三个节点的链表 
Redis中的链表具备以下特点： 双端：每个节点保存了指向前后两个节点的指针 无环：表头节点的prev为NULL，表尾节点的next为NULL 有表头指针和表尾指针 记录了链表长度 多态：链表节点listNode使用指针void *保存节点的值，而链表list使用dup、free和match指针来根据链表中存放的对象的不同从而实现不同的方法。
###字典 字典是一种用于保存键值对的抽象数据结构。因为C语言没有提供字典的实现，所以Redis使用哈希表实现了字典这种数据结构。 下图为一个空的哈希表示意图： 
下图是普通状态(非rehash期间)下，保存了两个键值对的字典： 
哈希表节点的数据结构如下：
typedef struct dictEntry { //键 void *key; //值，可以是一个指针，也可以是一个uint64_t整数，也可以是int64_t的整数 union { void *val; uint64_tu64; int64_ts64; } v； //指向下一个节点的指针 struct dictEntry *next; } dictEntry；
Redis使用的哈希表数据结构如下：
typedef struct dictht { //哈希表数组，每个元素存储的是哈希表节点链表 dictEntry **table; //哈希表大小，也就是table数组的大小 unsigned long size; //哈希表大小掩码，总是等于size-1,用于计算哈希表节点在table中存储的位置 usigned long sizemask; //当前存储的节点总数 unsigned long used; } dictht;
Redis字典的数据结构如下：
typedef struct dict { //类型特定函数，type是一个指向dictType结构的指针，每个dictType保存了一系列用于操作特定类型键值对的函数，不同的字典会有不同的类型特定函数 dictType *type; //私有数据，privatedata保存了一些需要传给类型特定函数的可选参数 void *privatedata; //哈希表数组，ht是一个数组，保存了两个哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。 dictht ht[2]; //rehash索引，当不进行rehash时，值为-1 int rehashindex; }
类型特定函数的数据结构
typedef struct dictType { // 计算哈希值的函数 unsigned int (*hashFunction)(const void *key); // 复制键的函数 void *(*keyDup)(void *privdata, const void *key); // 复制值的函数 void *(*valDup)(void *privdata, const void *obj); // 对比键的函数 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 销毁键的函数 void (*keyDestructor)(void *privdata, void *key); // 销毁值的函数 void (*valDestructor)(void *privdata, void *obj); } dictType;
哈希算法
当要将一个新的键值对添加到字典里面时，Redis先根据键值对的键计算出哈希值，
hash = dict->type->hashFunction(key);
然后根据哈希值计算得到索引值
index = hash & dict->ht[x].sizemask;
再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
解决键冲突
Redis的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。
rehash（扩容和收缩）
为了让哈希表的负载因子（load factor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。 扩展和收缩哈希表的工作可以通过执行rehash（重新散列）操作来完成，Redis对字典的哈希表执行rehash的步骤如下： 1.为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）： (1) 如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂； (2) 如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂； 2.将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。 3.当ht[0]包含的所有键值对都迁移到了ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。
哈希表扩展和收缩的触发条件
扩展操作： 1.服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。 2.服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。 Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。 收缩操作： 当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。
渐进式rehash
当键值对比较多时，如果要一次性完成rehash那么会对性能产生影响，所以可以分多次，渐进式地完成rehash操作。 哈希表渐进式rehash的详细步骤： 1）为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。 2）在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash工作正式开始。 3）在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成之后，程序将rehashidx属性的值增一。 4）随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash至ht[1]，这时程序将rehashidx属性的值设为-1，表示rehash操作已完成。 渐进式rehash的好处在于它采取分而治之的方式，将rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash而带来的庞大计算量。
第5章 跳跃表
跳跃表是一种有序数据结构，通过在每个节点中维持多个指向它3前面节点的指针，来达到快速访问节点的目的。Redis在两个地方用到了跳跃表，一个是在实现有序集合键时，当一个有序集合的元素数量比较多或者元素的成员是比较长的字符串时，会采用跳跃表作为有序集合键的底层实现。一个是在集群节点中用作内部数据结构。 
上图是一个跳跃表，最左边的是zskiplist结构，用于保存跳跃表相关的信息，包含以下属性：
typedef struct zskiplist { // 表头节点和表尾节点 structz skiplistNode *header, *tail; // 表中节点的数量，头结点不计算在内 unsigned long length; // 表中层数最大的节点的层数 int level; } zskiplist;
位于zskiplist结构右方的是四个zskiplistNode结构，该结构包含以下属性：
typedef struct zskiplistNode { // 层，level是一个数组，在创建跳跃表节点的时候，程序都根据幂次定律（power law，越大的数出现的概率越小）随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的“高度” struct zskiplistLevel { // 前进指针:用于访问位于表尾方向的其他节点 struct zskiplistNode *forward; // 跨度:当前节点和前进指针所指向节点的距离 unsigned int span; } level[]; // 后退指针：指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。 struct zskiplistNode *backward; // 分值，跳跃表所有节点都是按照分值从小到大排序的，分值相同时，则按照成员对象在字典序中的大小进行排序 double score; // 成员对象，每个节点所保存的成员对象都是唯一的 robj *obj; } zskiplistNode;
跳跃表遍历过程： 
1）迭代程序首先访问跳跃表的第一个节点（表头），然后从第四层的前进指针移动到表中的第二个节点。 2）在第二个节点时，程序沿着第二层的前进指针移动到表中的第三个节点。 3）在第三个节点时，程序同样沿着第二层的前进指针移动到表中的第四个节点。 4）当程序再次沿着第四个节点的前进指针移动时，它碰到一个NULL，程序知道这时已经到达了跳跃表的表尾，于是结束这次遍历。
