双向多路归并排序

Question

这是《数据库系统完全指南》第二版第15章“基于排序的两遍算法”的问题：“有时，如果我们将最后一个子列表保留在内存中，则可以节省一些磁盘I / O。甚至使用少于块的子列表也可能有利用这种效果的意义。这种方法可以节省多少磁盘I / O？”

我发现您需要将原始关系划分为子列表并在第一遍排序时对其进行排序，将最后一个列表保留在内存中，并且它将占用少于M-1块。那么如何进行排序呢？

- Minh Pham

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

在这里，我们将每个子树与其同一高度的邻居合并，一旦该邻居被构建，就立即进行合并。我们做了同样数量的工作，但是提高了局部性。

干杯。

- Rafe