大家好，我是北军。前段时间有朋友面试京东的时候，遇到了这样一道面试题。下面说说Redis的数据类型及其对应的底层数据结构。那么今天智贝君就带大家了解一下Redis的基本数据类型对应的底层数据结构。一、前言Redis的键值对中常见的数据类型有String（字符串）、List（列表）、Hash（散列）、Set（集合）、Zset（有序集合）。那么它对应的底层数据结构有SDS（简单动态字符串）、链表、字典、跳转表、压缩链表、快速链表、整数集等，下面我们来看看它底层数据结构的精妙之处。2.Redis底层数据结构2.1SDSRedis自定义了一个简单的动态字符串（simpledynamicstring）作为Redis默认的字符串表示。其主要结构如下：len表示SDS字符串的长度，如果buff字节数组中存放了5个字符，则长度为5。同时也方便获取SDS的长度。alloc表示分配的字符数组的长度。它的值一般大于SDS字符串的长度（len）。由于Redis的设计场景是频繁访问和修改数据，所以无论数据是增加还是缩减，都需要尽量减少重新分配内存的操作。因此，SDS会预留一些空间，下次修改数据时可以直接使用原来预分配的内存，而预留的内存空间会在每次数据操作时动态增减。Redis3.0版本的SDS结构中使用free表示未分配空间，但也是同样的设计思路。flags标志位，低3位表示类型，其余5位不用。buf是一个实际存储数据的数组，可以存储字符或者二进制数据。redis6.0中SDS定义如下*然而，此处用于记录5类SDS字符串的布局。*/struct__attribute__((__packed__))sdshdr5{无符号字符标志；/*3lsb的类型，5msb的字符串长度*/charbuf[];};struct__attribute__((__packed__))sdshdr8{uint8_tlen;/*使用*/uint8_talloc;/*不包括标头和空终止符*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr16{uint16_tlen;/*使用*/uint16_talloc;/*不包括标头和空终止符*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr32{uint32_tlen;/*使用*/uint32_talloc;/*不包括标头和空终止符*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};struct__attribute__((__packed__))sdshdr64{uint64_tlen;/*使用*/uint64_talloc;/*不包括标头和空终止符*/unsignedcharflags;/*3lsboftype,5unusedbits*/charbuf[];};与C语言中的字符串相比，SDS有以下优点：获取字符串的长度复杂度较低（常数复杂度）。更节省内存（不同数据类型sdshdr5、sdshdr8、sdshdr16等设置不同长度。）防止缓冲区溢出。大大减少了修改字符串长度所需的内存分配次数。二进制安全。2.2链表链表是大家比较熟悉的一种数据结构。链表通过添加或删除节点提供高效的节点重排能力、顺序访问和长度调整。RedisList对象的底层实现之一是链表。每个链表节点由以下结构表示。/*Node、List和Iterator是目前唯一使用的数据结构。*/typedefstructlistNode{structlistNode*prev;结构列表节点*下一个；void*value;}listNode;一个双端队列如下图所示：多个节点可以组成一个链表，Redis使用List结构来保存这些节点，操作起来更方便。其结构如下：typedefstructlist{listNode*head;//链表头节点指针listNode*tail;//链表尾节点指针void*(*dup)(void*ptr);//用于复制列表节点保存的值void(*free)(void*ptr);//用于释放链表节点保存的值int(*match)(void*ptr,void*key);//用于比较链表节点保存的值与其他输入值是否相等unsignedlonglen;//链表包含的节点数}list;简单结构如下图所示：Redis链表有以下特点：由于是双端链表，有prev和next指针，获取节点的前一个节点和复杂度发布节点是O(1)。头节点的prev和尾节点的next都指向NULL，这是一个无环链表，NULL可以作为链表访问的终点。链表本身提供了指针，可以快速获取链表的头节点和尾节点。内置链表长度计数器，可以快速获取链表长度。链表可以存储各种类型的值。2.3字典字典是一种用于存储键值对的抽象数据结构。在字典中，一个键（key）可以与一个值（value）相关联，称为键值对。字典中的每个键都是唯一的，程序使用键来更新值或删除数据。Redis字典使用哈希表作为底层实现。一个哈希表可以包含多个哈希表节点，每个哈希表节点在字典中存储一个键值对。下面说说哈希表、哈希表节点、字典的实现。哈希表和哈希表节点结构，字典结构如下：//字典结构typedefstructdict{dictType*type;//特定于类型的函数void*privdata;//私有数据字典ht[2];//length为2哈希表数组，一般情况下只有字典使用ht[0]哈希表，rehash时会用到ht[1]。长重新哈希；/*rehashidx==-1当没有执行rehash时*/unsignedlongiterators;/*当前运行的迭代器数量*/}dict;//哈希表结构typedefstructdicttht{dictEntry**table;//哈希数组unsignedlongsize;//哈希表大小unsignedlongsizemask;//哈希表掩码，用于计算索引值，总是等于size-1unsignedlongused；//表示存在的节点个数}dictht;//哈希节点typedefstructdictEntry{void*key;//keyunion{//value值，包含多种类型的值，不同类型的值可以存储在不同的数据结构中，以节省内存。无效*值；//它的值可以是一个指针uint64_tu64;//它的值也可以是一个uint64_tintegerint64_ts64;//它的值可以是一个int64_tintegerdoubled;//它的值可以是double}v;结构dictEntry*下一个;//指向一个哈希节点}dictEntry;正常状态下的字典结构示意图：添加新机制是一个熟悉的想法。使用字典设置的hash函数计算key的hash值，对hash值和sizemask进行&运算，计算索引值。然后添加到数组中。如果存在hash冲突，会使用链地址的方式解决冲突，使用next指针指向下一个hash节点。在哈希表中存储的键值逐渐增加或减少的过程中，程序会扩大或缩小哈希表。这个过程称为重新散列。上面的ht[0]ht[1]会在rehash过程中用到。具体过程这里不再赘述，将单独写一篇文章进行介绍。2.4跳表跳表（skiplist）是一种有序的数据结构，在每个节点中维护多个指向其他节点的指针，以便于快速访问。它支持平均O(logN)复杂度的节点查找。Zset使用跳跃列表和字典作为其底层实现。优点是可以进行高效的范围查询，也可以进行高效的单点查询。它在源码中的结构如下：typedefstructzskiplistNode{//skiplistnodesdsele;//typedefstructzskiplistNode{//跳过列表节点sdsele;//成员对象，每个节点中的成员对象是唯一的。双倍分数；//得分structzskiplistNode*backward;//后向指针structzskiplistLevel{//层数，最多32层structzskiplistNode*forward;//前向指针无符号长跨度；//span}level[];}zskiplistNode;typedefstructzskiplist{//跳表structzskiplistNode*header,*tail;//指向跳表头尾节点unsignedlonglength;//节点号intlevel;//skiplist中层数最多的节点层数}zskiplist;typedefstructzset{//zset的数据结构使用字典dict和zskiplistdict*dict;zskiplist*zsl;}zset;跳表节点的参数解释如下：层级：跳表节点的层级数组可以包含多个节点元素，每个元素包含指向其他节点的指针，程序可以利用这些指针来加速访问其他节点，层数越多，访问效率越高。每创建一个新的跳表节点，程序都会随机生成一个1-32之间层数的值作为level数组的大小。指示节点的高度。前向指针，forward：每一层都有一个指向表尾的前向指针，可以从表头到表尾访问节点。spanspan：记录两个节点之间的距离。向后指针backward：节点的向后指针，用于访问从表尾到表头的节点。每个节点只有一个后向指针，因此一次只能向后移动一个节点。分数score：分数是一个浮点数，跳表中的节点按照分数排序。成员对象ele：指向SDS对象的指针。下面我们画一个跳表的示意图：如果要访问图中的节点3，只需要通过头节点第四层的前向指针找到这个节点即可。如果需要添加元素，会先使用高阶前向指针遍历，比较score值，然后逐渐缩小插入元素的位置范围，再确定最终的位置。这样，它的平均时间复杂度是O(logN)。与链表O(N)的时间复杂度相比，其效率大大提高。但代价是它需要多一点内存空间。个人感觉有点类似于MySql的索引。2.5压缩列表ziplist压缩列表是Redis中list和hash对象的底层实现之一。开发压缩列表是为了节省内存，它由一系列连续编码的内存块组成。其结构如下图：每个节点的说明如下：zlbytes，4字节，记录压缩列表占用的内存字节数，仅用于压缩列表的内存重分配，或者计算位置时zlend尾节点。zltail，4字节，记录压缩列表的尾节点距离压缩列表起始地址多少字节。可以快速计算出尾节点的地址。zlen，2字节，记录压缩列表中包含的节点数。entryX压缩列表中的节点，其长度取决于节点内容zlend，1字节，特殊值OxFF(255)标记压缩列表的结束。每个压缩列表节点条目由以下部分组成：previous_entry_length记录压缩列表中前一个节点的长度，其属性可以是1或5个字节。如果前一个节点的长度小于254，那么它的长度为1字节，表示前一个节点的长度。如果迁移节点的长度大于254字节，则其属性长度为5字节，第一个字节设置为OxFE(254)，后面的4字节用于表示前一个节点的长度。encoding表示content属性保存的数据类型和长度。内容保存字节数组时，编码的值为1、2、5个字节，最高前两位分别为00、01、10，最高前两位之后的其他数字记录内容的长度。内容存储整数编码时，最高2位为11，其余位记录整数类型和。content保存节点的内容，可以保存一个字节数组，也可以保存一个整数。由于previous_entry_length记录的是前一个节点的长度，可能是1个字节，也可能是5个字节，如果前一个节点的长度从254以下增加到254以上，那么previous_entry_length的值将使用5个字符的Section类表示。而如果后面的节点存在同样的情况，那么压缩列表就会发生链式更新，导致内存空间的重新分配，导致压缩列表中添加节点或删除节点的最坏时间复杂度O(N2)。新版本在redis中引入了listpack。它的目的是取代ziplist，整体结构类似。其入口结构如下：len保存当前节点的编码和数据的长度合成，避免链式更新。2.6快速列表快速列表（quicklist）可以看作是双向链表和压缩列表的结合。Redis3.2之后，list对象使用fastlist作为底层实现。快速列表使用quickListNode节点组成一个双向链表，然后使用压缩列表在每个快速列表节点内部存储数据，从而可以控制压缩列表的长度，避免链更新带来的性能影响。其中快速列表的源代码结构如下：typedefstructquicklist{quicklistNode*head;快速列表节点*尾巴；无符号长计数；/*所有ziplists中所有条目的总数*/unsignedlonglen;/*快速列表节点数*/intfill:QL_FILL_BITS;/*单个节点的填充因子*/unsignedintcompress:QL_COMP_BITS;/*结束节点的深度不压缩；0=关闭*/unsignedintbookmark_count:QL_BM_BITS;quicklistBookmark书签[];}quicklist;typedefstructquicklistBookmark{quicklistNode*node;char*name;}quicklistBookmark;typedefstructquicklistNode{structquicklistNode*prev;结构quicklistNode*下一个;无符号字符*zl；无符号整数sz；/*以字节为单位的ziplist大小*/unsignedintcount:16;/*ziplist中的项目数*/unsignedintencoding:2;/*RAW==1或LZF==2*/unsignedintcontainer:2;/*NONE==1或ZIPLIST==2*/unsignedint重新压缩小号：1；/*这个节点以前是压缩过的吗？*/unsignedintattempted_compress:1;/*节点不能压缩；太小*/unsignedintextra:10;/*为将来使用窃取更多比特*/}quicklistNode;quickList维护了一个quicklistBookmark数组，里面有执行qulickListNode的head和tail的指针。每个quicklistBookmark都有一个指向quickListNode的指针，每个quickListNode都有指向前后节点的指针。其结构图如下：2.7整数集整数集（intset）是setkey的底层实现之一。当一个集合只包含整数元素时，Redis将使用整数集合作为集合键的实现。整数集源码如下：typedefstructintset{uint32_tencoding;uint32_t长度；int8_t内容[];}intset;那么数组的每个元素都是int16_t。如果新加入的整数超出这个范围，在32位以内，则整个数组中的每一个元素都会升级为一个int32_t表示的整数。如果新加入的整数是64位的，可以表示为Integers，所以元素会再次升级。但是整数集合不支持降级，如果整数集合中有一个64位的整数，即使去掉这个元素，整个集合也不会被降级。这提供了一些灵活性并节省了内存。仅在需要时升级。总结从上面Redis的底层数据结构可以看出，其设计的核心始终是节省内部内存，提高访问速度。所以Redis快，这种巧妙的底层设计也是少不了的。同时，我们也可以根据一些设计思路来优化自己的代码。优秀的设计永远值得学习。
