双向多向归并排序

Question

这是“数据库系统全书第二版”一书中的一个问题-第15章:基于排序的两遍算法。有时，如果我们把最后一个子列表留在内存中，就有可能节省一些磁盘I/O。甚至可以使用少于块的子列表来利用这种效果。这样可以节省多少磁盘I/O？

我计算出，您将原始关系划分为子列表，并在第一次遍历中对它们进行排序，并将最后一个列表保留在内存中，这将占用不到M-1个块。那么你是如何进行排序的呢？

Answer 1

这只是一个猜测，但我怀疑答案可以描述如下。标准的“一次一级”合并排序如下所示：

1 1 1 1 1 1 1 1
--- --- --- ---  -- pass 1
 2   2   2   2
 -----   -----   -- pass 2
   4       4
   ---------     -- pass 3
       8

请注意，在进入下一个级别之前，我们对输入数据执行了一次完整的传递。

另一种选择是“一次子树”合并排序，如下所示：

1 1 1 1 1 1 1 1
--- | | | | | |
 2  --- | | | |
 |   2  | | | |
 -----  | | | |
   4    --- | |
   |     2  ---
   |     |   2
   |     -----
   |       4
   ---------
       8

在这里，我们正在将每个子树与其相同高度的邻居合并，只要那个邻居已经构建好了。我们做了相同数量的工作，但局部性得到了改善。

干杯。