redis主要的数据类型有：String，List，Hash，Set，SortedSet，也称为对象，而这些数据类型，底层是基于特定的数据结构来实现的。

我们之前也在IT宅(itzhai.com)以及Java架构杂谈中聊过了一些常见的数据结构：

数据结构与算法

而Redis中，基于存储效率和访问效率的考虑，使用到了一些其他的数据结构。我们首先来看看Redis中常见的这些数据结构，然后在看看这些数据类型是由什么数据结构组成的。

1、SDS

我们知道，String类内部定义了常量数组进行存储字符串，是不可以修改的，每次对字符串操作都会另外分配一个新的常量数组空间。

而Redis中的字符串是动态的。字符串是Redis中最为常见的存储类型，底层采用简单动态字符串实现(SDS^[1], simple dynamic string)，是可以修改的字符串，类似于Java中的ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配。

Redis中的键值对中的键、值里面的字符串、缓冲区、AOF缓冲区、等都是用的SDS。

下面是SDS数据结构的一个图示：

亮点：

获取字符串长度时间复杂度为O(1)，而C语言则需要遍历整个数组才能得到长度；
采用空间预分配避免反复对字节数组进程扩容，如上图的SDS，还有2个字节的空闲空间，如果只是追加一个字符，就不用扩容了。避免了类似C语言要手动重新分配内存的情况下，忘记了进行分配而导致的缓冲区溢出或者内存泄露问题；
惰性空间释放：当要缩短字符串长度的时候，程序不会立刻释放内存，而是通过free属性将这些需要释放的字节数量记录下来，等待将来重复使用；
二进制安全：所有的SDS API都会以处理二进制的方式来处理SDS的buf数组数据，这样就避免了C字符串读取到空字符就返回，导致读取不完整字符串的问题。二进制安全的SDS，是的Redis可以保存任意格式的二进制数据，而不仅仅是文本数据。
- 如果是C语言，字符串存入了一种使用空字符(\0，不是指空格)来分隔单词的特殊数据格式，存储如下内容：
- 使用C字符串函数读取到的结果会丢失空字符后面的内容，得到：itzhai，丢失了com。
- SDS使用len属性的值来判断字符串是否结束，而不是空字符。
兼容部分C字符串函数：为了兼容部分C字符串函数库，SDS字符串遵循C字符串以空字符结尾的惯例。

空间预分配规则

字符串大小小于1M的时候，每次扩容加倍；
超过1M，扩容只会多扩容1M的空间，上限是512M。

更多关于Redis字符串的命令：Redis - Strings^[2]

2、链表 linkedlist

Redis中List^[3]使用的是双向链表存储的。

如下图：

List特点：

双向链表；
无环；
带head和tail指针；
带链表长度；
多态，链表节点可存储不同类型的值；

List提供了以下常用操作参考：命令列表：redis.io/commands#list^[3:1]

通过LPUSH，LPOP，RPUSH，RPOP操作，可以把List当成队列或者栈来使用：

3、Hash字典

Redis的字典使用哈希表作为底层实现。该数据结构有点复杂，我直接画一个完整的结构图，如下：

如上图，字典结构重点属性：

type和privdata主要是为创建多态字典而设置的；
ht[1]: 包含两个哈希表，正常情况下，只使用ht[0]，当需要进行rehash的时候，会使用到ht[1]；
rehashidx: 记录rehash目前的进度，如果没有在rehash，则值为-1；

而哈希表又有如下属性：

哈希表数组，里面的元素作为哈希表的哈希桶，该数组每个元素都会指向一个dictEntry结构指针，dictEntry结构保存具体的键值对；
数组大小，记录了哈希表数组的大小；
哈希掩码，主要用于计算哈希索引值，这个属性和哈希值决定一个键在哈希表数组中的位置；
已有节点个数，记录哈希表目前已有节点的数量。

dictEntry结构如图中代码所示：

key保存键值对的键的指针；
v保存着键值对的值，值可以是一个指针，或者是unit64_t整数，或者是int64_t整数。

3.1、hash和hash冲突

作为哈希表，最重要的就是哈希函数，计算新的数据应该存入哪个哈希桶中。

具有良好统一的哈希函数的时候，才能真正的实现花费恒定时间操作哈希表。由于哈希算法计算的数据是无限的，而计算结果是有限的，因此最终会出现哈希冲突。常用的两种解决哈希冲突的方式是链地址法和开放定址法。而Redis中使用的是链地址法。

3.2、字典是如何进行rehash的？

随着哈希冲突的不断加剧，hash查找的效率也就变慢了，为了避免这种情况的出现，我们要让哈希表的负载因子维持在一个合理地范围之内。

当哈希冲突增加的时候，就需要执行rehash操作了。

rehash操作，也就是指增加哈希表中的哈希桶数量，让超负载哈希桶中的entry元素重新分散到更多的桶里面，从而减少单个桶中的元素数量，减少哈希冲突，从而提高查找效率。

rehash的流程

Redis的rehash是一个渐进的rehash的过程。为什么要这样做呢？

如果需要rehash的字典非常大，有几百上千万个键值对，那么执行rehash就要很长的时间了，这个期间有客户端需要写入新的元素，就会被卡住了，因为Redis执行命令是单线程的，最终将导致Redis服务器在这段时间不能正常提供服务，后果还是比较严重的。

这种这种情况，我们可以采用分而治之的思想，把rehash的过程分小步一步一步来处理，每一步迁移少量键值对，并在对字典的操作流程中做一些兼容处理，确保rehash流程对客户端无感知，这就是我们所说的渐进式rehash。

大致流程如下：

这样，从第0个哈希桶开始，每次执行命令的时候，都rehash下一个哈希桶中的entry，并且新增的元素直接往ht[1]添加。于是ht[0]的元素逐渐减少，最终全部转移到了ht[1]中，实现了哈希表的平滑rehash，最小程度的降低对Redis服务的影响。

4、跳跃表 skiplist

Redis中的跳跃表是一种有序数据结构，通过在每个节点维持指向其他节点的指针，从而实现快速访问节点的目的。

Redis中的有序集合就是使用跳跃表来实现的。

为了简化跳跃表模型，我们先来看看，假设所有跳跃表节点的层级都是1的情况，如下图：

这个时候，跳跃表相当于一个双向链表，查找元素的复杂度为最差的O(N)，即需要遍历所有的节点。

为了提高遍历效率，让跳跃表真正的跳起来，现在我们尝试在各个节点添加更多的Level，让程序可以沿着这些Level在各个节点之间来回跳跃，如下图，我们现在要查找score=9的节点，查找流程如下图红线所示：

这种查找类似于二分查找，首先从最高层L3进行查找，发现L3的下一个节点score=10，比目标节点大，于是下降到L2继续比较，发现L2的下一个节点为5，比目标节点小，于是继续找下一个节点，为10，比目标节点大，于是在score为5的节点中继续下降到L1，查找下一个节点，刚好为9，至此，我们就找到了目标节点，查找的时间复杂度为O(log N)。

如果每一层节点数是下面一层节点个数的一半，那就是最理想的类，跟二分查找一样。但是这样每次插入新元素，都会打乱上下两层链表节点个数2:1的比例关系，如果要维持这种关系，就必须对插入节点的后面所有节点进行重新调整。为了避免这种问题，跳跃表不做这个严格的上下级比例约束，而是每个节点随机出一个Level层数。

跳跃表节点如何生成level数组？

每次创建新的跳跃表节点的时候，都会根据幂次定律，随机生成一个介于1~32之间的数组大小，这个大小就是level数组元素个数。

插入节点操作只需要修改插入节点前后的指针就可以了，降低了插入的复杂度。

5、整数集合 intset

在Redis中，当一个集合只包含整数值，并且集合元素不多的时候，会使用整数集合保存整数集，集合中的数据不会出现重复，集合元素从小到大有序排列，可以保存int16_t,int32_t,int64_t的整数值。

下面是整数集合的数据结构：

在内存中，整数集合是在一块连续的内存空间中的，如下图所示：

contents数组按从小到大的顺序保存集合的元素；
encoding编码，可选编码：
- INTSET_ENC_INT16（From −32,768 to 32,767）
- INTSET_ENC_INT32（From −2,147,483,648 to 2,147,483,647）
- INTSET_ENC_INT64（From −9,223,372,036,854,775,808 to 9,223,372,036,854,775,807）

整数集合是如何升级的？

当往整数集合添加的元素比当前所有元素类型都要长的时候，需要先对集合进行升级，确保集合可以容纳这个新的元素。

升级方向：INTSET_ENC_INT16 --> INTSET_ENC_INT32 --> INTSET_ENC_INT64

注意，一旦升级之后，就不可以降回去了。

下面是一个升级的过程说明：

原本整数数组存的都是INTSET_ENC_INT16编码的元素，接下来往里面插入一个元素 32768，刚好超出了原来编码的范围，于是需要对整数集合进行升级。于是对intset进行内存扩容，扩容后也是通过一块连续空间存储的，这有可能带来一次数据拷贝。

如果要插入的元素在中间，说明不用进行升级，这个时候会使用二分查找算法找到插入的位置，然后扩容插入元素，重新调整元素位置。

intset特点

由于intset是从小到到排列的，所以可以进行二分查找，查找性能比ziplist的遍历查找性能高；
intset只能存储整数，并且由于是内存紧凑的存储模式，没有携带len信息，所以每个元素必须统一编码；
intset存储可能变成字典存储，条件：
- 添加了一个超过64bit的有符号数字之后；
- 添加的集合元素个数超过了set-max-intset-entries配置的值；

6、压缩列表 ziplist

压缩列表是为了节省Redis内存，提高存储效率而开发的数据结构，是列表键和哈希键的底层实现之一，当hash中的数据项不多，并且hash中的value长度不大的时候，就会采用压缩列表存储hash。

为什么要这样设计呢？是因为ziplist不擅长存储大量数据：

数据量大了，每次插入或者修改引发的realloc操作可能会造成内存拷贝，加大系统开销；
ziplist数据量大了，由于是遍历查找，查找性能会变得很低。

以下是压缩列表的数据结构：

尾节点地址 = 压缩列表起始指针地址 + zltail(偏移量)

我们再来看看压缩列表节点的结构：

xxxx部分表示存储的长度内容，或者是0~12整数。

压缩列表的content可以保存一个字节数组或者一个整数值。

如上图，ziplist通过特殊的编码约定，通过使用尽可能少的空间，很巧妙的存储了编码和长度信息，并且通过entry中的属性，可以在ziplist中进行双向遍历，效果相当于双向链表，但是占用更少的内存。

整数编码 1111xxxx为什么能存储2^4-1个整数？

由于11110000，11111110分别跟24位有符号整数和8位有符号整数冲突了，所以只能存储 0001_{1101范围，代表1}13数值，但是数值应该从0开始计数，所以分别代表 0~12。

什么是ziplist连锁更新问题？

假设我们有一个ziplist，所有节点都刚好是253字节大小，突然往中间插入了一个254字节以上大小的节点，会发生什么事情呢？

如下图，由于新的节点插入之后，新节点的下一个节点的previous_entry_length为了记录新节点的大小，就必须扩大4个字节了。然后又会触发后续节点的previous_entry_length扩大4个字节，一直这样传递下去。所以这个过程也成为连锁更新。

最坏情况进行N次空间重新分配，每次重新分配最坏复杂度O(N)。触发连锁更新的最坏复杂度为O(N^2)。

但是实际情况，出现连续多个节点长度结语250~253之间的情况还是比较少的，所以实际被连续更新的节点数量不会很多，平均时间复杂度为O(N)。

由于ziplist的数据是存储在一块连续的空间中，并不擅长做修改操作，数据发生改动则会触发realloc并且触发连锁更新，可能导致内存拷贝，从而降低操作性能。

7、quicklist

linkedlist由于需要存储prev和next指针，消耗内存空间比较多，另外每个节点的内存是单独分配的，会加剧内存的碎片化，影响内存管理的效率。

于是，在Redis 3.2之后的版本，重新引入了一个新的数据结构：quicklist，用来代替ziplist和linkedlist。

为何需要quicklist？

我们得先来说说ziplist和linkedlist的优缺点：

linkedlist优点：插入复杂度很低；
linkedlist缺点：有prev和next指针，内存开销比较大；
ziplist优点：数据存储在一段连续的内存空间中，存储效率高；
ziplist缺点：修改复杂度高，可能会触发连锁更新。

为了整合linkedlist和ziplist的优点，于是引入了quicklist。quicklist底层是基于ziplist和linkedlist来实现的。为了进一步节省空间，Redis还会对quicklist中的ziplist使用LZF算法进行压缩

quicklist结构

如上图所示，quicklist结构重点属性：

head：指向链表表头；
tail：指向链表表尾；
count：所有quicklistNode中的ziplist的所有entry节点数；
len：链表的长度，即quicklistNode的个数。

quicklistNode重点属性：

*prev：指向链表前一个节点的指针；
*next：指向链表后一个节点的指针；
*zl：数据指针，如果当前节点数据没有被压缩，那么指向一个ziplist结构；否则，指向一个quicklistLZF结构；
sz：不管有没有被压缩，sz都表示zl指向的ziplist占用的空间大小；
count：ziplist里面包含的entry个数；
encoding：ziplist是否被压缩，1没有被压缩，2被压缩了；
container：预留字段，固定为2，表示使用ziplist作为数据容器；
recompress：之前是否已经压缩过此节点？当我们使用类似index这样的命令查看已经压缩的节点数据的时候，需要暂时解压数据，通过这个属性标记后边需要把数据重新压缩。

quicklist配置项

list-max-ziplist-size：指定quicklist中每个ziplist最大的entry元素个数，负数表示：

-5：指定快速列表的每个ziplist不能超过64 KB；

-4：指定快速列表的每个ziplist不能超过32 KB；

-3：指定快速列表的每个ziplist不能超过16 KB；

-2：指定快速列表的每个ziplist不能超过8 KB。这是默认值；

-1：指定快速列表的每个ziplist不能超过4 KB。

list-compress-depth：指定列表中两端未压缩的条目数。有效值：0到65535。

0：不压缩列表中的节点。这是默认值；

1到65535：不压缩列表两端的指定节点数，但是压缩所有中间节点。

可以看出，表头和表尾总是不会被压缩，以便在两端进行快速存取。

而实际上，Redis顶层是以对象(数据类型)的形式提供数据的操作API的，而对象的底层实现，则是用到了以上的数据结构。

接下来我们继续看看Redis中的对象。

Redis

Redis内存数据结构 | sds,linkedlist,hash,skiplist,intset,ziplist,quicklist