Database System （五）
2025-4-12
| 2025-4-12
Words 3229Read Time≈ 9 min
type
status
date
slug
summary
tags
category
icon
password

动机

有时候，排序对于我们要解决的问题来说有些小题大做。我们常常只是想把相同的值归为一组，而并不关心这些值出现的顺序（可以类比数据库中的 GROUP BY 或去重操作）。在数据库中，将相同的值聚集到一起的过程被称为 哈希（hashing）。
我们无法像在 61B 课程中学到的那样用标准方式构建哈希表，原因与我们在上一篇笔记中无法使用快速排序类似：我们无法将所有数据都放入内存中！
接下来我们将看看如何构建一个高效的 外部哈希算法（out-of-core hashing algorithm）。

通用策略

由于我们无法将所有数据一次性放入内存中，因此我们需要构建多个不同的哈希表，并在最后将它们拼接（concatenate）在一起。然而，这个想法存在一个问题：
如果我们构建了两个独立的哈希表，而它们中都包含了相同的值（例如，“Brian”同时出现在两个表中），那在拼接这些哈希表时，就会导致某些“Brian”没有被聚集在一起。
为了解决这个问题，在我们将数据构建为哈希表之前，必须确保一个条件：
如果某个值已经出现在内存中，那么它的所有出现也都必须在内存中。
换句话说，如果“Brian”至少在内存中出现了一次，那么我们只有在“Brian”的所有出现都在内存中的时候，才能构建哈希表。
这个策略可以确保：每个值只会出现在一个哈希表中，从而使得这些哈希表在最终拼接时是安全的（不会打乱聚集）。
notion image

哈希的缺点

需要注意的是，哈希非常容易受到数据倾斜（data skew）的影响。 数据倾斜指的是：我们要哈希的值并不遵循均匀分布。由于哈希的特性——相同的值会被哈希到相同的分区，因此如果某个值出现很多次，那它所属的分区就会非常大，导致分区不均衡，这对我们的算法是不利的。
另外，并不是所有哈希函数都是“理想”的。
理想情况下，我们的哈希函数应该是均匀哈希函数（uniform hash function），能将数据平均分散到不同分区中。但实际上，很多哈希函数并不均匀，会使数据分布很不平衡。
本课程中，默认使用均匀哈希函数，除非另有说明。
图中的约定：
  • 圆柱体 = 磁盘操作；
  • 方块 = 内存操作；
  • 箭头 = 磁盘和内存之间的数据流动。

图一：普通分治（无需递归）

分为两个阶段：
notion image

Divide（分阶段，用哈希函数 ）

  • 从磁盘读取数据到 1 个输入缓冲区；
  • 使用 B−1个缓冲区将数据哈希为 B−1个分区；
  • 每个分区大小约为 。

Conquer（治阶段，用哈希函数 ）

  • 对每个分区，在内存中构建哈希表；
  • 将哈希结果写回磁盘。

图二：递归分区（用于处理超大分区）

notion image
当某个分区的大小 > 页，无法直接进入 conquer 阶段时，进行递归处理：
  1. Divide（第一层）：用 把整个数据分成 个分区；
  1. Divide（第二层）：对于大于 页的灰色分区，用新的哈希函数 再次进行分区；
  1. Conquer（治）：对每个子分区，分别构建哈希表并写回磁盘；
  1. 重复这个过程，直到所有分区大小都 ≤ 页。

完整的外部哈希过程示例（Example）

notion image
我们假设系统中有 个缓冲页可用。
还假设：
  • Brian 和 Eric 在 第一轮哈希函数中映射到相同的值；
  • 但在 第二轮哈希函数中，它们映射到不同的值；
  • 而 Jamie 和 Lakshya 在 第一轮哈希函数中映射到同一个值。

第一轮分区（Partitioning Pass 1）

  • 输入数据被分为两个分区：
    • Partition 0（4 页）：包含了很多 Brian 和 Eric；
    • Partition 1（2 页）：包含 Jamie 和 Lakshya。
  • Partition 1 的大小 ≤ ，可以直接进行哈希；
  • 但 Partition 0 太大（超过 B 页），必须继续递归分区。

第二轮分区（Partitioning Pass 2）

对 Partition 0 继续分区为：
  • Partition 0.a：2 页，主要是 Eric；
  • Partition 0.b：2 页，主要是 Brian。

Conquer 阶段（最终哈希）

现在所有的分区都 ≤ 页，可以分别进行哈希表构建：
  • Partition 0.a → 构建 Eric 的哈希表；
  • Partition 0.b → 构建 Brian 的哈希表；
  • Partition 1 → 构建 Jamie 和 Lakshya 的哈希表。
最终结果中，所有相同的值（Brian、Eric、Jamie、Lakshya）都被聚集在一起，达成了“分组但不排序”的目标。

外部哈希分析（Analysis of External Hashing）

我们无法像分析排序算法那样，给出一个简单的公式来计算 I/O 次数，因为我们不知道每个分区到底有多大。这里有几点很重要的认知：
  • 分区过程可能会导致总页数增加！
      • 看下面这个例子：每页能存两个整数，原始数据有 3 页：
      假设 ，我们将其分为两个分区，使用哈希函数使得：
    • 值 1 和 3 哈希到分区 1；
    • 值 2 和 4 哈希到分区 2。
      • 分区后结果如下：
      → 原来只有 3 页，现在有 4 页！这说明在分区时可能会产生额外的页数。

如何计算总 I/O 成本？

不能直接用简单公式计算每一轮的 I/O，因此需要逐轮分析每一轮中：
  • 读取（read）了哪些页
  • 写出（write）了哪些页
我们定义如下变量：
  • ：总共的分区轮数；
  • ：第 轮中需要读取的页数；
  • ：第 轮中需要写出的页数；
  • ：最终我们要构建哈希表的总页数（即分区完成后的页总数）。
公式如下：
含义：
  • ：所有分区轮中读取和写入的总开销；
  • ：最终构建哈希表时的读+写操作（每个页需要读一次再写一次）。

四个重要性质说明：

  1. ：第一轮必须读入所有 NN 页数据；
  1. ：每一轮写出的页数 ≥ 读入的页数；
  1. ：写出的页数 ≥ 下一轮需要读入的页数；
  1. ：最终哈希所用的页总数 ≥ 初始数据页数。
解释：
  • 性质 1 是显然的，第一轮要读所有页；
  • 性质 2 说明分区过程中页数可能增加（如示例所示）；
  • 性质 3 表示虽然页数可能增长，但我们不会在下一轮中读取比上一轮写出还多的页；
  • 性质 4 说明最终的哈希表会占用至少与原始数据一样多的页数，分区只会增加页数，不会减少。
notion image

练习题：

1)

How many IOs does it take to hash a 500 page table with B = 10 buffer pages? Assume perfect hash functions.
  • 初始页数 N = 500
  • 缓冲页数 B = 10 → 可分区数 = B - 1 = 9
  • 每轮哈希后，每个分区约为：
      • 页左右，远大于内存能容纳的 B 页 → 需要递归。
这其实是典型的 B 页缓冲对 N 页数据进行外部哈希所需的 I/O 总数。
我们用公式：
但因为是完美哈希函数，分布均匀，每次分区页数减小为：
估算需要几轮：
  • Pass 1：500 / 9 ≈ 56
  • Pass 2：56 / 9 ≈ 7（可进内存）
→ 需要两轮分区（Pass 1 + Pass 2）+ 1 次 Conquer
每轮都要读写全部数据页：
  • 第 1 轮：读 500 + 写 500 = 1000 I/Os
  • 第 2 轮：读 500 + 写 500 = 1000 I/Os
  • 最终构建哈希表：再读 500 + 写 500 = 1000 I/Os
✅ 总计 I/O：3000 次

2)

Hash 30-page table, B = 6 buffer pages. 1 partition gets 10 pages, others evenly distributed. How many I/Os?
  • 个分区
  • 一开始一个分区拿走了 10 页，其它 20 页分成 4 份：每个 5 页
只有这个 10 页的分区太大 → 需要单独递归处理。
分区 Pass 1：
  • 读 30 页，写 30 页 → 60 I/Os
分区 Pass 2：（仅对那 10 页）
  • 假设完美哈希，将其分为 ≤ 5 页的小分区 → 无需再递归
  • 读 10，写 10 → 20 I/Os
Conquer Pass：
  • 全部数据 = 30 页 → 读 + 写 = 60 I/Os
✅ 总计：60 + 20 + 60 = 140 I/Os

3)

If we have 20 buffer pages, what is the minimum table size such that recursive partitioning is required?
只用一轮不递归的外部哈希时，每个分区 ≤ B 页：
  • 分区数 = B−1=19B - 1 = 19，每个分区最多能容纳 B 页 → 数据总量上限为
再多一页就需要递归：
✅ 最小页数 = 381

4)

With B buffer pages and page table, how many passes needed? (Assume perfect hash)
每轮分区后页面缩小为 ：
  • 第一轮后：
  • 第二轮： → fit in memory
✅ 需要两轮分区 + 1 Conquer → 总共 3 次 Pass（两轮分区 + 构建哈希）

5)

With B = 10, what's the smallest table size such that it requires at least two partitioning passes?
即至少 三次遍历：2 轮分区 + 1 次构建
我们找最小的 ，使得分两轮后还不能 fit in memory：
  • 1st pass：
  • 2nd pass：
  • 若 ，说明需要第三轮
解：
✅ 最小值为 811 页

解答

题目 1 解答总结：3209 次 I/O

  • 第一轮分区：500 页分为 9 份，每份 56 页（向上取整），共写出 504 页
      • → 读 500、写 504，共 1004 次 I/O
  • 第二轮递归分区：504 页分为 9×9 = 81 个分区，每个分区约 7 页
      • → 读 504、写 567（81×7） → 共 1071 次 I/O
  • Conquer 阶段：读 567、写 567 → 1134 次 I/O
✅ 总计：1004 + 1071 + 1134 = 3209 次 I/O

题目 2 解答总结：140 次 I/O

  • 第一轮：30 页全部读入，写出 5×4 + 10 = 30 页 → 60 次 I/O
  • 对于 10 页的那个分区递归分区为 5 份（每份 2 页）
      • → 读 10、写 10 → 20 次 I/O
  • Conquer 阶段：共 10 个小分区，每个读 + 写：10×2 = 20 次 I/O
      • 加上之前的 4 个正常分区：4×2 = 8 次 I/O
✅ 总计：60 + 20 + 60 = 140 次 I/O

题目 3 解答总结：381 页

  • B = 20，最多可以分成 19 个分区；
  • 每个分区最多容纳 B 页 → 19×20=38019 × 20 = 380 页是极限；
  • 想要保证一定触发递归 → 再加 1 页：381 页

题目 4 解答总结：3 次 Pass

  • 表大小为 B2B^2
  • 一轮后每个分区大小：，仍超出内存；
  • 再一轮后：，可以 fit in memory；
  • 所以需要 两次分区 + 一次构建哈希表 → 共 3 次 Pass

题目 5 解答总结：91 页

  • B=10B = 10 时，一次分区最多支持 (B−1)×B=90(B-1) × B = 90 页；
  • 想要至少触发第二轮分区 → 表大小要大于 90 → 91 页
Relate Posts :
数据库
  • database
    • Database System （六）DS4.2 Query 相关 设计
    Loading...
    Catalog
    0%