前段时间，一个朋友采访JD.COM的时候，遇到了这样一个采访问题。
谈Redis的数据类型及其对应的底层数据结构，今天北君就给大家展示一下Redis基本数据类型对应的底层数据结构。
1.简介Redis的键值对中常见的数据类型有String(字符串)、List(列表)、Hash(哈希)、Set(集合)和Zset(有序集)。然后对应的底层数据结构有SDS(简单动态字符串)、链表、字典、跳转表、压缩表、快速表、整数集等。
让我们看看它的底层数据结构的微妙之处。
2.Redis 2.1的底层数据结构SDSRedis定义了一个简单的动态字符串作为Redis的默认字符串。
其主要结构如下：
Len表示这个SDS字符串的长度。如果buff字节数组中存储了5个字符，则长度为5。同时，便于获得SDS的长度。Alloc表示分配的字符数组长度。由于Redis的设计场景就是会频繁的访问，修改数据，所以无论是数据增大或者是缩小都需要尽量减少重新分配内存的操作.该值通常大于SDS字符串长度(len)。因此，SDS将保留一些空间，下次修改数据时，可以直接使用原来预分配的内存。同时，在每次数据操作期间，保留的存储空间将动态增加或减少。Redis3.0的SDS结构中使用Free，表示未分配的空间，但也是同样的设计思路。标志标志位，低3位表示类型，其余5位未使用。Buf是实际存储数据的数组，可以保存字符或二进制数据。redis6.0中的SDS是这样定义的(越来越节约使用内存，内存节省！)
typedef char * sds/* Note: sdshdr5从不使用，我们只是直接访问flags字节。*然而，此处记录了5类SDS字符串的布局。*/struct _ _ attribute _ _((_ _ packed _ _))sdshdr 5 { unsigned char flags；/*类型的3 lsb，字符串长度的5 msb */char buf；};struct _ _ attribute _ _((_ _ packed _ _))SD shdr 8 { uint 8 _ t len；/* used */uint 8 _ t alloc；/*不包括标头和空终止符*/无符号字符标志；/*类型的3个lsb，5个未使用的位*/char buf；};struct _ _ attribute _ _((_ _ packed _ _))SD shdr 16 { uint 16 _ t len；/* used */uint 16 _ t alloc；/*不包括标头和空终止符*/无符号字符标志；/*类型的3个lsb，5个未使用的位*/char buf；};struct _ _ attribute _ _((_ _ packed _ _))SD shdr 32 { uint 32 _ t len；/* used */uint 32 _ t alloc；/*不包括标头和空终止符*/无符号字符标志；/*类型的3个lsb，5个未使用的位*/char buf；};struct _ _ attribute _ _((_ _ packed _ _))SD shdr 64 { uint 64 _ t len；/* used */uint 64 _ t alloc；/*不包括标头和空终止符*/无符号字符标志；/*类型的3个lsb，5个未使用的位*/char buf；};与C语言字符串相比，SDS有以下优点。
得到的字符串长度复杂度较低(常数复杂度)(复杂度可以在本文中看到。如果你还不知道时间复杂度，请来找我)。更节省内存(不同数据类型sdshdr5、sdshdr8、sdshdr16等。被设置为不同的长度。消除缓冲区溢出大大减少了修改字符串长度所需的内存分配数量。二进制安全2.2链表是一种大家熟悉的数据结构，链表提供了高效的节点重排能力、顺序访问以及通过添加或删除节点来调整长度。Redis列表对象的底层实现之一是链表。
p>每一个链表节点使用如下的结构来表示。
/* Node, List, and Iterator are the only data structures used currently. */typedef struct listNode { struct listNode *prev; struct listNode *next; void *value;} listNode;而多了listNode可以通过prev 和 next 指针组成一个双端队列如下图：
多个节点可以组成一个链表，Redis使用了List结构来持有这些节点，操作更方便。其结构如下：
typedef struct list { listNode *head; //链表头节点指针 listNode *tail; //链表尾节点指针 void *(*dup)(void *ptr); // 用于复制链表节点所保存的值 void (*free)(void *ptr); // 用于释放链表节点所保存的值 int (*match)(void *ptr, void *key); //用于对比链表节点所保存的值和另一个输入值是否相等 unsigned long len; // 链表所包含的节点数量} list;简单结构如下图：
Redis链表具有如下特性：
由于是双端链表，有prev和next指针，获取节点的前置节点和后置节点的复杂度为O(1)头节点的prev和尾节点的next均指向NULL，为无环链表，可以以NULL为链表访问终点链表本身提供了指针，可以快速获取链表的表头节点和表尾节点自带链表长度计数器，可以快速获取链表长度链表可以保存各种不同类型的值2.3 字典字典是一种用于保存键值对的抽象数据结构。
在字典中，一个键（key）可以和一个值（value）进行关联，称之为键值对。字典中每个键都是独一无二的，并且程序都是通过key来操作更新value或者删除数据等。
Redis的字典使用哈希表作为底层实现的， 一个哈希表可以包含多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。
下面再讲一下哈希表，哈希表节点，以及字典的实现。
哈希表及哈希表节点结构，字典结构 如下：
//字典结构typedef struct dict { dictType *type; // 类型特定的函数 void *privdata; //私有数据 dictht ht<2>; //长度为2的哈希表数组， 一般情况下字典仅使用 ht<0>哈希表， ht<1>在rehash的时候会使用到。 long rehashidx; /* 未进行rehash的时候 rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */} dict;//哈希表结构typedef struct dictht { dictEntry **table; //哈希数组 unsigned long size; //哈希表大小 unsigned long sizemask; //哈希表掩码，用于计算索引值， 总是等于size-1 unsigned long used; //表示已有节点数量} dictht;//哈希节点typedef struct dictEntry { void *key; //键 union { //value值，包含了多种类型的值，不同类型的值可以使用不同的数据结构存储，节省内存。 void *val; //其值可以是一个指针 uint64_t u64; //其值也可以是一个uint64_t 整数 int64_t s64; //其值可以是一个int64_t 整数 double d; //其值可以是一个double } v; struct dictEntry *next; //指向像一个哈希节点} dictEntry;普通状态下的字典结构示意图：
添加新建的机制是大家比较熟悉的思路啦。
使用字典设置的哈希函数计算key的哈希值，哈希值与sizemask 进行 & 运算，计算出索引值。然后加入到数组中。如果出现哈希冲突，那么会使用链地址法解决冲突，使用next指针指向下一个哈希节点。
哈希表保存的键值逐渐增多或者减少地过程中，程序会对哈希表进行扩展或者收缩，这个过程称之为rehash。
rehash过程中会使用上面的ht<0> ht<1>，具体过程这里就不详细说了，会另外专门写一篇来介绍。
2.4 跳跃表跳跃表（skiplist ）是一种有序数据结构，它在每个节点中维护多个指向其他节点的指针，从而可以快速访问。其支持平均O(logN) 复杂度的节点查找。
Zset使用了跳跃表和字典作为其底层实现。其好处就是可以进行高效的范围查询，也可以进行高效的单点查询。
在源码中其结构如下：
typedef struct zskiplistNode { //跳跃表节点 sds ele; //成员对象，各个节点中成员对象唯一的。 double score; //分值 struct zskiplistNode *backward; //后退指针 struct zskiplistLevel { //层， 最大32层 struct zskiplistNode *forward; //前进指针 unsigned long span; //跨度 } level<>;} zskiplistNode;typedef struct zskiplist { //跳跃表 struct zskiplistNode *header, *tail;//指向 跳跃表头 和表尾节点 unsigned long length; // 节点数量 int level; //跳跃表中层数最大的节点层数量} zskiplist;typedef struct zset { // zset的数据结构使用了 字典dict 和 zskiplist dict *dict; zskiplist *zsl;} zset;关于跳跃表节点的各参数解释如下：
层 level：跳跃表节点的level数组可以包含多个节点元素，每个元素都包含指向其他节点的指针，程序可以通过这些指针来加快访问其他节点的速度，层数越多访问效率越高。每创建一个新的跳跃表节点，程序会随机生成一个1-32之间层数的值，作为level数组的大小。表示节点的高度。前进指针，forward ：每层有一个指向表尾方向的前进指针，可以通过表头向表尾访问节点。跨度 span：记录两个节点之间的距离。后退指针 backward：节点的后退指针，用于从表尾向表头访问节点，每个节点只有一个后退指针，所以每次只能后退一个节点。分值 score：分值是一个浮点数，跳跃表中的节点按照分值来排序，成员对象 ele：一个指针，指向一个SDS对象。下面我们画一个跳跃表的示意图：
图中如果要访问节点3，则只需要通过头节点第四层的前进指针，就可以找到此节点。
如果需要增加元素的时候，会先使用高层前进指针去遍历，并对比score值，然后逐步缩小插入元素的位置范围，然后确定最终的位置。这样其平均时间复杂度为O(logN). 相比于链表的O(N)的时间复杂度来说，其效率大大提高。只不过其代价就是需要多一点的内存空间。
个人感觉和MySql的索引有点类似。
2.5压缩列表 ziplist压缩列表是 Redis中list和 hash 对象的底层实现之一。压缩列表是为了节约内存而开发的，是由一系列连续编码的内存块组成。其结构示意如下：
其中各节点说明如下：
zlbytes ，4字节， 记录压缩列表占用的内存字节数，对压缩列表仅进行内存重分配，或计算zlend尾节点位置时使用。zltail ，4字节， 记录压缩列表尾节点距离压缩列表的起始地址有多少个字节。可以快速计算得到尾节点的地址zlen， 2字节 ，记录了压缩列表包含的节点数量entry X 压缩列表中的节点，其长度取决于节点内容zlend ， 1字节 ， 特殊值OxFF (255) 标记压缩列表末端其中每一个压缩列表节点entry由如下部分组成：
previous_entry_length 记录了压缩列表中前一个节点的长度，其属性可以是1或5个字节。如果前一个节点的长度小于254，那么其长度就是1字节，表示前一节点的长度。如果迁移节点的长度大于254字节， 那么其属性长度则为5个字节，其中第一个字节会设置为OxFE(254) , 后面的4个字节用来表示前一节点的长度。encoding 表示content 属性保存的数据类型以及长度。content保存字节数组时，encoding的值为1，2，5字节， 最高前两位分别为00，01，10， 最高前两位后面的其他位数则记录content的长度。content保存整数编码时，最高2位为11， 其余位记录整数类型及。content 保存节点的内容，可以保存字节数组或者整数。由于previous_entry_length 记录了前一个节点的长度，而且其可能为1个字节或者5个字节，如果前一个节点的长度从254之下增加到254之上，那么previous_entry_length 的值就要使用5个字节类表示。而如果后面的节点均存在同样的情况，那么压缩列表就会出现连锁更新，导致内存空间重新分配，从而导致压缩列表增加节点或者删除节点的最坏时间复杂度位O(N2).
新版本的redis中，引入了listpack。其目的是替换ziplist，整体结构类似。
其entry结构如下：
len保存了当前节点encoding及data的长度综合，从而可以避免连锁更新
2.6快速列表快速列表（quicklist）可以看成是双向链表和压缩列表的一种组合。Redis3.2之后 list对象使用快速列表作为其底层实现。
快速列表使用了quickListNode节点组成双向链表，然后在每个快速列表节点内部使用压缩列表存储数据，从而可以控制压缩列表的长度，避免连锁更新带来的性能影响。
其中快速列表的源码结构如下：
typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all ziplists */ unsigned long len; /* number of quicklistNodes */ int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks<>;} quicklist;typedef struct quicklistBookmark { quicklistNode *node; char *name;} quicklistBookmark;typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *zl; unsigned int sz; /* ziplist size in bytes */ unsigned int count : 16; /* count of items in ziplist */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* NONE==1 or ZIPLIST==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int extra : 10; /* more bits to steal for future usage */} quicklistNode;quickList 中维护了一个quicklistBookmark数组，并且有执行qulickListNode 头尾的指针。
每一个quicklistBookmark 中有一个quickListNode的指针，同时每一个quickListNode又有指向前一个后一个node的指针。
其结构示意图如下：
2.7 整数集合整数集合（intset） 是集合键底层实现之一，当一个集合只包含整数元素的时候，Redis会使用整数集合作为集合键的实现。
整数集合的源码如下：
typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents<>;} intset;整数集合底层是一个数组，如果每一个元素都在16位以内的整数类型(-32768 到 32767)，则数组的每个元素都为int16_t ， 如果新加的整数超过这个范围，并且在32位以内的话， 整个数组中的每一个元素都会升级成int32_t 表示的整数， 如果新加入的是64 位才能表示的整数的话，所以的元素又会再一次升级。
但是整数集合不支持降级，及 整数集合中如果有一个64位的整数，即使移除此元素，整个集合也不会降级。
这样做具有一定的灵活性，而且可以节省内存。当需要升级的时候才进行升级。
总结通过以上 Redis 底层数据结构可以看出，其设计核心总是在节约内内存，提高访问速度。所以Redis快，这小巧妙的底层设计也是功不可没。同时我们也可以根据着些设计思想去优化我们自己的代码，优秀的设计总是值得去学习的。
