外部排序和外部合并之间的区别

Question

我在postgresql里看到有两个独立的算法叫做外部排序和外部合并进行排序。我觉得两者是一样的。据我所知，外部排序是一个排序算法的集合，当整个批次无法在内存(RAM)中排序时，它处理大量数据的排序，并有两个阶段，第一阶段是对小块数据进行排序并将其存储在临时文件中，第二阶段是合并所有这些子文件以获得最终数据集。

我还知道外部合并排序算法是外部排序技术的一个示例。

所以在我的例子中，外部排序和外部合并不是几乎一样吗？我想知道区别以及何时使用这些算法（在什么类型的数据上）。

PS:对于相同类型的数据，外部合并要比外部排序花费更长的时间

Answer 1

我想你很困惑。

“合并排序”绝对是排序算法的一种类型。其他排序算法有快速排序、气泡排序、堆排序等。

然而，在数据库中(我一般会说在Dag中)，< code>merge指的是稍微不同的东西。合并是将两个排序后的数据集进行合并。它可以通过在并行遍历两个元素时逐个比较元素来做到这一点。

这与合并排序算法有关。这种合并是在幕后发生的。但是在这种情况下，合并运算符正在合并已经排序的列表。

我还应该指出，mer是许多数据库中允许在单个语句中进行插入和更新的语句。Postgres中并非如此（它在冲突中使用），但它是该域中“合并”的另一种用法。