Redis数据结构

Redis为什么那么快？

• 除了它是内存数据库，使得所有的操作都在内存上进行之外，还有一个重要因素，就是它实现的数据结构，使得我们对数据进行增删改查操作时，Redis能高效的处理。

注意：

• Redis数据结构并不是指String（字符串）对象、List（列表）对象、Hash（哈希）对象、Set（集合）对象和ZSet（有序集合）对象，因为这些是Redis中键值对中值Value的数据类型，也就是数据的保存形式，这些对象的底层实现的方式就用到了数据结构。?

Redis是C-S架构

Redis 数据类型和底层数据结构的对应关系图：

• 左边是 Redis 3.0版本的，也就是《Redis 设计与实现》这本书讲解的版本，现在看还是有点过时了，右边是现在 Redis 7.0 版本的。

键值对数据库是怎么实现的？

• 我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查，而键与值的映射关系正是通过Dict来实现的。?

Dict?

• Dict由三部分组成，分别是：哈希表(DictEntryTable)、哈希节点(DictEntry)、字典(Dict)?。

Redis 使用 dictht 结构体表示哈希表，不过，在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。??

• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash。

之所以定义了 2 个哈希表，是因为进行 rehash 的时候，需要用上 2 个哈希表了。

Redis是怎么实现键值对（Key-Value）数据库的？

• Redis是使用了一个「哈希表」来保存所有的键值对，哈希表的最大好处就是让我们可以用O(1)的时间复杂度来快速查找键值对；
• 哈希表其实就是一个数组，数组中的元素叫做哈希桶。

Redis的哈希桶是怎么保存键值对数据的呢？

• 哈希桶存放的是指向键值对数据的指针，这样通过指针就能找到键值对数据。

Redis 的哈希表以及哈希表节点的结构如下：?

可以看到，哈希表是一个数组（dictEntry **table），数组的每个元素是一个指向「哈希表节点（dictEntry）」的指针。?

• 当我们向Dict添加键值对时，Redis首先根据Key计算出Hash值，然后利用出来的Hash值? &? sizemask - 哈希表大小的掩码，即哈希表的数组长度 - 1来计算元素应该存储到数组中的哪个索引位置。?

• dictEntry 结构里不仅包含指向键和值的指针，还包含了指向下一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对链接起来，以此来解决哈希冲突的问题，这就是链式哈希。

8. 哈希表

• 哈希表是一种保存键值对（Key-Value）的数据结构。?
• 哈希表中的每一个Key都是独一无二的，程序可以根据Key找到与之关联的Value。
• Hash对象的另外一个底层实现就是哈希表，哈希表的优点在于，它能以O(1)的时间复杂度快速查找数据? =>? ?将Key通过Hash函数的计算得到哈希值，再将哈希值 % 哈希表的数组长度 - 1进去取模计算，得到的结果就是该key-value对应的数组元素位置，就能定位到数据在表中的位置，因为哈希表实际上是数组，可以通过数组下标索引值快速查询到数据。
• 随着数据的不断增多，哈希冲突的可能性也会越高，Redis采用链式地址法解决哈希冲突。

哈希冲突：

• 当有两个以上数量的Key被分配到了哈希表中同一个哈希桶上时，此时称这些key发生了冲突。?

链式哈希是怎么实现的？

• 实现的方式就是每个哈希表节点都有一个next指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个哈希桶上的多个节点可以用这个单向链表链接起来，这样就解决了哈希冲突。
• 不过，链式哈希局限性也很明显，随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，查询效率会大大降低，毕竟链表的查询的时间复杂度是 O(n)。

要想解决这一问题，就需要进行 rehash，也就是对哈希表的大小进行扩展。

• 不管是哈希表扩容还是收缩，必定会创建新的哈希表，这就会导致哈希表的size和sizemask发生变化，而key的查询与sizemask有关，因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。??

接下来，看看 Redis 是如何实现的 rehash 的。

在正常服务请求阶段，插入的数据，都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。

随着数据逐步增多，触发了 rehash 操作，这个过程分为三步：

1. 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大一倍（两倍的意思）；
2. 将「哈希表 1 」的数据迁移到「哈希表 2」 中；
3. 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备。

这个过程看起来简单，但是其实第二步很有问题，如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。?

渐进式 rehash

• 为了避免 rehash 在数据迁移过程中，因拷贝数据的耗时，影响 Redis 性能的情况，所以 Redis 采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

渐进式 rehash 步骤如下：

• 给「哈希表 2」 分配空间；
• 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；
• 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的过程中，会有两个哈希表，所以在渐进式 rehash 进行期间，哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

比如，查找一个 key 的值的话，先会在「哈希表 1」 里面进行查找，如果没找到，就会继续到哈希表 2 里面进行找到。

另外，在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」 则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。

rehash 触发条件

介绍了 rehash 那么多，还没说什么时情况下会触发 rehash 操作呢？

rehash 的触发条件跟 负载因子（load factor）有关系。

负载因子可以通过下面这个公式计算：

?

触发 rehash 操作的条件，主要有三个：

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作。
• Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩，此时也会进行rehash操作。

1. String类型内部实现 - 动态字符串SDS?

• 我们都知道Redis中保存的Key是字符串，Value往往是字符串或者字符串的集合，可见字符串是Redis中最常用的一种数据结构。

Redis String类型的底层的数据结构实现主要是SDS（简单动态字符串），不过Redis并没有直接使用C语言中的字符串，因为SDS相比C语言的原生字符串：

• SDS不仅可以保存文本数据，还可以保存图片、音视频等这样的二进制数据，而C语言的原生字符串只能保存文本数据。
• SDS获取字符串长度的时间复杂度是O(1)，因为C语言的字符串并不记录自身长度，所以获取长度的时间复杂度为O(n)，而SDS结构里用len属性记录了字符串长度，所以时间复杂度为O(1)。
• 不会发生缓冲区溢出 - SDS之所以叫动态字符串，是因为它具备动态扩容的能力：Redis的SDS API是安全的，拼接字符串不会造成缓冲区溢出，因为SDS在拼接字符串之前会检查SDS空间是否满足要求，如果空间不够会自动扩容，会申请新的内存空间，所以不会导致缓冲区溢出的问题。?

所以Redis构建了一种全新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。?

2. List类型内部实现

List类型的底层数据结构是由双向链表或ZipList压缩列表实现的：

• 如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用ZipList压缩列表作为 List 类型的底层数据结构；
• 如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构；

但是在 Redis 3.2 版本之后，List 数据类型底层数据结构就只由 QuickList 实现了，替代了双向链表和压缩列表。?

3. Hash类型内部实现

Hash类型的底层数据结构是由ZipList压缩列表或哈希表实现的：?

• 如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用ZipList压缩列表作为 Hash 类型的底层数据结构；
• 如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。

在 Redis 7.0 中，ZipList压缩列表数据结构已经废弃了，交由 listpack 紧凑列表数据结构来实现了。

4.?Set 类型内部实现?

Set 类型的底层数据结构是由哈希表或整数集合IntSet实现的：

• 如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用IntSet????整数集合作为 Set 类型的底层数据结构；
• 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

5.?ZSet / SortedSet?类型内部实现?

Zset / SortedSet有序集合类型的底层数据结构是由ZipList压缩列表或SkipList跳表实现的：

• 如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表ZipList作为 Zset 类型的底层数据结构，来代替HashTable和SkipList；
• 如果有序集合的元素不满足上面的条件，Redis 会使用SkipList跳表作为 Zset 类型的底层数据结构；

由于ZipList压缩列表存在连锁更新问题，因此在 Redis 7.0 中压缩列表数据结构已经废弃了，交由 Listpack紧凑列表 数据结构来实现了。

6. 链表?

• Redis的List对象的底层实现之一就是链表，而C语言本身是没有链表这个数据结构的，所以Redis自己设计了一个链表数据结构。

链表节点结构设计

先来看看「链表节点」结构的样子：

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

有前置节点和后置节点，可以看的出，这个是一个双向链表：

因此，Redis 3.0 的 List 对象在数据量比较少的情况下，会采用「压缩列表」作为底层数据结构的实现，它的优势是节省内存空间，并且是内存紧凑型的数据结构。?

7. 压缩列表 -?ZipList

• 压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，从而有效的利用CPU缓存，节省内存开销。?

但是，压缩列表的缺陷也是有的：

• 不能保存过多的元素，否则查询效率就会降低，如果我们要查找定位第一个元素和最后一个元素，复杂度是 O(1) - 压缩列表可以在任意一端进行压入 / 弹出操作，而查找其他元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了，因此压缩列表不适合保存过多的元素。；
• 新增或修改某个元素时，如果空间不够，压缩列表占用的内存空间就需要重新分配，当新插入或删除的元素较大时，甚至可能引发「连锁更新」的问题，导致每个元素的空间都要重新分配，这会直接影响到压缩列表的访问性能。

因此，Redis 对象（List 对象、Hash 对象、Zset 对象）包含的元素数量较少，或者元素值不大的情况才会使用压缩列表作为底层数据结构。

压缩列表结构设计：

• 压缩列表是 Redis 为了节约内存而开发的，它是由连续内存块组成的顺序型数据结构，有点类似于数组。
• 压缩列表紧凑型的内存布局能节省内存开销。

9. 整数集合 - intset?

• 整数集合IntSet是Redis中Set集合的一种实现方式，当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会基于整数数组来实现，整数集合本质上是一块连续内存空间，并且具备长度可变、有序等特征。?
• Redis会确保IntSet中的元素唯一、有序，底层采用二分查找的方式来查询。

10. QuickList

• ZipList虽然节省内存，但申请空间必须是连续空间，如果内存占用较多，申请内存效率很低，因此Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList? =>? 本质：是一个节点为ZipList的双端链表。
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList的大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存空间，因为链表一般都是从首尾访问较多，所以首尾是不压缩的。

11.?SkipList - 跳表?

• Redis 只有 Zset 对象的底层实现用到了跳表，跳表的优势是能支持平均 O(logN) 复杂度的节点查找。
• zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。?

Zset 对象在执行数据插入或是数据更新的过程中，会依次在跳表和哈希表中插入或更新相应的数据，从而保证了跳表和哈希表中记录的信息一致。

Zset 对象能支持范围查询（如 ZRANGEBYSCORE 操作），这是因为它的数据结构设计采用了跳表，而又能以常数复杂度获取元素权重（如 ZSCORE 操作），这是因为它同时采用了哈希表进行索引。

可能很多人会奇怪，为什么我开头说 Zset 对象的底层数据结构是「压缩列表」或者「跳表」，而没有说哈希表呢？

Zset 对象在使用跳表作为数据结构的时候，是使用由「哈希表+跳表」组成的 struct zset，但是我们讨论的时候，都会说跳表是 Zset 对象的底层数据结构，而不会提及哈希表，是因为 struct zset 中的哈希表只是用于以常数复杂度获取元素权重，大部分操作都是跳表实现的。

接下来，详细的说下跳表。

传统链表在查找元素的时候，因为需要逐一查找（因为链表它的指针跨度是1，也就是说每一个节点它的指针永远指向的是下一个节点，所以需要逐一查找，依次遍历），所以查询效率非常低，时间复杂度是O(N)，于是就出现了跳表。?

跳表结构设计? =>? 空间换时间?

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

跳表是在链表基础上改进过来的，实现了一种「多层」的有序链表，这样的好处是能快读定位数据。??

• 元素按照升序排列存储
• 节点可能包含多个指针，且指针跨度不同? =>? 内部包含了跨度不同的多级指针，可以让我们跳跃查找链表中间的元素，效率非常高。?

?