面试题】Redis常用数据类型，以及底层实现

字符串（string），队列（list），哈希（hash），集合（sets），有序集合（sorted sets）。

Redis中的字符串都是由动态字符串(simple dynamic string SDS)实现的

所有非数字的key。例如<code>set msg "hello world"</code> 中的key msg.

字符串数据类型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"

非字符串数据类型中的“字符串值”。例如<code>RPUSH fruits "apple" "banana" "cherry"</code>中的"apple" "banana" "cherry"。

SDS数据结构定义：

Redis 3.2之前的SDS这样设计的有点：

1）有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。

2）内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。

3）由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。

list的底层数据结构时链表。Redis 3.2之前的版本（包含3.2）使用的时ziplist或者linkedlist，Redis 3.2之后版本使用的quicklist。

ziplist

压缩列表是为了节约内存而开发的，是存储在连续内存块上的顺序数据结构。一个压缩列表可以包含任意多的 entry 节点，每个节点包含一个字节数组或整数。redis 中并没有显式定义 ziplist 的数据结构，仅仅提供了一个描述结构 zlentry 用于操作数据。

各字段含义如下：

1、zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最长(2^32)-1字节；

2、zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节；

3、zllen：压缩列表的元素数目，占两个字节；那么当压缩列表的元素数目超过(2^16)-1怎么处理呢？此时通过zllen字段无法获得压缩列表的元素数目，必须遍历整个压缩列表才能获取到元素数目；

4、entryX：压缩列表存储的若干个元素，可以为字节数组或者整数；entry的编码结构后面详述；

5、zlend：压缩列表的结尾，占一个字节，恒为0xFF。

该数据结构具有以下特征：

结构紧凑：一整块连续内存，没有多余的内存碎片，更新会导致内存 realloc 与内存复制，平均时间复杂度为 O(N)

逆向遍历：从表尾开始向表头进行遍历

连锁更新：对前一条数据的更新，可能导致后一条数据的 prev_entry_length 与 encoding 所需长度变化，产生连锁反应，更新操作最坏时间为 O(N2)

quicklist

在较早版本的 redis 中，list 有两种底层实现：

当列表对象中元素的长度比较小或者数量比较少的时候，采用压缩列表 ziplist 来存储

当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储

两者各有优缺点：

ziplist 的优点是内存紧凑，访问效率高，缺点是更新效率低，并且数据量较大时，可能导致大量的内存复制

linkedlist 的优点是节点修改的效率高，但是需要额外的内存开销，并且节点较多时，会产生大量的内存碎片.

为了结合两者的优点，在 redis 3.2 之后，list 的底层实现变为快速列表 quicklist。

快速列表是 linkedlist 与 ziplist 的结合: quicklist 包含多个内存不连续的节点，但每个节点本身就是一个 ziplist。

该数据结构有以下特征：

无缝切换：结合了 linkedlist 与 ziplist 的优点，无需在两种结构之间进行切换

中间压缩：作为队列使用的场景下，list 中间的数据被访问的频率比较低，可以选择进行压缩以减少内存占用。

hash 类型是 Redis 常用数据类型之一，其底层存储结构有两种实现方式。

当存储的数据量较少的时，hash 采用 ziplist 作为底层存储结构，此时要求符合以下两个条件：

哈希对象保存的所有键值对（键和值）的字符串长度总和小于 64 个字节。

哈希对象保存的键值对数量要小于 512 个。

当无法满足上述条件时，hash 就会采用 dict（字典结构）来存储数据，数据结构如下：

数据结构有以下特征：

哈希算法：使用 murmurhash2 作为哈希函数，时间复杂度为O(1)

冲突解决：使用链地址法解决冲突，新增元素会被放到表头，时间复杂度为O(1)

Redis set 采用了两种方式相结合的底层存储结构，分别是 intset（整型数组）与 hash table（哈希表），当 set 存储的数据满足以下要求时，使用 intset 结构：

集合内保存的所有成员都是整数值；

集合内保存的成员数量不超过 512 个。

当不满足上述要求时，则使用 hash table 结构。

intset 的结构体定义如下:

encoding：用来指定编码格式，共有三种，分别是 INTSET_ENC_INT16、INSET_ENC_INT32 和 INSET_ENC_INT64，它们对应不同的数值范围。Redis 为了尽可能地节省内存，它会根据插入数据的大小来选择不同的编码格式。

length：集合内成员的数量，记录 contents 数组中共有多少个成员。

contents：存储成员的数组，数组中的成员从小到大依次排列，且不允许重复。

有序整型集合，具有紧凑的存储空间，添加操作的时间复杂度为O(N)

有序集合（zset）同样使用了两种不同的存储结构，分别是 zipList（压缩列表）和 skipList（跳跃列表），当 zset 满足以下条件时使用压缩列表：

成员的数量小于128 个；

每个 member （成员）的字符串长度都小于 64 个字节。

当有序结合不满足使用压缩列表的条件时，就会使用 skipList 结构来存储数据。

跳跃列表（skipList）又称“跳表”是一种基于链表实现的随机化数据结构，其插入、删除、查找的时间复杂度均为 O(logN)。从名字可以看出“跳跃列表”，并不同于一般的普通链表，它的结构较为复杂，本节只对它做浅显的介绍，如有兴趣可自行研究。

在 Redis 中一个 skipList 节点最高可以达到 64 层，一个“跳表”中最多可以存储 2^64 个元素，每个节点都是一个 skiplistNode（跳表节点）。skipList 的结构体定义如下：

header：指向 skiplist 的头节点指针，通过它可以直接找到跳表的头节点，时间复杂度为 O(1)；

tail：指向 skiplist 的尾节点指针，通过它可以直接找到跳表的尾节点，时间复杂度为 O(1)；

length：记录 skiplist 的长度，也就跳表中有多少个元素，但不包括头节点；

level：记录当前跳表内所有节点中的最大层数（level）；

跳跃列表的每一层都是一个有序的链表，链表中每个节点都包含两个指针，一个指向同一层的下了一个节点，另一个指向下一层的同一个节点。最低层的链表将包含 zset 中的所有元素。如果说一个元素出现在了某一层，那么低于该层的所有层都将包含这个元素，也就说高层是底层的子集。

查找：平均查找时间为O(logN)，最坏查找时间为O(N)，并且支持范围查找

概率：每次创建节点的时候，程序根据幂次定律随机生成一个 1 至 32 之间的随机数，用于决定层高

排位：在查找节点的过程中，沿途访问过所有的跨度 span 累计起来，得到目标节点在表中的排位

好学若饥，谦卑若愚