合并连接大文件的算法

Question

假设我有四个包含我需要处理的信息的大文件(太大以至于无法单独存入内存)。我打算从文件 #1 中的每一行生成一个应用程序级对象(记录)。文件 2-4 每个都有构成此 Record 对象所需的附加信息。例如，文件结构可能如下:

文件#1:
key 、描述

文件#2:
键、元数据、大小

文件#3:
来源、比率、 key

文件#4:
键、开始日期、结束日期

每个文件都有一个列(一行中的已知位置)代表一个唯一的键。这个 key 跨文件共享，但不能保证任何一个文件中存在的每个 key 都存在于其他文件中，这意味着我们只会处理所有文件中存在的 key 子集。文件的行未排序。您能否设计一种算法来通过处理这些文件来生成应用程序级对象？

Answer 1

使用键值存储数据库

数据库是处理大于您的内存的数据集的最佳工具。将您的文件放入键值存储(像 CouchDB 或 Cassandra 这样的 NoSQL DB 会很棒)。使用键查询解决您的问题。

使用排序和二分查找

如果您不能使用数据库，请根据键列对文件进行排序(这可以使用 GNU sort 轻松完成)。您可以使用 key 在 nlogn 时间内访问您的文件。迭代最大的文件，并使用对其他文件的调用来处理每条记录。这样您的磁盘读取可能会被缓存。