Database System （六）

type

status

date

slug

summary

I/O 回顾

请记住：每当我们将一个页面从内存写入磁盘，或者从磁盘读取一个页面到内存时，就会产生一次 I/O 操作。由于访问磁盘非常耗时，在分析算法性能时，我们只关心算法产生了多少次 I/O 操作，而不是像传统算法分析中那样关注时间复杂度（比如 big-O）。因此，在设计我们的排序算法时，目标就是尽可能减少 I/O 次数。

在统计 I/O 次数时，我们忽略缓冲区管理器可能做的缓存优化。这意味着：一旦我们释放了某个页面（也就是“unpin”了它，并声明我们已经不再使用它），那么下次如果我们再访问这个页面，就一定会产生一次新的 I/O 操作。你可以将这理解为：一旦我们不再使用某个数据页，缓冲区管理器就会将其从缓冲池中驱逐出去。

双路外部归并排序（Two Way External Merge Sort）

我们从一个“可行但不够优秀”的排序算法开始讲起。因为我们无法一次性把所有数据加载进内存，所以必须将数据拆分成小块分别排序，然后将它们合并起来。

为了高效地合并两个列表，它们首先必须是有序的。这提示我们排序算法的第一步应当是对每个数据页中的记录进行排序。我们称这一步为 征服阶段（conquer phase），因为我们是在“征服”单独的页面。

在完成页面内的排序后，我们就可以使用归并排序中的归并算法来将这些页面合并。我们把每次合并的结果称为一个 sorted run（有序串）。有序串是由一组已经排好序的数据页组成的序列。

整个算法的剩余部分就是持续不断地合并这些有序串，直到只剩下一个最终的有序串。那就意味着所有数据已经完全排序好了。

图示流程解释：

初始数据页（上方最初的 8 个框）：

每个框表示一页内的数据，最多只能容纳少量记录，如 “Brian, Jenny”。

Pass 0（征服阶段）

对每页内部排序，例如：Lakshya Jasmine → Jasmine Lakshya

每页现在都是局部有序的页。

Pass 1（第一次归并）

每两页合并为一个有序串（sorted run）：

如 “Brian Jenny” 和 “Jasmine Lakshya” → 合并为 “Brian Jasmine”, “Jenny Lakshya”
注意每一行表示一个页，合并的结果分布到多个页中

Pass 2（第二次归并）

把多个有序串再次归并为更大的有序串。

Pass 3（最终归并）

最后一步归并，将所有数据汇总成一个完整的有序序列：

例如：Angela Brian, Charles Daniel, David Eric, ..., Lakshya Sai

中文术语对照：

英文术语	中文术语
Two-Way Merge Sort	双路归并排序
External	外部（磁盘为主）
Sorted Run	有序串
Conquer Phase	征服阶段
Merging Pass	合并轮次
I/O	输入输出（读写磁盘）

双路归并分析（Analysis of Two Way Merge）

在分析数据库算法时，最重要的指标是算法产生的 I/O 次数，我们就从这里开始分析。

首先注意：每一轮（pass）对数据的处理会产生 次 I/O，其中 NN 是数据页的数量。为什么？因为每一轮都要：

把每个页面从磁盘读入内存（1 次 I/O），

修改后再写回磁盘（1 次 I/O）。

所以每一轮就是次 I/O。

要进行多少轮排序？

我们始终需要做第一轮“征服阶段”（Conquer Phase），所以至少有一轮。

之后每一轮归并排序都会将剩余的有序串数量减半，你应该很自然地想到对数（log）。因为每次都除以 2，所以对数底数是 2。于是我们需要：

轮归并，

总共轮排序（包括初始征服阶段）。

因此，I/O 总次数公式为：

注意：Pass 0（征服阶段）也计入总的归并轮数，并包含在 I/O 成本的计算中。

需要多少内存页（Buffer Pages）？

Buffer Page / Buffer Frame： 就是内存中可容纳一个页的空间。

第一轮（征服阶段）：

每次只排序一个页面 → 只需要 1 个 buffer page 就够了。

接下来的归并阶段：

回顾归并逻辑：我们只需要比较两个有序串中当前最前的值。

因此，只需为每个有序串前部的那一页保留一个 buffer page，不需要整个串都放内存。

假设我们正在归并两个有序串 → 需要 2 个 input buffer pages

我们还需要一个地方将归并结果写出去，这就是 output buffer。

当 output buffer 写满后，刷盘写入磁盘，开始写下一个页。

所以：

归并阶段共需 3 个 buffer pages：

2 个输入缓冲页（input buffer）
1 个输出缓冲页（output buffer）

总结：

该算法最多只用到 3 个内存页，因此无法充分利用更多可用内存，这为我们提供了改进空间。接下来可以设计一个更好的算法，让它能用上所有内存资源。

完全外部排序（Full External Sort）

我们现在假设系统拥有 B 个 buffer 页面（也称为 buffer frames），这是我们在内存中可同时容纳的数据页数。

优化一：改进征服阶段

在之前的双路归并排序中，每次征服阶段只处理一个页。现在我们改进它，在征服阶段（Pass 0）中：

一次性加载 B 个页面

然后对这 B 页内容整体排序，作为一个更长的有序串（sorted run）

这样做的好处是：我们在第一轮之后就能生成更少、但更长的有序串，从而减少后续的合并次数（也就是减少 I/O）。

优化二：改进归并阶段

在双路归并中我们每次只合并两个有序串。现在我们使用了 B 个缓冲页，其中：

保留 1 个用于输出（output buffer）

剩下的 B − 1 个都可以用于输入（input buffers）

所以我们就可以在每一轮归并中，同时归并多达 B − 1 个有序串！

示例（图中流程）

假设我们有 B = 4 个缓冲页：

Pass 0（征服阶段）：

每 4 页作为一组（共 B 页），生成一个长度为 4 的有序串。

Pass 1（归并阶段）：

使用 3 个输入缓冲区（B−1=3），每次合并 3 个有序串为一个更大的串。

所以只需 一轮归并 就能完成全部排序！

这个过程有效地减少了归并轮数，也就大幅减少了总 I/O 成本。

最下方图示含义：

Conquer（征服阶段）：

使用 B 页内存，一次处理 B 页，生成若干 sorted run（共 ⌈N / B⌉ 个）。

Merge（归并阶段）：

每轮使用 B−1 个 input buffers + 1 个 output buffer

每轮将 B−1 个 sorted run 合并成更大的 run

重复直到只剩一个最终有序串

完全外部归并排序的分析（Analysis of Full External Merge Sort）

现在我们来计算改进后的排序算法需要多少次 I/O，使用的方法与“双路归并排序”的分析类似。

征服阶段（Conquer Pass）：

每次处理 B 页，因此会生成大约 ⌈N / B⌉ 个有序串（sorted runs），相比之前更少。

归并阶段（Merging Passes）：

每一轮归并可以将 B−1 个有序串合并为一个更长的串，所以每轮之后有序串数量减少为原来的 1/(B−1)。
所以归并轮数的对数底数从 2 变成了 B−1。

因此，总共需要的轮数为：

💡

其中 1 是征服阶段；

后面的是归并阶段的轮数。

对应的总 I/O 成本为：

💡

总结

项目	Two-Way Merge Sort	Full External Merge Sort
每次处理页面数	1 页	B 页
每次归并数量	2 路归并	B−1 路归并
总 Pass 数
总 I/O 数

可以看到，利用更多内存页可以显著减少归并轮数，从而降低总 I/O 成本。

Practice Questions

1) Students 表，有 1960 页和 8 个 buffer 页

a. 每轮后会产生多少 sorted runs？

Pass 0（征服阶段）：我们每次可装入 8 页

Sorted runs 数量 = ⌈1960 / 8⌉ = 245

从 Pass 1 起，能合并 B-1 = 7 个 sorted runs 每次

所以每轮 sorted run 数会变为原来的 1/7（向上取整）

Pass 1: ⌈245 / 7⌉ = 35
Pass 2: ⌈35 / 7⌉ = 5
Pass 3: ⌈5 / 7⌉ = 1（结束）

✅ 共需要 4 轮（1 个征服 + 3 个归并）

b. 每轮中每个 sorted run 的页数是多少？

Pass 0: 每个 sorted run 有 8 页（except 最后一个可能不满）

Pass 1: 每个 run 是 7 × 8 = 56 页左右

Pass 2: 每个 run 是 7 × 56 = 392 页左右

Pass 3: 最后一个 run 是 5 × 392 = 约1960 页

c. 总共多少次 I/O？

使用公式：

💡

其中 ,

⌈1960 / 8⌉ = 245

⌈log₇(245)⌉ ≈ ⌈2.23⌉ = 3

所以总 I/O = 2 × 1960 × (1 + 3) = 15,680 次 I/O

2) 要在 2 个 Pass 内完成对 1000 页的排序，最少需要多少个 buffer 页？

我们希望满足：

💡

即：

💡

试出最小满足条件的 B：

B = 32 → 32 × 31 = 992

B = 33 → 33 × 32 = 1056 ✅ 满足

所以最小 buffer 页数是 33

3) Sailors 表有 200 页，Pass 0 有 10 buffer，之后只有 5 buffer

a. 每轮后会产生多少 sorted runs？

Pass 0: 每 10 页一个 sorted run → ⌈200 / 10⌉ = 20 runs

之后每轮最多归并 4 个 run（B-1 = 4）：

Pass 1: ⌈20 / 4⌉ = 5
Pass 2: ⌈5 / 4⌉ = 2
Pass 3: ⌈2 / 4⌉ = 1（完成）

✅ 共 4 个 Pass

b. 每个 sorted run 大小：

Pass 0: 10 页左右

Pass 1: 4 × 10 = 40 页

Pass 2: 4 × 40 = 160 页

Pass 3: 2 × 160 = 200 页

c. 总 I/O：

💡

4) True or False:

“增加 buffer 页不会影响 Pass 0 的 I/O 数量”

✅ True

每页都要读+写一次，无论 buffer 页多少，I/O 总是 2N

5) True or False:

“对已排序表排序比乱序表产生更少的 I/O”

❌ False

外部排序总是读每页一次、写每页一次（除非做了特定优化或检测）

所以随机 or 已排序，在默认实现下 I/O 是一样的

Solutions

1) Students 表（1960 页, 8 buffer 页）

a. 每轮产生的 sorted runs：

⟹ 每轮最多处理 8 页 → 1960 ÷ 8 = 245

然后每轮归并 7 个 runs（因为 1 buffer 留作 output）：

Pass 1: 245 ÷ 7 = 35
Pass 2: 35 ÷ 7 = 5
Pass 3: 5 ÷ 7 ≤ 1，完成

✔ 答案是：245, 35, 5, 1

b. 每个 sorted run 的页数：

Pass 0: 8
Pass 1: 8×7 = 56
Pass 2: 56×7 = 392
Pass 3: 1960 页

✔ 答案是：8, 56, 392, 1960

c. 总 I/O 次数：

4 轮 × 2 × 1960 = 15,680

2) 最少需要多少 buffer 页可在 2 轮内完成 1000 页排序？

我们希望满足：

解这个不等式：B ≈ 32.1

⟹ 所以最小整数 B = 33

3) Sailors 表（200 页，Pass 0 用 10 页，其它只用 5 页）

a. Sorted runs 数量：

Pass 0: 200 ÷ 10 = 20
Pass 1: 每轮最多归并 4 个（5-1），→ 20 ÷ 4 = 5
Pass 2: 5 ÷ 4 = 2
Pass 3: 2 ÷ 4 = 1（完成）

✔ 答案是：20, 5, 2, 1

b. 每轮中 run 的大小：

Pass 0: 10 页
Pass 1: 10×4 = 40
Pass 2: 两个 run，分别是 160 和 40 页
Pass 3: 最后是一个完整的 run（200 页）

✔ 答案是：10, 40, (160 和 40), 200

c. 总 I/O：

4 轮 × 2 × 200 = 1600

4) 判断题：

Increasing the number of buffer pages does not affect the number of I/Os in Pass 0

✔ True

每页都要读+写一次 → 与 buffer 数量无关

5) 判断题：

Already sorted tables use fewer I/Os than random ones

❌ False

排序操作无论输入是否已排序，都必须读写每个页面 → I/O 不变