Redis设计与实现阅读总结（一）数据结构和对象
最近团队几个人和我聊了下，加上我自己平时的反思，我发现自己问题确实很多
其中一个问题就是，自己学习东西没有系统性，没有总结
这次的博客算是一个总结的开始。
最近由于出实习题，趁着这个机会，自己阅读了《redis设计与实现》这本书
为了解决自己的毛病，准备围绕这个话题写博文，做总结，从细节到总体，围绕这个话题写更多东西
大家可能发现这个部分写的很粗略，因为redis本身设计的就是很简单的，这些数据结构基本没有太多好写的，主要是写了后做一个总结，后面的更为重要的部分会做更多叙述
1. SDS(简单动态字符串)
每个 sds.h/sdshdr 结构表示一个 SDS 值：
struct sdshdr {// 记录 buf 数组中已使用字节的数量// 等于 SDS 所保存字符串的长度int len;// 记录 buf 数组中未使用字节的数量int free;// 字节数组，用于保存字符串char buf[];};
为什么不使用c语言简单字符串
原因有如下
- 获取长度复杂度为O(1)
- 避免缓冲区溢出
优化策略
redis非常注重性能，于是优化是非常必要的。
减少内存重分配
- 空间预分配
内存的分配设计到复杂算法或可能的系统调用，比较耗时
于是，每次再字符串增长操作时，不仅仅会扩容到刚好所需的空间，而是会通过一定策略额外分配空间
- 惰性空间释放
字符串的缩短操作，不会进行内存重分配，而是会通过free记录起来，为未来可能存在的增长提供优化
二进制安全
不使用\0辨认结尾，而是通过len
并且在SDS中\0被保留，可以兼容部分c字符串函数
2. 链表
redis是一个设计追求简单的数据库，链表这种简单实用的数据结构在很多地方都得到了应用，（事实上应该说是双向链表。）
譬如 列表(List)，慢查询，监视器，订阅与发布等。包括客户端状态也是用链表在服务器中进行保存的。
结构
typedef struct listNode {// 前置节点struct listNode *prev;// 后置节点struct listNode *next;// 节点的值void *value;} listNode;
3. 字典
字典是使用哈希表作为底层实现。
一图胜千言
看的出来，解决键冲突(collision)的办法是通过每个哈希表节点都是一个链表。(链地址法)
- 哈希算法
- 链地址法
以上两者细节就不解释了
rehash扩容
要扩多少内容，开多大空间的新dictEntry，然后把之前的dictEntry转到新的。
当然，一次性转会有性能问题，所以
渐进式rehash
相当于是搭便车
每次对字典进行更新添加查找删除操作时，会顺带的转移旧的dictEntry的一个index链表到新的dictEntry
详细执行过程不予介绍
4. 跳跃表（跳表）
跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。
跳跃表支持平均 O(\log N) 最坏 O(N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。
在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。
Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现
从上图可以看书，跳表其实就是一种分治思想的，利用空间换取时间的一种算法
在看了上图之后，这个时候再看下图redis的跳表。就应该容易理解多了
整数集合
整数集合就比较简单了，重要的一个点主要是升级
redis的整数集合类型其实是会随着存入数字而变化的，当数都比较小的时候，类型可能就是int8_t,int16_t，但是一旦加入一个大数，集合会升级类型为相应类型，此时该集合中所有数都会被更新为该类型
另外注意
整数集合的数组不会出现降级
