Ron*_*rra 6 mergesort external-sorting database-optimization
我正在从Elmasri和Navathe的作者，第5版的数据库系统基础一书中研究数据库，并且几乎在第15章开始时，他们都使用合并排序简要地解释了外部排序。他们将算法分为两个阶段：
1）排序：他们使用下一个符号：
在此阶段中，我们将尽可能多的块放入数据文件中，使用任何内部排序算法对它们进行排序，并将它们写入为临时排序的子文件。我们在文件的其余块中重复此操作，因此我们将获得更多排序的子文件。这些子文件被它们称为“部分”，它们的数量是：
nr =？b / nb？。
符号？？表示上限功能。此阶段的I / O成本为2b，因为我们需要一次读取每个块（b次访问）。然后，要保存所有部分，我们还需要进行b访问。
2）合并：他们说类似的话（我用我的解释重写了它，以使其更清楚）：
生成的部分（有序子文件）以一遍或多遍混合。每次通过时，将在内存中保留一个输出块，以放置混合结果，其余部分用作输入块，最大可达nb-1，并且每个块一次放置一个块有序部分，目的是将它们混合。当输入块少于部分时，需要多次通过。另外，由于每个部分可以具有一个以上的块，因此将每个遍细分为迭代，每个迭代中都放置了每个部分的块。
数字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
在合并阶段，dm =最小{nb-1，nr} =最小{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，但合并传递的数量是 \xe2\x8c\x88log3\xe2\x8c\x89(10) = 3。第一个合并传递导致大小为 {9,9,9,3 的排序运行}（10 个块）。第二次合并过程导致大小为 {27,3}（10 个块）的排序运行。第三次合并过程产生单个排序运行 {30}（10 个块）。
\n\n初始传递和 3 次合并传递各涉及 20 个 I/O，总共 80 个 I/O。
\n