mergesort - 合并排序中 I/O 访问总数的公式 2b* (1+⌈ log (dm )〖(nr)〗⌉) 是否正确？
问题描述
我正在从作者 Elmasri 和 Navathe 第 5 版的《数据库系统基础知识》一书中研究数据库，他们几乎在第 15 章开头简要解释了使用合并排序的外部排序。他们将算法分为两个阶段：
1）排序：他们使用下一个符号：
- b = 我们要排序的数据文件的块数。
- nb = 内存中可用于排序的缓冲区（块）数。
- nr = 份数。
在这个阶段，我们将尽可能多的数据文件块放入内存，我们使用任何内部排序算法对它们进行排序，并将它们写为临时排序的子文件。我们对文件的其余块重复此操作，因此我们将获得更多排序的子文件。这些子文件被他们称为“部分”，它们的数量是：
nr = ⌈ b / nb ⌉。
符号 ⌈ ⌉ 表示上限函数。此阶段的 I/O 成本为2b，因为我们需要读取每个块一次（b 次访问）。然后，为了保存所有部分，我们还需要进行 b 访问。
2）合并：他们说了类似的话（我用我的解释重写了它以使其更清晰）：
生成的部分（有序子文件）在一个或多个通道中混合。对于每一遍，在内存中保留一个输出块以放置混合结果，其余用作输入块，最大可达 nb - 1，并且每次放置一个块有序的部分，目的是混合它们。当输入块少于部分时，需要不止一次通过。此外，由于每个部分可以有多个块，因此每个 pass 被细分为迭代，在每个迭代中放置每个部分的一个块。
- dm = 混合程度，即每次可以混合的份数。
数字 dm 必须等于 (nb - 1) 和 nr 之间的最小值。如果我们将对数的底放在 ( ) 之间，并将其参数放在〖〗之间，则通过次数为：
⌈ log(dm)〖nr〗⌉。
我感到困惑的是，他们说这个阶段的成本是
2b * ⌈ log(dm)〖nr〗⌉,
所以他们基本上是在暗示，在每次传递中，我们只需要读取每个块一次并写入一次，但我不确定这是否正确。我怀疑可能需要更多访问权限。
因此，算法的总成本为 2b + 2b * ⌈log(dm)〖nr〗⌉
= 2b (1 + ⌈log(dm)〖nr〗⌉)
其实他们不是这么说的，而是：“一般情况下，对数取dm为底，表示访问块数的表达式如下：”
(2*b) + (2* (b* (log(dm)〖nr〗))),
这基本上是一样的。
例如，假设我们有一个包含 10 个块的文件，每个块有 3 条记录。内存（缓冲池）中的可用空间大小为 4 个块。让我们用 || 分隔文件的块
29,11,27 || 22,1,20 || 7,30,26 || 9,8,21 || 13,24,15 || 23,4,28 || 17,12,10|| 5,3,6 || 16,19,2 || 25,14,18
导致排序阶段的部分“nr”的数量是⌈10/4⌉ = 3。
p1 = 1,7,8 || 9,11,20 || 21,22,26 || 27,29,30
p2 = 3,4,5 || 6,10,12 || 13,15,17 || 23,24,28
p3 = 2,14,16 || 18,19,25
在meging阶段，dm = minimum{nb-1, nr} = minimum{4-1,3} = 3。那么，通过的次数是log(3)〖3〗=1。根据公式，我们在这个阶段应该进行 20 个 I/O。
迭代 1：我们将这些块放入内存中：
1,7,8 || 3,4,5 || 2,14,16
它们变成了这个（一次一个块，保存在磁盘中）：
1,2,3 || 4,5,7 || 8,14,16
6 访问磁盘。
迭代 2：
9,11,20 || 6,10,12 || 18,19,25
他们变成了这样：
6,9,10 || 11,12,18 || 19,20,25
6次访问磁盘（已经累积了12次）。
我做错了什么，我该如何继续？
解决方案
我假设初始传递产生大小为 {3,3,3,3,3,3,3,3,3,3}（10 个块，30 条记录）的排序运行。我不确定 dm，但合并通道的数量是 ⌈log3⌉(10) = 3。第一次合并通道导致大小为 {9,9,9,3}（10 个块）的排序运行。第二次合并通过导致大小为 {27,3}（10 个块）的排序运行。第三次合并通过导致单个排序运行 {30}（10 个块）。
初始通道和 3 个合并通道各涉及 20 个 I/O，总共 80 个 I/O。