项目中用到了redis，但用到的都是最最基本的功能，比如简单的slave机制，数据结构只使用了字符串。但是一直听说redis是一个很牛的开源项目，很多公司都在用。于是我就比较奇怪，这玩意不就和 memcache 差不多吗？仅仅是因为memcache是内存级别的，没有持久化功能。而redis支持持久化？难道这就是它的必杀技？
带着这个疑问，我在网上搜了一圈。发现有个叫做huangz的程序员针对redis写了一本书叫做《redis设计与实现》，而且业界良心搞了一个reids2.6版本的注释版源码。这本书不到200页，估计2个星期能看完吧，之后打算再看下感兴趣部分的源码。当然，如果你不知道redis是干嘛的，请自行谷歌，简单说就是Key-Value数据库，而且 value 支持5种数据结构：
字符串
哈希表（map）
列表（list）
集合（set）
有序集
下面我们就从 redis 的内部结构开始说起吧：）
一、redis内部数据结构
首先需要知道，redis是用C写的。众所周知，任何系统对于字符串的操作都是最频繁的，而恰巧C语言的字符串备受诟病。然后作者就封装了一下 C 语言的字符串 char *。
总之，根据redis的业务场景，整个redis系统的底层数据支撑被设计为如下几种：
简单动态字符串sds(Simple Dynamic String)
双端链表
字典(Map)
跳跃表
下面我们就分别来说说这4种数据结构。
1. 简单动态字符串sds
redis的字符串表示为sds，而不是C字符串（以\0结尾的char*）
对比C字符串，sds有以下特性
可以高效执行长度计算O(1)
可以高效执行append操作(通过free提前分配）
二进制安全
sds会为追加操作进行优化，加快追加操作的速度，并降低内存分配的次数，代价是多占用内存，且不会主动释放
这个一看名字就能知道个大概了，因为字符串操作无非是增删查改，如果使用char[]数组，那是要死人的，任何操作都是O(N)复杂度。所以，要对某些频繁的操作实现O(1)级性能。但是我们还是得思考：
为什么要对字符串造轮子？
因为redis是一个key-value类型的数据库，而key全部都是字符串，value可以是集合、hash、list等等。同时，在redis的各种操作中，都会频繁使用字符串的长度和append操作，对于char[]来说，长度操作是O(N)的，append会引起N次realloc。而且因为redis分为client和server，传输的协议内容必须是二进制安全的，而C的字符串必须保证是\0结尾，所以在这两点的基础上开发sds
知道了上面几点就可以看下实现了，其实实现特别简单。它通过一个结构体来代表字符串对象，内部有个len属性记录长度，有个free用于以后的append操作，具体的值还是一个char[]。长度就不说了，只在插入的时候用一下，以后只需要维护len就可以O(1)拿到；对于free也很简单，vector不也是这么实现的嘛。就是按照某个阈值进行翻倍叠加。
2. 双端链表
redis自己实现了双端链表
双端链表主要两个作用：
作为redis列表类型的底层实现之一
作为通用数据结构被其他模块使用
双端链表及其节点的性能特征如下：
节点带有前驱和后继指针
链表是双向的，所以对表头和表尾操作都是O(1)
链表节点可以会被维护，LLEN复杂度为O(1)
这玩意当时刷数据结构与算法分析那本书看过，但是没怎么用到过。说白了双端链表就是有2个指针，一个指向链表头，一个指向链表尾。对每个节点而言，记录自己的父节点和子节点，这样双向移动速度会快很多。
还是老问题：
为什么要有双端链表？
在Java或者C++中，都有现成的容器供我们使用，但是C没有。于是作者自己造了一个双端链表数据结构。而这个也是redis列表数据结构的基础之一（另外一个还是压缩列表）。而且双端链表也是一个通用的数据结构被其他功能调用，比如事务。
至于实现也是比较简单，双端链表，肯定有2个指针指向链表头和链表尾，然后内部维护一个len保存节点的数目，这样当使用LLEN的时候就能达到O(1)复杂度了。其他的，额，对每个节点而言，都有双向的指针，另外还有针对双端链表的迭代器，也是两个方向。
3. 字典（其实说Map更通俗）
字典是由键值对构成的抽象数据结构
redis中的数据库和哈希键值对都基于字典实现
字典的底层实现为哈希表，每个字典含有2个哈希表，一般只是用0号哈希表，1号哈希表是在rehash过程中才使用的
哈希表使用链地址法来解决碰撞问题
rehash可以用于扩展或者收缩哈希表
对哈希表的rehash是分多次、渐进式进行的