mergesort - 合并排序中 I/O 访问总数的公式 2b* (1+⌈ log (dm )⁡〖(nr)〗⌉) 是否正确？

Question

我正在研究来自作者 Elmasri 和 Navathe，第 5 版的《数据库系统基础》一书中的数据库，他们几乎在第 15 章开头简要解释了使用归并排序的外部排序。他们将算法分为两个阶段:

1) 排序 :他们使用下一个符号:

b = 我们要排序的数据文件的块数。

nb = 内存中可用于排序的缓冲区(块)数。

nr = 份数。

在这个阶段，我们将尽可能多的数据文件块放入内存，我们使用任何内部排序算法对它们进行排序，并将它们作为临时排序子文件写入。我们对文件的其余块重复此操作，因此我们将获得更多排序的子文件。这些子文件被他们称为“部分”，它们的数量是:

nr = ⌈ b/nb ⌉。

符号 ⌈ ⌉ 表示天花板函数。此阶段的 I/O 成本为 2b ，因为我们需要读取每个块一次(b 次访问)。然后，为了保存所有部分，我们还需要进行 b 访问。

2) 合并 :他们说了类似的话(我用我的解释重写了它以使其更清楚):

结果部分(有序子文件)在一个或多个 channel 中混合。对于每一轮，在内存中保留一个输出块来放置混合的结果，其余的用作输入块，最多可以是 nb - 1，并且其中每个块一次放置一个块有序的部分，目的是混合它们。当输入块少于部分时，需要不止一次通过。此外，由于每个部分可以有多个块，因此每次通过分割为迭代，在每个迭代中放置每个部分的块。

dm = 混合度，即每道可混合的份数。

数 dm 必须等于 (nb - 1) 和 nr 之间的最小值。如果我们把对数的底放在 ( ) 之间，把它的自变量放在〖 〗之间，则通过次数为:

⌈日志(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。那么，pass的次数是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个累积)。

我做错了什么，我该如何继续？

Answer 1

我假设初始传递产生大小为 {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 个块)。

初始 channel 和 3 个合并 channel 各涉及 20 个 I/O，总共 80 个 I/O。