之前在使用Redis的时候，只是简单的使用了它提供的基本数据类型和接口，并没有去深入研究它的底层数据结构。最近打算重新学习整理Redis的知识，所以打算先从介绍Redis的基本类型和数据结构开始。redisObjectRedis的key是顶层模型，它的值是扁平化的。在Redis中，所有的值都是一个对象，其结构如下：typedefstructredisObject{unsigned[type]4;unsigned[encoding]4;unsigned[lru]REDIS_LRU_BITS;intrefcount;void*ptr;}robj;简单介绍一下这几个A字段：type：数据类型，也就是我们熟悉的string、hash、list等。encoding：内部编码其实就是本文要介绍的数据结构。它指的是当前值的底部使用什么数据结构。因为同一个数据类型底层有多个数据结构实现，所以这里需要指定数据结构。REDIS_LRU_BITS：当前对象可以保留的时间长度。这个我们后面讲key过期策略的时候再讲。refcount：对象引用计数，用于GC。ptr：指针，指向编码实现的这个对象的实际地址。String在Redis内部，string类型有两种底层存储结构。Redis会根据存储的数据和用户的操作指令自动选择合适的结构体：int：存储整数类型；SDS：存储浮点数、字符串、字节类型；SDS:simpledynamicstringsimpledynamicstringSDSSDS内部数据结构：typedefstructsdshdr{//buf中已经占用的字符长度为unsignedintlen;//buf中剩余的可用字符长度为unsignedintfree;//数据空间charbuf[];}可见，它的底层是一个char数组。buf最大容量为512M，可以容纳字符串、浮点数和字节。所以你甚至可以放一张序列化的图片。为什么它不直接使用数组，而是包装成这样一个数据结构呢？因为buf会有动态扩缩容的需求。如果直接使用数组，每次修改字符串都会导致重新分配内存，效率很低。buf的扩容过程如下：如果修改后len的长度小于1M，则分配给free的大小与len相同。比如修改后是10字节，那么free也是10字节，buf的实际长度变成10+10+1=21byte如果修改后的len长度会大于等于1M，那么分配给free的长度是1M，比如修改后是30M，那么free的buf实际长度就变成了30M+1M+1bytelazyspaceRelease的意思是当字符串变短的时候，没有真正的收缩，但是free指针被感动了。这样以后当字符串长度增加的时候，就不需要重新分配内存了。但是这样会造成内存浪费，Redis提供了API来真正释放内存。listlist底层有两个数据结构：linkedlistlinkedlist和compressedlistziplist。当列表元素个数较少且元素内容长度不大时，使用ziplist实现，否则使用linkedlist。Redis使用的链表是双向链表。为了操作方便，使用了一个链表结构来保存这个链表。如图：typedefstructlist{//表头节点listNode*head;//表尾节点??listNode*tail;//链表包含的节点个数unsignedlonglen;//节点值复制函数void*(*dup)(void*ptr);//节点值释放函数void*(*free)(void*ptr);//节点值比较函数int(*match)(void*ptr,void*key);}list;数据stored实际上是一个指针。链表中的元素就是上面介绍的字符串。因为是双向链表，所以可以方便的用作栈或者队列。压缩列表对应于上面的链表。压缩列表有点像数组，通过连续的内存空间存储数据。但是，它与数组的不同之处在于它允许以不同的大小存储数据。为每个节点添加一个length属性，记录本节点的长度，这样更方便获取下一个节点的位置。上图中各个字段的含义分别为：zlbytes：链表总长度zltail：指向最后一个元素zllen：元素个数entry：元素的内容，记录了上一个Entry的长度，即用于方便双向遍历zlend:常量0xFF，作为ziplist的分隔符，压缩后的列表既是list的底层实现，也是hash的底层实现之一。当哈希元素个数较少，内容长度不大时，使用压缩列表来实现。hashhash有两种底层实现：压缩列表和字典（dict）。上面刚刚介绍了压缩列表，下面主要介绍字典的数据结构。字典字典其实类似于Java语言中的Map和Python语言中的dict。与Java中的HashMap类似，Redis底层也是采用哈希表作为字典实现，采用链表的方式解决哈希冲突。Redis也用了一个数据结构来保存这个哈希表：当key增加或减少时，它会扩容或缩容，并根据哈希值进行rehash，重新计算索引值。如果字典太大怎么办？为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作中，分批完成。当负载因子达到阈值时，只申请新的空间，但旧数据不会移动到新的哈希表中。当有新的数据要插入时，将新的数据插入到新的哈希表中，从旧的哈希表中取出一条数据放入新的哈希表中。每次向哈希表中插入一条数据，重复上述过程。经过多次插入操作，旧哈希表中的所有数据一点一点地移动到新哈希表中。这样就没有集中的一次性数据移动，插入操作变得非常快。此过程也称为渐进式重新散列。setset中没有重复的集合。set的实现比较简单。如果是整数类型，直接使用整数集合intset。使用二分查找辅助，速度还是挺快的。但是在插入的时候，由于需要移动元素，时间复杂度是O(N)。如果不是整数类型，就使用上面hash部分介绍的字典。key是set的value，value为空。zsetzset是一个可排序的集合。类似于hash的实现，如果元素个数不多也不大，使用压缩列表ziplist来存储。但是由于zset包含了score的排序信息，所以在ziplist内部，是按照score升序存储的。这意味着每次插入数据时，必须移动后续数据。跳表（skiplist）是实现dict的另一种数据结构。跳跃列表是对链表的增强。我们在使用链表的时候，即使元素是有序排列的，如果要找到一个元素，也需要从头一个一个的找，时间复杂度是O(N)。跳表顾名思义就是跳转一些元素，可以抽象出多层。如下图，比如我们要查找8，首先在最上层L2查找，在1到9之间查找；然后去L1层搜索，找到5到9之间；然后去L0查找，找到7和9之间，找到8。当元素比较多的时候，使用skiptable可以明显减少查找次数。与list类似，Redis并没有直接使用跳转列表，而是使用自定义的数据结构来保存跳转列表。下图左边蓝色部分是skiplist，右边是4个zskiplistNodes。zskiplistNode内部有很多层L1、L2等，指针指向这一层的下一个节点。BW是后向指针（backward），用于查找时回溯。然后下面是分数和对象本身。总结一下，Redis暴露了对象（数据类型），每个对象都由一个redisObject持有，通过不同的编码映射到不同的数据结构。从一开始的图我们可以知道，有时候不同的对象可能会使用相同的底层数据结构，比如压缩列表和字典。了解了数据结构之后，我们就可以更清楚选择什么样的对象，以及出现问题时如何优化。
