Redis性能之谜：揭秘数据结构背后的秘密

发表时间: 2024-06-25 20:29

“快！”，这几乎是所有人对 Redis 的第一印象。它就像一个身手敏捷的侠客，总能在电光火石间完成数据的读写操作。但你是否好奇，Redis 惊人的速度背后，究竟隐藏着怎样的秘密武器？

答案就藏在它的数据结构中。

内存数据库只是表象，高效数据结构才是关键

诚然，作为内存数据库，Redis 将所有数据存储在内存中，天生就拥有了速度优势。但这就好比一位武林高手拥有了充沛的内力，要想在实战中发挥出威力，还需要精妙的招式。

Redis 的“招式”就是它精妙的数据结构。键值对操作的本质是对数据结构进行增删改查，高效的数据结构自然就成了 Redis 快速处理数据的基石。

数据类型 vs 数据结构：拨开迷雾，直击本质

你可能会说：“Redis 的数据结构不就是 String、List、Hash、Set 和 Sorted Set 这五种类型吗？”

没错，但这只是 Redis 键值对中值的数据类型，也就是数据的保存形式。而我们今天要探讨的数据结构，是这些数据类型在底层的实现方式。

简单来说，Redis 的底层数据结构一共有 6 种：

简单动态字符串 (SDS)
双向链表
压缩列表
哈希表
跳表
整数数组

它们与数据类型的对应关系如下图所示：

可以看到，String 类型的底层实现只有一种数据结构，也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型，则分别对应两种底层实现结构，我们通常称之为集合类型。

为什么集合类型会有两种底层结构呢？它们都是如何组织数据的？哪种结构更快？别急，我们慢慢道来。

全局哈希表：Redis 的数据管家

在揭秘集合类型之前，我们先来看看 Redis 是如何组织键值对的。答案是：哈希表。

Redis 使用一个全局哈希表来保存所有的键值对。哈希表就像一个巨大的仓库，里面划分了许多个储物柜，每个储物柜就是一个哈希桶。

你可能会问：“如果值是集合类型，哈希桶要怎么保存呢？”

别担心，哈希桶中存储的并不是值本身，而是指向值的指针。也就是说，无论值是 String 类型还是集合类型，哈希桶中都只存储它们的指针。

这种设计的好处显而易见：

快速查找： 通过键的哈希值可以直接定位到对应的哈希桶，时间复杂度为 O(1)。
节省空间： 哈希桶中只存储指针，无论值的大小如何，都不会影响哈希表的存储空间。

哈希冲突与 rehash：Redis 的性能挑战

哈希表虽然高效，但也面临着一个棘手的问题：哈希冲突。

当两个不同的键计算出的哈希值相同时，就会发生哈希冲突。就好比两个顾客同时要把货物存放到同一个储物柜中，就会发生冲突。

Redis 解决哈希冲突的方式是链式哈希。简单来说，就是将发生冲突的键值对用链表连接起来，形成一个哈希冲突链。

然而，随着数据量的增加，哈希冲突会越来越频繁，哈希冲突链也会越来越长，查找效率就会降低。

为了解决这个问题，Redis 会进行 rehash 操作，也就是增加哈希桶的数量，将数据重新分配到更多的哈希桶中，减少哈希冲突。

为了避免 rehash 过程阻塞 Redis 主线程，Redis 采用了渐进式 rehash。简单来说，就是将 rehash 操作分散到多个请求中，每次请求处理一部分数据，从而避免了长时间的阻塞。

集合类型的底层数据结构：各显神通

了解了 Redis 如何组织键值对，我们再来看看集合类型的底层数据结构。

1. 整数数组和双向链表：简单直接，但效率有限

整数数组和双向链表是两种比较基础的数据结构，它们的优点是简单易懂，但缺点是查找效率较低，时间复杂度为 O(N)。

2. 压缩列表：以空间换时间，适用于小规模数据

压缩列表是一种为了节省内存而设计的顺序型数据结构。它将多个数据元素紧凑地存储在一块连续的内存空间中，通过减少内存碎片来提高内存利用率。

压缩列表的查找效率介于数组和哈希表之间，查找第一个元素和最后一个元素的时间复杂度为 O(1)，查找其他元素的时间复杂度为 O(N)。

3. 跳表：有序链表的救星，实现高效查找

跳表是一种基于有序链表的数据结构，它通过增加多级索引来提高查找效率。

跳表的查找过程就像是在走楼梯，每上一层楼就相当于跳过了一部分数据，从而快速接近目标数据。跳表的查找时间复杂度为 O(logN)，接近于哈希表的 O(1)。

4. 哈希表：高效查找的王者

哈希表是一种非常高效的数据结构，它通过哈希函数将数据映射到不同的哈希桶中，实现快速查找。哈希表的查找时间复杂度为 O(1)。

集合类型操作复杂度：四句口诀，轻松掌握

集合类型支持的操作类型非常多，每种操作的复杂度也不尽相同。为了帮助大家快速记忆，我总结了“四句口诀”：

单元素操作是基础： 指对单个数据进行的增删改查操作，例如 HGET、HSET、SADD、SREM 等。
范围操作非常耗时： 指遍历集合中所有数据或部分数据的操作，例如 HGETALL、SMEMBERS、LRANGE、ZRANGE 等。
统计操作通常高效： 指统计集合中元素个数的操作，例如 LLEN、SCARD 等。
例外情况只有几个： 指一些特殊情况下的操作，例如 List 类型的 LPOP、RPOP、LPUSH、RPUSH 等。

总结：知己知彼，百战不殆

Redis 之所以快，是因为它巧妙地选择了不同的数据结构来应对不同的应用场景。

对于需要快速查找的场景，Redis 使用哈希表作为底层数据结构，例如 String、Hash 和 Set 类型。
对于需要维护数据顺序的场景，Redis 使用跳表作为底层数据结构，例如 Sorted Set 类型。
对于需要快速增删元素的场景，Redis 使用压缩列表或双向链表作为底层数据结构，例如 List 类型。

了解 Redis 的数据结构，可以帮助我们更好地理解 Redis 的工作原理，选择合适的命令，编写高效的代码，充分发挥 Redis 的性能优势。

当然，Redis 的数据结构远不止于此，还有很多细节值得我们深入探讨。在接下来的学习中，我们将逐一揭开它们的神秘面纱，探索 Redis 更深层次的奥秘。