redis中使用的数据结构有:
dict 字典,就是个哈希表,实现和HashMap类似,不做阐述;不同的是在哈希表resize()的时候是分步执行的,后续篇幅再说明。
sds 很多项目都对自己的字符串进行了封装,作用类似于leveldb的slice。
linkedlist 双端链表，迭代器的实现是通过链表的pre和next实现的，是个BidirctionalIterator。代码中只实现了ForwardIterator的功能。
zipmap 已不再使用了
inset 一个紧致的有序整型数组。
ziplist 也是一个链表，但是它的内存是连续的，在数据量小的时候使用，增长到一定的大小会转化成list或者skiplist
skiplist 跳跃表，实现在t_zset.c中
本文只阐述inset，ziplist，skiplist三种数据结构。
1.ziplist
直接借用代码注释上ziplist的存储结构：
/*
area |<---- ziplist header ---->|<----------- entries ------------->|<-end->|
size 4 bytes 4 bytes 2 bytes ? ? ? ? 1 byte
+---------+--------+-------+--------+--------+--------+--------+-------+
component | zlbytes | zltail | zllen | entry1 | entry2 | ... | entryN | zlend |
+---------+--------+-------+--------+--------+--------+--------+-------+
^ ^ ^
address | | |
ZIPLIST_ENTRY_HEAD | ZIPLIST_ENTRY_END
|
ZIPLIST_ENTRY_TAIL
- zlbytes 记录了整个ziplist占用的内存大小；
- zltail 记录尾节点的相对于ziplist实例指针的偏移量；
- zllen 是整个list的节点数量的无符号数，占2个字节，可以最大表示2**16-1，实际使用保留了0xffff ffff ,即大于等于这个数的时候，已经不能通过此值来取得节点的数量了；
- zlend 固定为0xff。
- entry 的结构并不是代码中给的结构体zlentry。而是如下结构:
size 1/5 bytes 1/2/5 bytes ?
+---------------+---------------+-------+
component | pre_entry_len | cur_entry_len | value |
+---------------+---------------+-------+
这是个变长的结构，pre节点小于254则pre_entry_len占用1字节，否则5字节,为什么不是255字节呢？255会和zlend产生冲突；cur_entry_len中包含了编码信息（以字符串编码还是数字，数字编码能减少内存长度)和本节点的长度信息,数字格式编码固定占用1字节；字符串格式编码数据小于127字节占1字节，小于0x3fff 占用2字节，否则5个字节。
因此ziplist有如下特点:
- 内存连续，数据紧凑。
- 查找效率o(n)
- 双端查询，可前后遍历，类似于nodelist.
了解了数据结构，思考下如何对其增加一个节点p，p的大小为sp。
- 1.ziplist长度发生变化，zlbytes要增加entry的内存大小；
- 2.zltail也要做相应改变，如果插入的是尾节点，则zltail等于ziplist到新节点p的距离，否则是原值加上新节点p的长度。
- 3.内存大小发生改变，需要realloc个更大的内存。
- 4.对于在新节点以后的节点，后移sp个单位。接下来要更新p以后的节点内容:
- 4.1如果p的前一个节点的长度和p节点的长度一样长，那么皆大欢喜。只需要更新p节点后一个节点的pre_entry_len值；
- 4.2如果比p节点的长度大(5字节对1字节)，也ok，存下来，浪费4个字节内存。
- 4.3如果比p节点的长度小(1字节对5字节)，意味着p以后的节点长度会发生变化，增加4个字节来存储p的长度，zltail和ziplist也要同时加4;同时由于p->next节点长度发生变化，p->next->next也要去做一次判断，需要重复步骤4，直到不满足4.3的情况为止。
经过以上步骤，就可以大概还原redis中的代码实现了，也可以看出来ziplist的增删代价是很大的，改变一个节点的复杂度最差是（n^2);一个节点改动，可能牵一发而动全身，所以ziplist是不适合大数据量的存储的。
2.inset
inset 实际是一个整数数组，结构如下:
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
其中encoding是编码方式，有16位，32位，64位三种取值；length是inset集合中保存的元素个数，contents为保存的数据。下面是inset的特点和实现方式.
1.初始化的inset是16位编码的，如果inset里面只保存了16位的数字，那么这个编码方式将保持不变。
2.inset是有序不重复的，从小到大排列，每次插入/删除会触发inset的大小调整,length+1。
3.如果插入了比当前编码范围更大的数字，会触发intsetUpgradeAndAdd()，下面以16位-> 32位扩展为例。
3.1 重新调整contents大小，大小为原(size+1)*2，更新encoding的值为INTSET_ENC_INT32;
3.2 新数字肯定是位于数组开头或者结尾，如果是在结尾，将原数组的每个数从原位置pos移到pos2的位置，否则是(pos+1)2；
3.3 插入新的数据，intsetUpgradeAndAdd()过程结束
4.删除不改变inset的编码方式，即如果原inset为32位，删光了inset里的16位不能表示的数字以后，inset也不会恢复到16位，代价太大，即intsetUpgradeAndAdd()的过程是不可逆的。
5.在inset中查找一个数采用二分查找。
根据这些特点，写出inset的实现，想必不难，inset的特点是在存储的数据为小值的时候，占用的内存较小，但是只要插入了一个64位的数据，那么inset就没有优势了，插入和删除的时间复杂度都是o(n)，因此不适合做大数量的存储。
3.skiplist
跳表是一个特殊的有序链表，盗一张网图吧。
结构如下
typedef struct zskiplist {
// 表头节点和表尾节点
struct zskiplistNode *header, *tail;
// 表中节点的数量
unsigned long length;
// 表中层数最大的节点的层数
int level;
} zskiplist;
节点的结构
typedef struct zskiplistNode {
// 成员对象
robj *obj;
// 分值
double score;
// 后退指针
struct zskiplistNode *backward;
// 层
struct zskiplistLevel {
// 前进指针
struct zskiplistNode *forward;
// 跨度
unsigned int span;
} level[];
} zskiplistNode;
简述下跳表的特点
- 跳表是一个排序链表，redis中以score的大小做排序，增删改查的效率均是o(logn)，由于其实现更易于理解和实现而被广泛使用。
- 跳表是不稳定的，即同样是创建一个跳表，插入若干相同的值，内部的数据结构可能是不一致的。
- 每个节点的大小不固定，不固定的原因是节点的拥有的forward指针个数不定，这个数值是在节点创建的时候随机选取的一个正整数，redis实现默认最大层数是32。
- redis中的跳表增加了一个指向前节点的backward来往前遍历;一个span，用于计算forward节点和本节点中间的跨度，以方便zcount等命令来计算范围内score的数量。
如何插入一个数据?redis排序顺序是从头到尾，按照score从小到大。如果要增加一个值，首先需要确定插入后的顺序，假设跳表为skl ，新节点为n。
- 找到每一层比新节点score小，而且距离最近的节点，保存为update[]。
- 随机产生新节点的层高，对每一层的forward节点复制，令n->level[i]->forward = update[i]->level[i]->forward，给新节点的所有forward指针赋值。令update[i]->forward = n使新节点和其所有前置节点关联;实际上和双向链表操作类似。
如何查找一个节点p?
场景1.根据score范围查找内容，对应zrange命令。查找左界和右界，中间的范围及所求。左界和右界算法类似，从head的顶层forward节点开始，如果比p的score小，那么让head = forward 继续此步骤.如果等于score那么返回。如果小于那么代表需要找的左界在head和forward之间，跳到下一层重复此步骤。
场景2.根据内容查找score，对应zscore命令。redis不查找skiplist，而是额外使用了个hash表来达到o(1)的效率。
迭代器如何设计?
- 可知n->level[0]->forward的步长是1，循环forward可以遍历整个跳表。
推荐跳表的leveldb版实现。
综上，redis的数据结构分析告一段落。
