database - 内部排序，使用两个堆解释的锦标赛排序算法

Question

我试图理解以下 tournament sort (replacement selection)，是一种在主存中做排序的排序算法。

任何解释这是如何工作的？

Keep two heaps in memory, H1 and H2
read B-2 pages of records, inserting into H1;  #B is buffer size

while (records left) {
  m = H1.removemin();  
  put m in output buffer;
  if (H1 NOT empty)
       read in a new record r (use 1 buffer for input pages);
       if (r < m)  
           H2.insert(r);
       else        
           H1.insert(r);
 else
      H1 = H2;  
      H2.reset();  
      start new output run; 
}
H1.output();  
start new run;  
H2.output();

Answer 1

替换选择技术特别令人感兴趣，因为生成的运行的预期长度是可用主内存大小的两倍。这种估计首先由 E.H. 提出。 E.F. Moore 的 friend ，后来由 E.F. Moore 描述。在现实世界的应用程序中，输入数据通常不是随机的(即，它通常表现出某种程度的预排序)。在这种情况下，替换选择生成的运行往往包含超过 2m 的记录。事实上，对于最好的情况，即当输入数据已经排序时，替换选择只会产生一次运行。

给定一组元组记录 status ，其中 record 是从未排序的输入中读取的记录，而 status 是一个 bool 标志，指示记录是事件的还是非事件的。事件记录是当前运行的候选记录，而不活动记录为下一次运行保存。该算法背后的思想如下:假设主内存大小为 m，我们从未排序的输入数据中读取 m 条记录，将其状态设置为事件。然后，选择具有最小键和事件状态的元组并将其移动到输出文件。当一个元组被移动到输出(选择)时，它的位置被输入数据中的另一个元组占据(替换)。如果最近读取的记录小于刚刚写入的记录，则其状态设置为inactive，这意味着它将被写入到下一次运行。一旦所有元组都处于非事件状态，则关闭当前运行文件，创建一个新的输出文件，并将所有元组的状态重置为事件状态。

您可以阅读更多关于替换选择的信息 here .