Redis数据存储和查询过程的详细分析

Guo 2025-02-21

Redis 的底层实现非常高效，采用了多种数据结构来支持不同的使用场景。在 Redis 中，全局哈希表（用于存储键值对）是查询数据的核心，它包含多个哈希桶，每个桶内部可以使用不同的复杂数据结构（如 压缩列表（ZipList）、跳表（SkipList） 等）来存储数据。

让我们详细探讨一下 全局哈希表、哈希桶和跳表等数据结构如何工作，以及 Redis 如何在这些结构中进行查找。

1. Redis 数据存储概览

在 Redis 中，每个数据对象（如 string、hash、list、set、sorted set）都存储在一个全局哈希表（字典）中。该哈希表用于将每个 key 映射到一个对应的 数据结构。

1.1 全局哈希表（dict）

Redis 使用 哈希表 来存储键值对。哈希表中的每个桶（bucket）保存一组键值对，键（key）通过哈希算法被分配到一个桶中。

  • 哈希表是 Redis 内存的基础数据结构，所有的 Redis 数据都通过哈希表进行索引。
  • 每个桶内的存储结构可能是不同的，依据数据量和数据类型的不同，桶内的数据结构也会有所变化。

2. 哈希桶及数据结构

2.1 哈希表（Dict）的实现：

Redis 的哈希表底层实现是通过动态扩展的哈希表（rehashing）来实现的。哈希表会定期进行扩展和缩小，以保证负载因子（load factor）的平衡。

  • 哈希表的桶（Bucket）：每个桶存储一组哈希冲突的元素。哈希冲突的发生是因为不同的 key 可能通过哈希算法映射到同一个桶中。每个桶内部的元素是通过链表或其他数据结构来存储的。
  • 哈希表扩展和收缩：当哈希表的负载因子（存储的元素数与桶的数量的比率）达到一定阈值时，Redis 会对哈希表进行扩展；当负载因子过低时，Redis 会收缩哈希表。

2.2 哈希桶中的数据结构

在 Redis 的哈希表的每个桶中，数据可以是不同的数据结构，这取决于实际的存储需求：

压缩列表（ZipList）

  • 适用场景：通常用于存储小的哈希表（字段较少的哈希表），或者存储小型的 list、set。
  • 查找方式：ZipList 是一个 顺序存储 数据的结构，查找时需要从头开始遍历整个列表。虽然查找效率较低，但由于其内存紧凑，适合存储小规模的数据。
    • 查找时间复杂度：O(N)，其中 N 是列表中元素的个数。

哈希表（HashTable）

  • 适用场景：当哈希表中的数据量增加时，Redis 会将桶从 ZipList 转换为标准的哈希表。哈希表使用链表或其他结构来存储数据。
  • 查找方式：哈希表使用哈希算法直接定位桶的索引，再根据哈希值定位到具体的元素。
    • 查找时间复杂度：O(1)，因为哈希表的查找是通过哈希值直接定位的。

2.3 跳表（SkipList）

跳表是 Redis 用于存储 有序集合（Sorted Set） 的一种数据结构。跳表通过多层链表来实现 快速的范围查询 和 高效的查找。

跳表结构：

  • 跳表包含多层链表，每一层都对上一层链表的元素进行部分筛选，从而允许在多层之间跳跃，减少查找的时间。
  • 跳表保证了 O(logN) 的查找时间复杂度，因此适合存储大量有序数据（例如排行榜、时间序列数据等）。

查找过程：

  1. 从顶部层级开始：查找从跳表的最顶层开始，每一层会根据跳跃指针快速跳过多个元素，直到找到接近目标值的位置。
  2. 逐层向下：如果当前层不能进一步跳跃到目标元素，就向下跳到下一层，继续查找直到找到目标元素。
  3. 找到元素：一旦找到目标元素，就返回该元素。

⚡ 时间复杂度：

  • 查找：O(logN)，跳表的多层结构使得查询变得高效。
  • 插入：O(logN)，插入数据时需要维护跳表的层级结构。

3. 数据结构查找总结

数据结构 使用场景 查找时间复杂度 存储特性
全局哈希表（Dict） 存储键值对，快速定位元素 O(1) 哈希表，内存高效
压缩列表（ZipList） 存储小型哈希表或 list/ set O(N) 顺序存储，内存紧凑
跳表（SkipList） 存储有序集合（Sorted Set） O(logN) 高效的有序数据存储

4. Redis 查询数据的全过程

4.1 从 Key 到获取数据的过程：

  1. 输入 Key：客户端向 Redis 发送命令，查询某个特定的 Key（如 GET user:1001）。

  2. 计算哈希值：Redis 根据 Key 计算哈希值（使用哈希算法，如 MurmurHash2）。

  3. 定位哈希桶：Redis 将哈希值映射到全局哈希表中的一个桶。

  4. 查找桶中的数据：

    • 如果桶内的数据是 ZipList，Redis 将遍历列表查找数据。

    • 如果桶内的数据是 哈希表，Redis 将使用哈希表结构直接查找目标数据。

    • 如果数据是 跳表（如在有序集合中），Redis 使用跳表多层链表结构快速定位数据。

      `先根据key值从哈希表（Dict）获取桶位置，在桶中根据链表顺序查找到实际位置，再根据存储的实际类型查找，比如是string类型那他的值存储方式是sds就直接返回，那要是zset类型那他值的存储就可能是压缩表或者跳跃表 就按照压缩表和跳跃表的方式查找 ，其他类型也是如此。`

4.2 执行查询

  • 一旦找到匹配的数据，Redis 会将数据返回给客户端。

  • 如果没有找到数据，Redis 返回空值或错误。

5. Redis 查询数据过程的详细步骤

5.1 根据 key 查找桶的位置

首先，Redis 使用全局哈希表（dict） 来管理所有键值对。每个 key 都会经过哈希函数计算出一个哈希值，然后通过该哈希值定位到哈希表中的一个桶（bucket）。

  • 哈希表（dict） 是一个由多个桶（bucket）组成的数组，每个桶存储多个键值对。桶的位置是根据 key 的哈希值来计算的。

5.2 桶内查找：链表顺序

桶内可能会存储多个键值对，这是因为哈希冲突的存在（即多个 key 可能通过哈希函数计算出相同的哈希值，导致它们被存储在同一个桶中）。为了解决这个问题，Redis 使用了链地址法（链表）来存储冲突的元素。

  • 链地址法：如果多个 key 存储在同一个桶中，它们会形成一个链表，在查找时，需要顺序遍历这些元素，直到找到匹配的 key。

5.3 根据类型查找实际存储位置

每个 Redis 键（key）都有一个与之关联的值（value），并且根据 value 的类型，Redis 会使用不同的数据结构来存储它。

在桶内找到对应的 key 后，Redis 会根据 key 对应的 value 类型来选择不同的数据结构。你提到的 SDS、压缩表（ZipList）、跳跃表（SkipList） 等就是 Redis 存储不同数据类型的方式。

String 类型（SDS）

  • SDS（Simple Dynamic String）：是 Redis 中的字符串类型的存储方式。SDS 是一种高效的字符串表示方法，它为字符串提供了动态扩展和 O(1) 的字符串长度存储方式。
  • 查找过程：当 Redis 存储一个 String 类型 的 key 时，value 会直接存储为 SDS 数据结构。通过 key，Redis 直接返回 SDS 中的内容，操作是 O(1)。

Hash 类型（ZipList 或 HashTable）

  • 小规模数据（ZipList）：当 Hash 中的字段数量较少时，Redis 使用 压缩列表（ZipList） 来存储数据。ZipList 是一个内存紧凑的数据结构，适用于小型的哈希表。
  • 大规模数据（HashTable）：当 Hash 中的字段数量较多时，Redis 会切换到 标准哈希表（HashTable） 来存储这些数据。
  • 查找过程：如果是 ZipList，Redis 需要遍历 ZipList 来查找字段；如果是 HashTable，查找是通过哈希表直接定位的，操作是 O(1)。

ZSet 类型（跳跃表 + 哈希表）

  • 跳跃表（SkipList）：ZSet 的元素按照分数（score）进行排序，Redis 使用跳跃表来存储 ZSet 的数据。跳跃表是一个多层链表，它能够以 O(log N) 的时间复杂度高效地执行查找、范围查询等操作。
  • 哈希表（HashTable）：为了支持快速查找和删除，Redis 同时使用哈希表来存储 ZSet 中的元素。
  • 查找过程：通过 key 定位到 ZSet 后，Redis 使用 跳跃表 来根据分数查找元素。如果需要修改或删除某个元素，还会查询哈希表。

其他类型（List、Set）

  • List：Redis 使用双端链表（QuickList）或压缩列表（ZipList）来存储 List 类型 的数据。双端链表支持 O(1) 的头尾操作，ZipList 则用于小型的列表。
  • Set：Redis 使用哈希表（HashTable）来存储 Set 类型 数据，确保去重并支持快速查找。

总结

  1. 全局哈希表：用于快速查找每个键的值，底层采用哈希算法来决定元素的存储桶。
  2. 桶中的数据结构：
    • ZipList：适合存储小数据，查找时需要遍历。
    • 哈希表：适合存储大量的键值对，查找时间复杂度为 O(1)。
    • 跳表：适用于有序集合，查找时间复杂度为 O(logN)。
  3. Redis 查找数据的过程：通过哈希表的桶定位，再根据数据类型（ZipList、哈希表、跳表等）采用不同的查找方式。

Redis 的高效存储结构使得它在数据量大、查询频繁的情况下，依然能够提供 极高的性能，是现代分布式系统中的重要组成部分。