之前以Epoll模式说明了redis在处理网络io层面的高性能原理
本篇从redis底层数据结构层面继续研究为了达到高性能，redis做了那些设计。

一.字符串
redis没有直接使用c语言的字符串，自定义了一套叫做 simple dynamic string简称SDS的抽象类型。
以github代码https://github.com/antirez/redis/blob/unstable/src/sds.h为例
其包含一个header，比如sdshdr64定义如下

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used 即字符串的长度*/
    uint64_t alloc; /* excluding the header and null terminator 即字符串最大容量，去掉header和最后的空字符*/
    unsigned char flags; /* 3 lsb of type, 5 unused bits 一共8bit，低位的3比特表示header类型，一共5种*/
    char buf[];//真正保存字符串的数组。
}

与传统的c字符串相比，redis定义的sds由于哪些优势呢？

1.传统的c字符串没有记录自身长度，获取字符串的长度需要遍历整个字符串，遇到结尾的空字符为止，时间复杂度为O(n）;
那么sds数据结构中，有记录len，时间复杂度为O(1);
2.c字符串在进行字符串拼接等操作时，可能由于预先没有分配足够的内存，导致缓冲区溢出。而sds在进行相应操作的时候，会预先检查空闲空间是否足够，如果不够，先拓展sds空间。
3.同样sds由于一个空闲空间的预留，在增长或者缩短字符串时，不一定必须进行内存重分配。c的字符串就需要这么做
4.c字符串会以空字符标示是否结束，造成二进制不安全。而sds有len这个属性，不必根据空字符来判断是否结束，二进制安全

二.链表
代码见git https://github.com/antirez/redis/blob/unstable/src/adlist.h

typedef struct list {
    listNode *head; //头节点
    listNode *tail; //尾节点
    void *(*dup)(void *ptr);//复制节点保存的值
    void (*free)(void *ptr); //释放节点保存的值
    int (*match)(void *ptr, void *key);//对比节点保存的值与给定值
    unsigned long len; //长度
} list;

这个链表数据结构的特点，取头节点，尾节点，链表长度的时间复杂度都是O(1)

三。字典
底层与hashmap类似，是个数组加链表的数据结构。特点是rehash时，会保留两个hash表。渐进式的rehash，新加的元素都在新表中，老表逐渐的将元素rehash到新表中，最终成为空表。

四 跳跃表 用来形成有序集合

五 整数集合

六 压缩列表