所在的位置：数据结构 >> 核心技术 >> Redis为何这么快关键在于它的数据

Redis为何这么快关键在于它的数据

本文内容思维导图如下：

来源：　　set：sdscpy—O(n)

　　create：sdsnew---O(1)

　　len：sdslen---O(1)

常数复杂度获取字符串长度：因为SDS在len属性中记录了长度，所以获取一个SDS长度时间复杂度仅为O(1)。

预空间分配：如果对一个SDS进行修改，分为一下两种情况：

SDS长度（len的值）小于1MB，那么程序将分配和len属性同样大小的未使用空间，这时free和len属性值相同。举个例子，SDS的len将变成15字节，则程序也会分配15字节的未使用空间，SDS的buf数组的实际长度变成15+15+1=31字节（额外一个字节用户保存空字符）。

SDS长度（len的值）大于等于1MB，程序会分配1MB的未使用空间。比如进行修改之后，SDS的len变成30MB，那么它的实际长度是30MB+1MB+1byte。

惰性释放空间：当执行sdstrim（截取字符串）之后，SDS不会立马释放多出来的空间，如果下次再进行拼接字符串操作，且拼接的没有刚才释放的空间大，则那些未使用的空间就会排上用场。通过惰性释放空间避免了特定情况下操作字符串的内存重新分配操作。

杜绝缓冲区溢出：使用C字符串的操作时，如果字符串长度增加（如strcat操作）而忘记重新分配内存，很容易造成缓冲区的溢出；而SDS由于记录了长度，相应的操作在可能造成缓冲区溢出时会自动重新分配内存，杜绝了缓冲区溢出。

四、List

List对象的底层实现是quicklist（快速列表，是ziplist压缩列表和linkedlist双端链表的组合）。Redis中的列表支持两端插入和弹出，并可以获得指定位置（或范围）的元素，可以充当数组、队列、栈等。

1typedefstructlistNode{//前置节点3structlistNode*prev;4//后置节点5structlistNode*next;6//节点的值7void*value;8}listNode;typedefstructlist{11//表头节点1listNode*head;13//表尾节点14listNode*tail;15//节点值复制函数16void*(*dup)(void*ptr);17//节点值释放函数18void(*free)(void*ptr);19//节点值对比函数0int(*match)(void*ptr,void*key);1//链表所包含的节点数量unsignedlonglen;3}list;

　rpush:listAddNodeHead---O(1)

　　lpush:listAddNodeTail---O(1)

　　push:listInsertNode---O(1)

　　index:listIndex---O(N)

　　pop:ListFirst/listLast---O(1)

　　llen:listLength---O(N)

4.1linkedlist（双端链表）

此结构比较像Java的LinkedList，有兴趣可以阅读一下源码。

从图中可以看出Redis的linkedlist双端链表有以下特性：节点带有prev、next指针、head指针和tail指针，获取前置节点、后置节点、表头节点和表尾节点的复杂度都是O（1）。len属性获取节点数量也为O（1）。

与双端链表相比，压缩列表可以节省内存空间，但是进行修改或增删操作时，复杂度较高；因此当节点数量较少时，可以使用压缩列表；但是节点数量多时，还是使用双端链表划算。

4.ziplist（压缩列表）

当一个列表键只包含少量列表项，且是小整数值或长度比较短的字符串时，那么redis就使用ziplist（压缩列表）来做列表键的底层实现。

ziplist是Redis为了节约内存而开发的，是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构；具体结构相对比较复杂，有兴趣读者可以看Redis哈希结构内存模型剖析。在新版本中list链表使用quicklist代替了ziplist和linkedlist：

quickList是zipList和linkedList的混合体。它将linkedList按段切分，每一段使用zipList来紧凑存储，多个zipList之间使用双向指针串接起来。因为链表的附加空间相对太高，prev和next指针就要占去16个字节(64bit系统的指针是8个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。

quicklist默认的压缩深度是0，也就是不压缩。为了支持快速的push/pop操作，quicklist的首尾两个ziplist不压缩，此时深度就是1。为了进一步节约空间，Redis还会对ziplist进行压缩存储，使用LZF算法压缩。

五、Hash

Hash对象的底层实现可以是ziplist（压缩列表）或者hashtable（字典或者也叫哈希表）。

Hash对象只有同时满足下面两个条件时，才会使用ziplist（压缩列表）：1.哈希中元素数量小于51个；.哈希中所有键值对的键和值字符串长度都小于64字节。

hashtable哈希表可以实现O(1)复杂度的读写操作，因此效率很高。源码如下：

1typedefstructdict{//类型特定函数3dictType*type;4//私有数据5void*privdata;6//哈希表7dicththt[];8//rehash索引9//当rehash不在进行时，值为-intrehashidx;/*rehashingnotinprogressifrehashidx==-1*/11//目前正在运行的安全迭代器的数量1intiterators;/*numberofiteratorscurrentlyrunning*/13}dict;14typedefstructdictht{15//哈希表数组16dictEntry**table;17//哈希表大小18unsignedlongsize;19//哈希表大小掩码，用于计算索引值0//总是等于size-11unsignedlongsizemask;//该哈希表已有节点的数量3unsignedlongused;4}dictht;5typedefstructdictEntry{6void*key;7union{void*val;uint64_tu64;int64_ts64;}v;8//指向下个哈希表节点，形成链表9structdictEntry*next;30}dictEntry;31typedefstructdictType{3//计算哈希值的函数33unsignedint(*hashFunction)(constvoid*key);34//复制键的函数35void*(*keyDup)(void*privdata,constvoid*key);36//复制值的函数37void*(*valDup)(void*privdata,constvoid*obj);38//对比键的函数39int(*keyCompare)(void*privdata,constvoid*key1,constvoid*key);40//销毁键的函数41void(*keyDestructor)(void*privdata,void*key);4//销毁值的函数43void(*valDestructor)(void*privdata,void*obj);44}dictType;

上面源码可以简化成如下结构：

这个结构类似于JDK7以前的HashMapString,Object，当有两个或以上的键被分配到哈希数组的同一个索引上时，会产生哈希冲突。Redis也使用链地址法来解决键冲突。即每个哈希表节点都有一个next指针，多个哈希表节点用next指针构成一个单项链表，链地址法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位。

Redis中的字典使用hashtable作为底层实现的话，每个字典会带有两个哈希表，一个平时使用，另一个仅在rehash（重新散列）时使用。随着对哈希表的操作，键会逐渐增多或减少。为了让哈希表的负载因子维持在一个合理范围内，Redis会对哈希表的大小进行扩展或收缩（rehash），也就是将ht里面所有的键值对分多次、渐进式的rehash到ht里。

六、Set

Set集合对象的底层实现可以是intset（整数集合）或者hashtable（字典或者也叫哈希表）。

intset（整数集合）当一个集合只含有整数，并且元素不多时会使用intset（整数集合）作为Set集合对象的底层实现。

1typedefstructintset{//编码方式3uint3_tencoding;4//集合包含的元素数量5uint3_tlength;6//保存元素的数组7int8_tcontents[];8}intset;

sadd:intsetAdd---O(1)

smembers:intsetGetO(1)---O(N)

srem:intsetRemove---O(N)

slen:intsetlen---O(1)

intset底层实现为有序，无重复数组保存集合元素。intset这个结构里的整数数组的类型可以是16位的，3位的，64位的。如果数组里所有的整数都是16位长度的，如果新加入一个3位的整数，那么整个16的数组将升级成一个3位的数组。升级可以提升intset的灵活性，又可以节约内存，但不可逆。

7.ZSet

ZSet有序集合对象底层实现可以是ziplist（压缩列表）或者skiplist（跳跃表）。

当一个有序集合的元素数量比较多或者成员是比较长的字符串时，Redis就使用skiplist（跳跃表）作为ZSet对象的底层实现。

1typedefstructzskiplist{//表头节点和表尾节点3structzskiplistNode*header,*tail;4//表中节点的数量5unsignedlonglength;6//表中层数最大的节点的层数7intlevel;8}zskiplist;9typedefstructzskiplistNode{10//成员对象11robj*obj;1//分值13doublescore;14//后退指针15structzskiplistNode*backward;16//层17structzskiplistLevel{18//前进指针19structzskiplistNode*forward;0//跨度---前进指针所指向节点与当前节点的距离1unsignedintspan;}level[];3}zskiplistNode;

zadd---zslinsert---平均O(logN),最坏O(N)

zrem---zsldelete---平均O(logN),最坏O(N)

zrank--zslGetRank---平均O(logN),最坏O(N)

skiplist的查找时间复杂度是LogN，可以和平衡二叉树相当，但实现起来又比它简单。跳跃表(skiplist)是一种有序数据结构，它通过在某个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

-End-

加小编，可以邀请加入咱们的「菜鸟架构」技术群一起讨论技术，禁止发广告及垃圾信息哦。