使用序列化二进制搜索树对海量数据进行排序

Question

我有50 GB的结构化数据(作为键/值)，这些数据存储在文本文件中(input.txt /键和值是63位无符号整数)；

3633223656935182015 2473242774832902432
8472954724347873710 8197031537762113360
2436941118228099529 7438724021973510085
3370171830426105971 6928935600176631582
3370171830426105971 5928936601176631564

我需要将这些数据按键的最小值按递增顺序排序。结果必须在另一个文本文件(data.out)中显示在30分钟以下。例如，对于上面的示例，结果必须是这样的；

2436941118228099529 7438724021973510085
3370171830426105971 5928936601176631564
3633223656935182015 2473242774832902432
8472954724347873710 8197031537762113360

我决定这么做；

• 我将创建一个具有最小值的input.txt键的BST树，但是这个树将超过50 be。我的意思是，我现在有时间和记忆的限制。
• 因此，我将使用另一个文本文件(tree.txt)，并将BST树序列化到该文件中。
• 之后，我将使用有序遍历遍历树，并将顺序数据写入data.out文件。

我的问题主要是序列化和反序列化部分。如何序列化这种类型的数据？我想对序列化的数据使用INSERT操作。因为我的数据比内存大。我不能在记忆里做这个。实际上，我想使用文本文件作为内存。

顺便说一句，我对这类东西很陌生。如果与我的算法步骤有冲突，请警告我。任何想法，技术和代码样本将是有帮助的。

OS: Linux
Language: C
RAM: 6 GB

注意:我不允许使用内置函数，如排序和合并。

Answer 1

考虑到您的文件的行大小似乎相同--大约40个字符，总共大约有1250000000行--我会通过命令将输入文件拆分为更小的文件：

split -l 2500000 biginput.txt

然后我会把每一种

for f in x*; do sort -n $f > s$f; done

最后我会把它们合并

sort -m sx* > bigoutput.txt