排序算法:具有可变长度行的大文本文件(以逗号分隔的值)

Question

什么是一个很好的算法来排序大于可用内存(许多10千兆字节)并包含可变长度记录的文本文件？我见过的所有算法都假设1)数据适合内存,或者2)记录是固定长度的.但想象一下我想按"BirthDate"字段(第4个字段)排序的大型CSV文件:

Id,UserId,Name,BirthDate
1,psmith,"Peter Smith","1984/01/01"
2,dmehta,"Divya Mehta","1985/11/23"
3,scohen,"Saul Cohen","1984/08/19"
...
99999999,swright,"Shaun Wright","1986/04/12"
100000000,amarkov,"Anya Markov","1984/10/31"

我知道:

1. 这将在一台机器上运行(未分发).
2. 我运行它的机器将有几个处理器.
3. 我要排序的文件可能比机器的物理内存大.
4. 文件包含可变长度的行.每行包含固定数量的列(分隔符分隔值).文件将按特定字段(即文件中的第4个字段)排序.
5. 一个理想的解决方案可能是"使用这个现有的排序实用程序",但我正在寻找最好的算法.
6. 我不期望一个完全编码的,有效的答案; 更多的事情是"检查出来,这里是它的工作方式,或者这就是为什么它适用于这个问题." 我只是不知道在哪里看......
7. 这不是功课!

谢谢!♥

Answer 1

这类算法称为外部排序。我首先查看维基百科条目。它包含一些讨论和指示。