sorting - 两遍多路归并排序？

Question

如果我有一个不适合内存的关系 (SQL)，并且我想使用 TPMMS(两遍多路合并排序方法)对该关系进行排序。我如何将表划分为适合内存的子表(以及多少个)，然后合并它们？假设我正在使用 C#。

Answer 1

我还没有找到两遍多路合并排序的当前定义，但“外部排序”理论(数据太大而无法放入内存)几乎是标准的。任何一本像样的算法书籍都会涵盖它；除此之外，您可以看看 Knuth、Sedgewick 或(对于软件考古学家)Kernighan & Plauger Software Tools .

基本技术很简单:

1. 读取数据，直到没有剩余空间。
2. 排序。
3. 写入临时文件。
4. 从 1 开始重复，直到没有数据可供读取。
5. 你知道你有多少个临时文件，N。
6. 您需要确定一次可以读取多少个文件，M。
7. 如果 N > M，则您设计合并阶段，以便最后一个阶段将合并 M 个文件。
8. 您将 M 个文件集合并到新的临时文件中，直到到达最后一次合并。
9. 将最后一组 M 个文件(如果 N < M，则合并 N 个)写入最终目标。

所有这些都非常标准 - 但也有一些挑剔的细节需要正确处理。

AT&T 的 Unix 系统读物第二卷中有一篇很好的文章，名为“构建工作排序例程的理论与实践”，如果您认真学习如何处理外部排序，您应该找到并阅读该文章。然而，当您阅读它时，请记住，自本书编写以来，机器已经发生了巨大的变化，拥有千兆字节的主内存(而不是兆字节)和兆兆字节的磁盘空间(或 SSD - 也不是兆字节)。