因为项目中经常使用到Redis，所以楼主一直以来对redis的源码很感兴趣。前段时间忽然心血来潮，抽了点时间将Redis的源码过了一遍，主要包括多路复用和常用数据结构的底层实现部分，看的是C语言版本的Redis（虽然楼主是JAVA程序猿）。
应该说收益颇丰，尤其是redis对各种数据结构的实现，它的每个数据结构为各种不同的应用场景，做了特定的优化，譬如数据量大的时候结构怎么定义、数据量小的时候结构怎么定义、由于redis是单线程，在hash表rehash时还采用了渐进式的hash，诸如此类。
Redis为存储做的这些优化，充分解答了redis为何如此高效，以下是我对Redis常见数据结构的一些总结。
一、SDS(Simple Dynamic String) 简单动态字符串
SDS是redis最简单的数据结构
sds（简单动态字符串）特点，预先分配内存，记录字符串长度，在原字符串数组里新增加一串字符串。
新长度newlen为原len+addlen，若newlen小于1M，则为SDS分配新的内存大小为2*newlen；若newlen大于等于1M，则SDS分配新的内存大小为newlen + 1M
SDS是以len字段来判断是否到达字符串末尾，而不是以'\0'判断结尾。所以sds存储的字符串中间可以出现'\0'，即sds字符串是二进制安全的。
当要清空一个SDS时，并不真正释放其内存，而是设置len字段为0即可，这样当之后再次使用到该SDS时，可避免重新分配内存，从而提高效率。
SDS的好处就是通过预分配内存和维护字符串长度，实现动态字符串。
二、ADList(A generic doubly linked list) 双向链表
ADList就是个具有头尾指针的双向链表，没什么可以多说的，看一下结构体的定义
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;
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
三、skipList 跳表
Redis 使用跳跃表作为有序集合键的底层实现之一： 如果一个有序集合包含的元素数量比较多， 又或者有序集合中元素的成员（member）是比较长的字符串时， Redis 就会使用跳跃表来作为有序集合键的底层实现。
1.跳表描述
先看一下比较抽象的描述
1.跳表是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。
2.跳跃表支持平均 O(log N) 复杂度的节点查找， 还可以通过顺序性操作来批量处理节点。
3.在大部分情况下， 跳跃表的效率可以和平衡树相媲美， 并且因为跳跃表的实现比平衡树要来得更为简单， 所以有不少程序都使用跳跃表来代替平衡树。
这样的描述对数据结构理解不够深刻的同学或许难以理解，别着急，下面看楼主对跳表给出解释。
1.跳表本质是一个有序链表。（此刻你应想一下一个有序链表是怎样的）
2.跳表的查询、插入、删除的时间复杂度均为O(logn)，跟平衡二叉树的时间复杂度是一样的。
3.跳表是一种通过空间冗余来换取时间效率的数据结构。（怎么样的空间冗余的有序链表能换取更高的查询效率呢？）
下来看一下跳表的数据结构的示意图
注意观察示意图中圈起来的链表，它是有序的原始链表，存入跳表的数据，就存在这张链表中。那么上面额外的两条链表又是什么呢，他们有什么作用呢？
是的，上面的两条链表就是所谓的冗余空间，他们被称为跳表的索引，通过这样的冗余空间就可以在有序链表的基础上实现更高的查询效率。具体怎么提高查询效率的呢？
2.举个例子
譬如查询59这个元素，如果只有原始链表，你需要依次遍历14-23-34-43-50-59，总共6个节点，而通过上面2条链表，你将依次遍历14-50-59，总共3个节点。
这个例子已经说明了跳表通过冗余空间对查询效率的优化，但是我们还需要理论证明它带来的查询效率的优化对于所有case存在而不是仅仅某些特定的case。
3.跳表查询优化证明
跳表查询优化实际上利用了二分查找的思想，基于有序链表的二分查找。
观察跳表结构，从最底层开始，每隔一个或者两个节点向上抽取一个节点作为索引链表，当抽取到最顶层时，最终只剩两个元素。
查询时，从顶层链表开始将查询关键字与链表节点进行对比，逐层向下进行查找。
譬如查询59这个元素的过程如下：
对比59、14，发现59>14。
对比59、50，发现59>50.
50在顶层是最后一个元素，从50节点下降一层。
对比59、72，发现59<72.
即59>50且59<72，从50节点下降一层。
对比59、59，查找成功返回节点
通过这样的查找方式，优化了时间效率。
一般来说，跳表存储的关键字越多，跳表的冗余数据也会越多，跳表的层数也越高，并且，
实际上，到底隔多少个节点向上抽取一个节点并不是固定的。
若抽取节点的间距越大，则使用冗余空间越少，跳表总层数越小，查询效率越低 。
若抽取节点的间距越小（最小为1），则使用冗余空间越多，跳表总层数越大，查询效率越高。
这便是以空间换取时间。
4.跳表结构体c语言定义
跳表的示意图看起来很复杂，那么怎么用c语言实现跳表呢。其实，跳表的实现非常简单，看一下跳表结构体的基本定义。
struct skipList{
int lenth;
skipListNode* head;
}skiplist;
跳表结构体记录了存储的元素个数和跳表头节点。
struct skipListNode{
skipListNode* levelnext[3];
int currentlevel;
int totallevel;
int value;
}