在面试中，redis也是面试官非常喜欢的部分。我这里说的是redis的底层数据结构，并不是你理解的五大数据结构。有没有想过redis的底层数据结构，它们和java中的HashMap、List等使用的数据结构有什么区别。1、字符串处理（string）我们都知道redis是用C语言写的，但是用C语言处理字符串和数组的成本是非常高的。下面我举几个例子。没有数据结构支持的几个问题极易造成缓冲区溢出问题，比如使用strcat()，在使用这个函数之前，必须先给目标变量分配足够的空间，否则会溢出。如果要获取字符串的长度，可能需要在没有数据结构支持的情况下遍历。它的复杂度是O(N)内存重新分配。C字符串的每次更改（延长或缩短）都会重新分配数组的内存。同样，如果缩短了，多余的空间没有处理好，也会造成内存泄漏。那么，Redis构建了一个数据结构，叫做简单动态字符串（Simpledynamicstring,SDS），他分别处理这些问题。先看一下它的结构体源码：structsdshdr{//记录buf数组中已使用的字节数//等于SDS保存字符串的长度intlen;//记录buf数组中未使用的字节数intfree;//字节数组，用于保存字符串charbuf[];}先说说它的优点：开发者不用担心字符串变化导致的内存溢出。获取字符串长度len字段的恒定时间复杂度。spacepre-allocatedfree字段默认会留出足够的空间，防止多次重新分配内存。了解更多：https://redis.io/topics/internals-sds这是string的底层实现，也是redis处理所有string数据的方式（SDS会嵌套到其他数据结构中使用）。2、链表Redis的链表扩展了双向链表的头、尾节点、元素个数等属性。2.1源码ListNode节点数据结构：typedefstructlistNode{//前节点structlistNode*prev;//后节点structlistNode*next;//节点值void*value;}listNode链表数据结构：typedefstructlist{//头节点listNode*head;//listNode*tail;//链表包含的节点个数unsignedlonglen;//节点值复制函数void(*free)(void*ptr);//节点值释放函数void(*free)(void*ptr);//节点值比较函数int(*match)(void*ptr,void*key);}list;从上面可以看出，Redis的链表有这些特点：可以直接获取header，tail节点。获取链表长度的恒定时间复杂度。是一个双向链表。3、字典（Hash）Redis的Hash是基于数组+链表，进行了一些rehash优化。3.1数据结构源码哈希表：typedefstructdict{//哈希表数组dictEntry**table;//哈希表大小unsignedlongsize;//哈希表大小掩码，用于计算索引值//始终等于size-1unsignedlongsizemask;//哈希表中已有的节点个数unsignedlongused;}dictht;哈希表节点：typedefstructdictEntry{//Keyvoid*key;//Valueunion{void*val;uint64_tu64;int64_ts64;}v;//指向下一个哈希table节点形成一个链表structdictEntry*next;//单链表结构}dictEntry;dictionary:typedefstructdict{//type-specificfunctiondictType*type;//privatedatavoid*privdata;//hashtabledictththt[2];//rehashindex//当没有进行rehash时，值为-1intrehashidx；/*rehashingnotinprogressifrehashidx==-1*/}dict;可以看出Reids的Hash是使用链地址的方式来处理冲突的，然后就没有使用红黑树优化。哈希表节点采用单向链表结构。重新哈希优化。下面说说它的rehash优化。3.2rehash当哈希表的关键字正确或太少时，需要调整哈希表的大小。redis如何调整呢？我们可以仔细看到dict结构体中有一个字段dictththt[2]，也就是说有两个dicttht数组。第一步是为ht[1]哈希表分配空间，大小取决于ht[0]当前的使用情况。将ht[0]中存储的数据rehash（重新计算hash值）到ht[1]。当ht[0]中的所有键值对迁移到ht[1]后，释放ht[0]，将ht[1]设置为ht[0]，并初始化ht[1]，为下一次rehash做准备。3.3Progressiverehash我们在3.2中看到redis处理了rehash过程，但是更详细一点，它是如何进行数据迁移的呢？这涉及渐进式重新散列。考虑到海量数据迁移导致cpu繁忙（可能导致服务停止一段时间），Redis采用了progressiverehash方案。步骤如下：为ht[1]分配空间，同时持有两张哈希表（一空一有数据）。维护一个初始值为0的技术设备rehashidx，每次字典的增删改查都会将ht[0]中的数据迁移到ht[1]中，顺便rehashidx++（注意：ht[0]中的数据只能减少不能增加）。直到rehash操作完成，rehashidx值被设置为-1。它的好处：采用分而治之的思想，将庞大的迁移工作量分到各个CURD中，避免繁忙的服务。4.跳表的数据结构是我在面试中看到最多的一种，其实也很简单。学过的人可能都知道，它的性能和平衡树差不多，但是为什么要用skipList而不是平衡树呢？4.1skipList和AVL的选择从算法实现难度上来说，skiplist比平衡树要简单的多。平衡树的插入和删除操作可能会引起子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，简单快速。查找单个key、skiplist和平衡树的时间复杂度都是O(logn)，大致相同。在进行范围查找时，平衡树比跳表操作更复杂。skiplist和各种平衡树（如AVL、红黑树等）的元素按顺序排列。可以看出skipList中的元素是有序的，因此在redis中使用skiptable来进行有序集合键和集群节点内部数据结构。4.2源码跳表节点：typedefstructzskiplistNode{//后向指针structzskiplistNode*backward;//scoredoublescore;//memberobjectrobj*obj;//layerstructzskiplistLevel{//前向指针structzskiplistNode*forward;//spanunsignedintspan;}level[];}zskiplistNode;Skiplist:typedefstructzskiplist{//表头节点和表尾节点structzskiplistNode*header,*tail;//表中的节点数unsignedlonglength;//表中层数最大的节点的层数intlevel;}zskiplist;它有几个概念：4.2.1层(level[])层，即level[]字段，层数越多，访问节点速度越快。（因为相当于一个索引，层数越多，索引越细，索引值可以很快找到）。4.2.2前向指针（forward）层中有一个forward字段，用于从表头到表尾的访问。4.2.3跨度（span）用于记录两个节点之间的距离。4.2.4向后指针（backward）用于从表尾访问表头。案例level01------------>5level11---->3---->5level21->2->3->4->5->6->7->8例如，我想找到key为6的元素，直接定位到level0中的5，然后回头找一个元素。5.整数集（intset）Reids专门针对整数存储进行了优化。Intset是redis用来存储整数值的集合数据结构。当一个组合只包含整数元素时，redis会用这个来存储。127.0.0.1:6379[2]>saddnumber123456(integer)6127.0.0.1:6379[2]>objectencodingnumber"intset"源码intset数据结构：typedefstructintset{//编码方式uint32_tencoding;//集合包含的元素个数uint32_tlength;//数组int8_tcontents[];}intset;你一定很好奇编码字段是做什么用的？如果编码属性的值为INTSET_ENC_INT16，则contents是一个int16_t类型的数组，数组中的每一项都是一个int16_t类型的整数值（最小值为-32,768，最大值为32,767）。如果encoding属性的值为INTSET_ENC_INT32，则contents是一个int32_t类型的数组，数组中的每一项都是一个int32_t类型的整数值（最小值为-2,147,483,648，最大值为2,147,483,647）。如果encoding属性的值为INTSET_ENC_INT64，那么contents是一个int64_t类型的数组，数组中的每一项都是一个int64_t类型的整数值（最小值为-9,223,372,036,854,775,808，最大值为9,223,372,036,854,775,807）。说白了就是根据contents字段来判断使用哪种int类型比较好，也就是优化int的存储。说到优化，redis是怎么做的呢？它涉及升级。5.1编码升级如果我们有一个Int16类型的整数集合，现在我们需要在这个集合中添加65535（int32），int16不能存储，所以我们需要升级整数集合。它是如何升级（过程）的？如果有两个int16元素：1和2，则增加一个新的int32位元素65535。为了重新分配内存，新增后应该有3个元素，所以分配3*32-1=95位。选择最大的数65535，放入(95-32+1,95)的内存段，然后将2放入(95-32-32+1+1,95-32)位……以此类推.升级有什么好处？改进了整数集合的灵活性。尽可能节省内存（能用小的就不用大的）。5.2不支持降级按照上面的例子，如果我删除65535，编码会回到Int16吗？答案是不。官方没有给出原因。我认为它应该减少性能消耗。毕竟一次调整就是O(N)的时间复杂度。6、压缩列表（ziplist）ziplist是redis为了节省内存而开发的一种顺序数据结构。它用于列表键和散列键。一般用于小数据存储。参考https://segmentfault.com/a/1190000016901154中的两张图：6.1源码ziplist没有明确定义结构，这里只是粗略演示。typedefstructentry{/*前一个元素的长度需要空格和前一个元素的长度*/unsignedintprevlengh;/*元素内容编码*/unsignedcharencoding;/*元素的实际内容*/unsignedchar*data;}zlentry;typedefstructziplist{/*ziplistSize分配的内存*/uint32_tzlbytes;/*到tail的偏移量*/uint32_tzltail;/*存储元素实体个数*/uint16_tzllen;/*存储内容实体元素*/unsignedchar*e??ntry[];/*尾标识符*/unsignedcharzlend;}压缩列表；第一次看的时候，你可能会很受骗。仔细读完这段话你就会明白了。Entry分析entry结构中有3个重要字段：previous_entry_length：该字段记录了ziplist中前一个节点的长度。这是什么意思？也就是说可以通过这个属性进行指针操作，从表尾遍历到表头。这个领域还有一个很大的问题将在下面讨论。encoding：记录数据类型（int16？string？）和长度。数据/内容：记录数据。previous_entry_length字段的链式更新分析上面提到，previous_entry_length字段存储的是前一个节点的长度。分配的默认长度是多少？Redis是这样划分的。如果前一个节点的长度小于254，则分配1个字节。如果大于Allocate5bytes，那么问题就来了。如果前一个节点的长度一开始小于254字节，后面又大于254，那么不能存储？这里涉及到previous_entry_length的更新，但是肯定不能改一个，需要更改后续节点的内存信息。所以需要重新分配内存，然后链更新包括受影响节点后面的所有节点。除了添加新节点会触发链更新外，删除节点也会触发。7.快速列表（quicklist）由ziplist组成的双向链表。但是一个quicklist可以有多个quicklist节点，这和B-tree的存储方式很相似。是redis3.2版本新增的一种数据结构，用于链表的底层实现。结构源码头结构：typedefstructquicklist{//指向头部（最左边）quicklist节点的指针quicklistNode*head;//指向尾部（最右边）quicklist节点的指针quicklistNode*tail;//ziplist中入口节点计数器unsignedlongcount;/*totalcountofallentriesinallziplists*///quicklist的quicklistNode节点计数器unsignedintlen;/*numberofquicklistNodes*///保存ziplist的大小，配置文件设置，占16bitsintfill:16;/*fillfactorforindividualnodes*///保存压缩度值，Configuration文件设置，占用16位，0表示不压缩unsignedintcompress:16;/*depthofendnodesnottocompress;0=off*/}quicklist;quicklist节点结构：typedefstructquicklistNode{structquicklistNode*prev;//前驱节点指针structquicklistNode*next;//后继节点指针//未设置压缩数据参数recompress时，指向一个ziplist结构//设置压缩数据参数recompress指向quicklistLZF结构unsignedchar*zl;//压缩列表ziplist的总长度unsignedintsz;/*ziplistsizeinbytes*///打包在ziplist中的节点数，占16bits长度unsignedintcount:16;/*countofitemsinziplist*///表示是否使用LZF压缩算法对quicklist节点进行压缩，1表示压缩，2表示不压缩，占2bitslengthunsignedintencoding:2;/*RAW==1orLZF==2*///表示quicklistNode节点是否使用保存数据的ziplist结构，2表示压缩，1表示不压缩，默认为2，占2bitslengthunsignedintcontainer:2;/*NONE==1orZIPLIST==2*///标记的quicklist节点的ziplist之前是否解压过，占1位长度//如果recompress为1，等待再次压缩unsignedintrecompress:1;/*wasthisnodepreviouscompressed?*///测试时使用unsignedintattempted_compress:1;/*nodecan'tcompress;toosmall*///额外扩展位，占用10bits长度unsignedtextra:10;/*morebitstostealforfutureusage*/}quicklistNode;相关配置在redis.conf的ADVANCEDCONFIG部分：list-max-ziplist-size-2list-compress-depth0list-max-ziplist-size参数下面详细解释一下参数list-max-ziplist-size的含义，它可以取正值或负值。当它取正值时，表示每个quicklist节点上的ziplist的长度是根据数据项的数量来限制的。例如，当该参数设置为5时，表示每个quicklist节点的ziplist最多包含5个数据项。当取负值时，表示ziplist在每个quicklist节点上的长度是根据占用的字节数来限制的。此时只能取-1到-5五个值，每个值的含义如下：-5：ziplist在每个quicklist节点上的大小不能超过64Kb。（注意：1kb=>1024字节）-4：每个quicklist节点上的ziplist大小不能超过32Kb。-3：每个quicklist节点上的ziplist大小不能超过16Kb。-2：每个quicklist节点上的ziplist大小不能超过8Kb。（-2是Redis给的默认值）list-compress-depthparameter该参数表示quicklist两端不压缩的节点数。注意：这里的节点数是指quicklist双向链表的节点数，不是ziplist的数据项数。实际上，如果对一个quicklist节点上的ziplist进行压缩，那么它是作为一个整体进行压缩的。参数list-compress-depth的取值含义如下：0：特殊值，表示不压缩。这是Redis的默认设置。1：表示quicklist两端各一个节点不压缩，中间节点压缩。2：表示quicklist两端的两个节点不压缩，中间节点压缩。3：表示quicklist两端的3个节点不压缩，中间的节点压缩。等等...Redis对quicklist内部节点的压缩算法采用了LZF这种无损压缩算法。
