双通多路合并排序？

Question

如果我有一个不适合内存的关系(SQL),我想使用TPMMS(两遍多路合并排序方法)对关系进行排序.我如何将子表中的表(以及多少)除以内存并合并它们？假设我正在使用C#.

Answer 1

我没有追求目前两通道多路合并排序的定义,但是"外部排序"理论(数据太大而无法适应内存)几乎是标准的.任何体面的算法书都会涵盖它; 在许多其他人中,你可以看看Knuth,Sedgewick或(对于软件考古学家)Kernighan&Plauger 软件工具.

基本技术很简单:

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

一切都非常标准 - 但是有一些挑剔的细节可以做对.

在AT&T的Unix系统读物第二卷中有一篇很好的文章称为"构建工作排序程序中的理论与实践",如果你认真学习如何处理外部排序,你应该找到并阅读.但是,当您阅读它时,请记住机器自写入以来发生了巨大变化,主内存(而不是兆字节)和太字节磁盘空间(或SSD - 也代替兆字节).