c - 使用 Serialize Binary Search Tree 对海量数据进行排序

Question

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

3633223656935182015 2473242774832902432
8472954724347873710 8197031537762113360
2436941118228099529 7438724021973510085
3370171830426105971 6928935600176631582
3370171830426105971 5928936601176631564

我需要将此数据作为键以该键的最小值递增的顺序进行排序。结果必须在 30 分钟内显示在另一个文本文件 (data.out) 中。例如上面的示例结果必须是这样的；

2436941118228099529 7438724021973510085
3370171830426105971 5928936601176631564
3633223656935182015 2473242774832902432
8472954724347873710 8197031537762113360

我决定了；

• 我将使用 input.txt 中的键及其最小值创建一个 BST 树，但这棵树将超过 50GB。我的意思是，此时我有时间和内存限制。

• 所以我将使用另一个文本文件 (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