概念

Redis作为用c编写的开源非关系数据库，基于良好的CRUD效率，经常用于软件系统的缓存，其本身提供以下五种数据格式。

string (字符串列表hash )散列表set )无序集合zset )有序集合接下来，对这五种数据结构分析其底层结构

这里选择的版本是redis-5.0.4，所以可能和现在互联网上的其他博文不太一致的地方很多，但本文会指出不同的地方

string

redis是用c语言开发的，所以当然没有java和c的字符串类库。 Redis自定义了一种称为简单动态序列(SDS )的字符串格式。 换句话说，它是一个简单的动态字符串

该结构由sds.h定义。

类型字符* SDS；

但是，此sds类型只用作参数和返回值，而不是实际用于操作的类型。 真正的中心部分是下一班。

结构_属性_打包的SD硬盘5

无符号标记；

卡尔巴赫；

(；

结构_属性_打包的SD硬盘8

uint8_t len；

uint8_ t分配；

无符号标记；

卡尔巴赫；

(；

结构_属性_打包的SD硬盘16

uint 16指示灯；

uint 16 _ t分配；

无符号标记；

卡尔巴赫；

(；

SD硬盘32

uint32_t len；

uint 32 _ t分配；

无符号标记；

卡尔巴赫；

(；

SD shdr 64

uint 64指示灯；

uint 64 _ t分配；

无符号标记；

卡尔巴赫；

(；

除去最初的结构体(废除)，sds的具体类型的结构可以分为以下部分。

(len )已使用的长度，即字符串的真正长度alloc )除了头和尾) (0) )之外的长度flags )后3位表示字符串类型，其余5位未使用) redis在哪里使用了这个属性还不知道) buus 因为手头只有4.x和5

len:buf已经占用的长度(表示该字符串的实际长度) free:buf中未使用的缓冲区的长度buf ) )实际存储字符串数据的位置redis同时重写了有关sds类型的许多方法，但redis

到o(1)为止降低获取字符串长度的时间复杂度，减少字符串修改时的存储器重新分配次数，提高与c字符串的兼容性，同时提高一些字符串工具方法的有效二进制安全性(数据写入的形式和读取的形式一致)

list

ziplist

ziplist不是类名。 其结构如下。 zlbyteszltailentriesentry . entryzlend

其中各部分的代表意义如下。

ZL字节： 4字节(32字节)表示ziplist所占用的总字节数zltail:4 ) 4字节) 32字节)，表示ziplist的最后一个节点的ziplist中的偏移字节数entries:2 因为这些数据都存储在小端节序中，有些人看数据的二进制流可能不能适应其含义，但实际上是因为数据的读取方法错了

ziplist在内部以数据压缩方式存储，压缩方式不是重点。 从宏上看，ziplist就像封装的数组，使用zltail可以更容易地添加和删除末尾的数据以及使用条目

地计算长度

但是其依然有数组的缺点，就是当插入和删除数据时会频繁地引起数据移动，所以就引出了quicklist数据类型

quicklist

其核心数据结构如下：

typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* ziplist所有节点的个数 */ unsigned long len; /* quicklistNode节点的个数 */ int fill : 16; /* 单个节点的填充因子 */ unsigned int compress : 16; /* 压缩端结点的深度 */ } quicklist;

我们可以明显地看出，quicklist是一个双向链表的结构，但是内部又涉及了ziplist，我们可以这么说，在宏观上，quicklist是一个双向链表，在微观上，每一个quicklist的节点都是一个ziplist

在redis.conf中，可以使用下面两个参数来进行优化：

list-max-ziplist-size：表示每个quicklistNode的字节大小。默认为2，表示8KBlist-compress-depth：表示quicklistNode节点是否要压缩。默认为0，表示不压缩

这种存储方式的优点和链表的优点一致，就是插入和删除的效率很高，而链表查询的效率又由ziplist来进行弥补，所以quicklist就成为了list数据结构的首选

hash

hash这种结构在redis的使用时最为常见，在redis中，hash这种结构有两种表示：zipmap和dict

zipmap

zipmap其格式形如下面这样： <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

各部分的含义如下：

zmlen：1个字节，表示zipmap的总字节数len：1~5个字节，表示接下来存储的字符串长度free：1个字节，是一个无符号的8位数，表示字符串后面的空闲未使用字节数，由于修改与键对应的值而产生

这其中相邻的两个字符串就分别是键和值，比如在上面的例子中，就表示"foo" => "bar", "hello" => "world"这样的对应关系

这种方式的缺点也很明显，就是查找的时间复杂度为O(n)，所以只能当作一个轻量级的hashmap来使用

dict

这种方式就适于存储大规模的数据，其格式如下：

typedef struct dict { dictType *type;/* 指向自定义类型的指针，可以存储各类型数据 */ void *privdata; /* 私有数据的指针 */ dictht ht[2];/* 两个hash表，一般只有h[0]有效，h1[1]只在rehash的时候才有值 */ long rehashidx; /* -1：没有在rehash的过程中，大于等于0：表示执行rehash到第几步 */ unsigned long iterators; /* 正在遍历的迭代器个数 */ } dict;

如果我们不想更深入的话了解到这种程度就可以了，其中真正存储数据的是dictEntry结构，如下：

typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;

很明显是一个链表，我们知道这是采用链式结构存储就足够了

这种方式会消耗较多的内存，所以一般数据较少时会采用轻量级的zipmap

set

在redis中，我们可以查看intset.h文件，这是一个存储整数的集合，其结构如下：

typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents[]; } intset;

其中各字段含义如下：

encoding：数据编码格式，表示每个数据元素用几个字节存储（可取的值有2、4，和8）length：元素个数contents：柔性数组，这部分内存单独分配，不包含在intset中

具体的操作我们就不详细展开了，了解集合这种数据结构的应该都很清楚，我们这里说一下，intset有一个数据升级的概念，比方说我们有一个16位整数的set，这时候插入了一个32位整数，所以就导致整个集合都升级为32位整数，但是反过来却不行，这也就是柔性数组的由来

如果集合过大，会采用dict的方式来进行存储

zset

zset，有很多地方也叫做sorted set，是一个键值对的结构，其键被称为member，也就是集合元素（zset依然是set，所以member不能相同），其对应的值被称为score，是一个浮点数，可以理解为优先级，用于排列zset的顺序

其也有两种存储方式，一种是ziplist/zipmap的格式，这种方式我们就不过多介绍了，只需要了解这种格式将数据按照score的顺序排列即可

另一种存储格式是采用了skiplist，意为跳跃表，可以看成平衡树映射的数组，其查找的时间复杂度和平衡树基本没有差别，但是实现更为简单，形如下面这样的结构（图来源跳跃表的原理）：