merge-sort 中 I/O 访问总数的公式 2b* (1+⌈ log (dm )〖(nr)〗⌉) 是否正确？
Is the formula 2b* (1+⌈ log (dm )〖(nr)〗⌉) for the total of I/O access in merge-sort correct?
我正在从作者 Elmasri 和 Navathe 的书 数据库系统基础知识 中学习数据库，第 5 版，他们几乎在一开始就使用合并排序简要解释了外部排序第 15 章。他们将算法分为两个阶段：
1）排序：他们使用下一个表示法：
- b = 我们要排序的数据文件的块数。
- nb = 内存中可用于排序的缓冲区（块）数。
- nr = 份数。
在这个阶段，我们将尽可能多的数据文件块放入内存，我们使用任何内部排序算法对它们进行排序，并将它们写为临时排序子文件。我们对文件的其余块重复此操作，因此我们将获得更多排序的子文件。这些子文件就是他们所说的"portions"，它们的数量是：
nr = ⌈ b / nb ⌉.
符号⌈⌉表示上限函数。这个阶段的 I/O 成本是 2b，因为我们需要读取每个块一次（b 次访问）。然后，为了保存所有部分，我们还需要进行 b 次访问。
2) Merging：他们说了类似的话（我用我的解释重写了它以使其更清楚）：
生成的部分（有序子文件）混合在一个或多个 遍 中。对于每一遍，在内存中保留一个输出块用于放置混合的结果，其余用作输入块，最多为 nb - 1，并且每次放置一个块订购的部分，目的是将它们混合。当输入块少于部分时，需要不止一次通过。此外，由于每个部分可以有多个块，因此每个通道被细分为 迭代 ，在每个迭代中放置每个部分的块。
- dm = 混合度，即每次pass可以混合的份数。
数字 dm 必须等于 (nb - 1) 和 nr 之间的最小值。如果我们把对数的底放在( )之间，它的参数放在〖〗之间，通过的次数是：
⌈ log(dm)〖nr〗⌉.
我混的部分是他们说这个阶段的成本是
2b * ⌈ log(dm)〖nr〗⌉,
所以他们基本上是在暗示在每次传递中我们只需要读取每个块一次并写入一次，但我不确定这是否正确。我怀疑可能需要更多访问权限。
因此算法的总开销为2b + 2b * ⌈log(dm)〖nr〗⌉
=2b(1+⌈log(dm)〖nr〗⌉)
其实他们不是这么说的，而是："In general, the logarithm is taken in base dm and the expression indicating the number of blocks accessed is as follows:"
(2*b) + (2* (b* (log(dm)〖nr〗))),
基本相同
例如，假设我们有一个包含 10 个块的文件，每个块有 3 条记录。内存（缓冲池）中可用的 space 有 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次）
我做错了什么，我该如何继续？
我假设初始传递生成大小为 {3,3,3,3,3,3,3,3,3,3} 的排序 运行s（10 个块，30 条记录）。我不确定 dm，但合并传递的次数是 ⌈log3⌉(10) = 3。第一次合并传递导致大小为 {9,9,9,3} 的排序 运行s（10 个块).第二次合并通过导致大小为 {27,3}（10 个块）的排序 运行s。第三次合并通过导致单个排序的 运行 {30}（10 个块）。
初始通道和 3 个合并通道各涉及 20 个 I/O，总共 80 个 I/O。
我正在从作者 Elmasri 和 Navathe 的书 数据库系统基础知识 中学习数据库，第 5 版，他们几乎在一开始就使用合并排序简要解释了外部排序第 15 章。他们将算法分为两个阶段：
1）排序：他们使用下一个表示法：
- b = 我们要排序的数据文件的块数。
- nb = 内存中可用于排序的缓冲区（块）数。
- nr = 份数。
在这个阶段，我们将尽可能多的数据文件块放入内存，我们使用任何内部排序算法对它们进行排序，并将它们写为临时排序子文件。我们对文件的其余块重复此操作，因此我们将获得更多排序的子文件。这些子文件就是他们所说的"portions"，它们的数量是：
nr = ⌈ b / nb ⌉.
符号⌈⌉表示上限函数。这个阶段的 I/O 成本是 2b，因为我们需要读取每个块一次（b 次访问）。然后，为了保存所有部分，我们还需要进行 b 次访问。
2) Merging：他们说了类似的话（我用我的解释重写了它以使其更清楚）：
生成的部分（有序子文件）混合在一个或多个 遍 中。对于每一遍，在内存中保留一个输出块用于放置混合的结果，其余用作输入块，最多为 nb - 1，并且每次放置一个块订购的部分，目的是将它们混合。当输入块少于部分时，需要不止一次通过。此外，由于每个部分可以有多个块，因此每个通道被细分为 迭代 ，在每个迭代中放置每个部分的块。
- dm = 混合度，即每次pass可以混合的份数。
数字 dm 必须等于 (nb - 1) 和 nr 之间的最小值。如果我们把对数的底放在( )之间，它的参数放在〖〗之间，通过的次数是：
⌈ log(dm)〖nr〗⌉.
我混的部分是他们说这个阶段的成本是
2b * ⌈ log(dm)〖nr〗⌉,
所以他们基本上是在暗示在每次传递中我们只需要读取每个块一次并写入一次，但我不确定这是否正确。我怀疑可能需要更多访问权限。
因此算法的总开销为2b + 2b * ⌈log(dm)〖nr〗⌉
=2b(1+⌈log(dm)〖nr〗⌉)
其实他们不是这么说的，而是："In general, the logarithm is taken in base dm and the expression indicating the number of blocks accessed is as follows:"
(2*b) + (2* (b* (log(dm)〖nr〗))),
基本相同
例如，假设我们有一个包含 10 个块的文件，每个块有 3 条记录。内存（缓冲池）中可用的 space 有 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次）
我做错了什么，我该如何继续？
我假设初始传递生成大小为 {3,3,3,3,3,3,3,3,3,3} 的排序 运行s（10 个块，30 条记录）。我不确定 dm，但合并传递的次数是 ⌈log3⌉(10) = 3。第一次合并传递导致大小为 {9,9,9,3} 的排序 运行s（10 个块).第二次合并通过导致大小为 {27,3}（10 个块）的排序 运行s。第三次合并通过导致单个排序的 运行 {30}（10 个块）。
初始通道和 3 个合并通道各涉及 20 个 I/O，总共 80 个 I/O。