本文内容思维导图如下：
一、简介和应用Rdis是一个由ANSIC语言编写，性能优秀、支持网络、可持久化的K-K内存数据库，并提供多种语言的API。它常用的类型主要是String、List、Hash、St、ZSt这5种
Rdis在互联网公司一般有以下应用:
String：缓存、限流、计数器、分布式锁、分布式Sssion
Hash：存储用户信息、用户主页访问量、组合查询
List：微博
st：sdscpy—O(n)
crat：sdsnw---O(1)
ln：sdsln---O(1)
常数复杂度获取字符串长度：因为SDS在ln属性中记录了长度，所以获取一个SDS长度时间复杂度仅为O(1)。
预空间分配：如果对一个SDS进行修改，分为一下两种情况：
SDS长度（ln的值）小于1MB，那么程序将分配和ln属性同样大小的未使用空间，这时fr和ln属性值相同。举个例子，SDS的ln将变成15字节，则程序也会分配15字节的未使用空间，SDS的buf数组的实际长度变成15+15+1=31字节（额外一个字节用户保存空字符）。
SDS长度（ln的值）大于等于1MB，程序会分配1MB的未使用空间。比如进行修改之后，SDS的ln变成30MB，那么它的实际长度是30MB+1MB+1byt。
惰性释放空间：当执行sdstrim（截取字符串）之后，SDS不会立马释放多出来的空间，如果下次再进行拼接字符串操作，且拼接的没有刚才释放的空间大，则那些未使用的空间就会排上用场。通过惰性释放空间避免了特定情况下操作字符串的内存重新分配操作。
杜绝缓冲区溢出：使用C字符串的操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的操作在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。
四、ListList对象的底层实现是quicklist（快速列表，是ziplist压缩列表和linkdlist双端链表的组合）。Rdis中的列表支持两端插入和弹出，并可以获得指定位置（或范围）的元素，可以充当数组、队列、栈等。
typdfstructlistNod{//前置节点structlistNod*prv;//后置节点structlistNod*nxt;//节点的值void*valu;}listNod;typdfstructlist{//表头节点listNod*had;//表尾节点listNod*tail;//节点值复制函数void*(*dup)(void*ptr);//节点值释放函数void(*fr)(void*ptr);//节点值对比函数int(*match)(void*ptr,void*ky);//链表所包含的节点数量unsigndlongln;}list;
rpush:listAddNodHad---O(1)
lpush:listAddNodTail---O(1)
push:listInsrtNod---O(1)
indx:listIndx---O(N)
pop:ListFirst/listLast---O(1)
lln:listLngth---O(N)
此结构比较像Java的LinkdList，有兴趣可以阅读一下源码。
从图中可以看出Rdis的linkdlist双端链表有以下特性：节点带有prv、nxt指针、had指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O（1）。ln属性获取节点数量也为O（1）。
与双端链表相比，压缩列表可以节省内存空间，但是进行修改或增删操作时，复杂度较高；因此当节点数量较少时，可以使用压缩列表；但是节点数量多时，还是使用双端链表划算。
.2ziplist（压缩列表）当一个列表键只包含少量列表项，且是小整数值或长度比较短的字符串时，那么rdis就使用ziplist（压缩列表）来做列表键的底层实现。
ziplist是Rdis为了节约内存而开发的，是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构；具体结构相对比较复杂，有兴趣读者可以看Rdis哈希结构内存模型剖析。在新版本中list链表使用quicklist代替了ziplist和linkdlist：
quickList是zipList和linkdList的混合体。它将linkdList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来。因为链表的附加空间相对太高，prv和nxt指针就要占去16个字节(6bit系统的指针是8个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。
quicklist默认的压缩深度是0，也就是不压缩。为了支持快速的push/pop操作，quicklist的首尾两个ziplist不压缩，此时深度就是1。为了进一步节约空间，Rdis还会对ziplist进行压缩存储，使用LZF算法压缩。
五、HashHash对象的底层实现可以是ziplist（压缩列表）或者hashtabl（字典或者也叫哈希表）。
Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1.哈希中元素数量小于个；2.哈希中所有键值对的键和值字符串长度都小于6字节。
hashtabl哈希表可以实现O(1)复杂度的读写操作，因此效率很高。源码如下：
typdfstructdict{//类型特定函数dictTyp*typ;//私有数据void*privdata;//哈希表dicththt[2];//rhash索引//当rhash不在进行时，值为-1intrhashidx;/*rhashingnotinprogrssifrhashidx==-1*///目前正在运行的安全迭代器的数量intitrators;/*numbrofitratorscurrntlyrunning*/}dict;typdfstructdictht{//哈希表数组dictEntry**tabl;//哈希表大小unsigndlongsiz;//哈希表大小掩码，用于计算索引值//总是等于siz-1unsigndlongsizmask;//该哈希表已有节点的数量unsigndlongusd;}dictht;typdfstructdictEntry{void*ky;union{void*val;uint6_tu6;int6_ts6;}v;//指向下个哈希表节点，形成链表structdictEntry*nxt;}dictEntry;typdfstructdictTyp{//计算哈希值的函数unsigndint(*hashFunction)(constvoid*ky);//复制键的函数void*(*kyDup)(void*privdata,constvoid*ky);//复制值的函数void*(*valDup)(void*privdata,constvoid*obj);//对比键的函数int(*kyCompar)(void*privdata,constvoid*ky1,constvoid*ky2);//销毁键的函数void(*kyDstructor)(void*privdata,void*ky);//销毁值的函数void(*valDstructor)(void*privdata,void*obj);}dictTyp;
上面源码可以简化成如下结构：
这个结构类似于JDK7以前的HashMapString,Objct，当有两个或以上的键被分配到哈希数组的同一个索引上时，会产生哈希冲突。Rdis也使用链地址法来解决键冲突。即每个哈希表节点都有一个nxt指针，多个哈希表节点用nxt指针构成一个单项链表，链地址法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位。
Rdis中的字典使用hashtabl作为底层实现的话，每个字典会带有两个哈希表，一个平时使用，另一个仅在rhash（重新散列）时使用。随着对哈希表的操作，键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内，Rdis会对哈希表的大小进行扩展或收缩（rhash），也就是将ht里面所有的键值对分多次、渐进式的rhash到ht里。
六、StSt集合对象的底层实现可以是intst（整数集合）或者hashtabl（字典或者也叫哈希表）。
intst（整数集合）当一个集合只含有整数，并且元素不多时会使用intst（整数集合）作为St集合对象的底层实现。
typdfstructintst{//编码方式uint32_tncoding;//集合包含的元素数量uint32_tlngth;//保存元素的数组int8_tcontnts[];}intst;
sadd:intstAdd---O(1)
smmbrs:intstGtO(1)---O(N)
srm:intstRmov---O(N)
sln:intstln---O(1)
intst底层实现为有序，无重复数组保存集合元素。intst这个结构里的整数数组的类型可以是16位的，32位的，6位的。如果数组里所有的整数都是16位长度的，如果新加入一个32位的整数，那么整个16的数组将升级成一个32位的数组。升级可以提升intst的灵活性，又可以节约内存，但不可逆。
7.ZStZSt有序集合对象底层实现可以是ziplist（压缩列表）或者skiplist（跳跃表）。
当一个有序集合的元素数量比较多或者成员是比较长的字符串时，Rdis就使用skiplist（跳跃表）作为ZSt对象的底层实现。
typdfstructzskiplist{//表头节点和表尾节点structzskiplistNod*hadr,*tail;//表中节点的数量unsigndlonglngth;//表中层数最大的节点的层数intlvl;}zskiplist;typdfstructzskiplistNod{//成员对象robj*obj;//分值doublscor;//后退指针structzskiplistNod*backward;//层structzskiplistLvl{//前进指针structzskiplistNod*forward;//跨度---前进指针所指向节点与当前节点的距离unsigndintspan;}lvl[];}zskiplistNod;
zadd---zslinsrt---平均O(logN),最坏O(N)
zrm---zsldlt---平均O(logN),最坏O(N)
zrank--zslGtRank---平均O(logN),最坏O(N)
skiplist的查找时间复杂度是LogN，可以和平衡二叉树相当，但实现起来又比它简单。跳跃表(skiplist)是一种有序数据结构，它通过在某个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。
作者：我叫刘半仙
来源：