javascript - 如何订购巨大(GB 大小)的 CSV 文件？

Question

背景

我有一个包含数百万行的巨大 CSV 文件。每行都有一个时间戳，我可以用来对其进行排序。

朴素的方法

所以，我的第一个方法显然是通过将其放入内存然后排序来读取整个内容。它并没有像您猜想的那么好......

朴素方法 v2

我的第二个尝试是遵循 MapReduce 背后的想法。

所以，我会将这个巨大的文件分成几个部分，然后对每个部分进行排序。然后我会将所有部分合并到最终文件中。

这里的问题是B部分可能有一条消息应该在A部分。所以最后，即使每个部分都是有序的，我也不能保证最终文件的顺序....

目标

我的目标是创建一个函数，当给定这个巨大的无序 CSV 文件时，可以创建一个具有相同信息的有序 CSV 文件。

问题

订购这么大的数据集的流行解决方案/算法是什么？

Answer 1

What are the popular solutions/algorithm to order data sets this big?

由于您已经得出结论，数据太大而无法在您可用的内存中进行排序/操作，因此流行的解决方案是一个数据库，该数据库将构建基于磁盘的结构来管理和排序比内存中更多的数据.

您可以构建自己的基于磁盘的方案，也可以使用已经完全开发、优化和维护的方案(例如流行的数据库)。您询问的“流行”解决方案是使用数据库来管理/排序大型数据集。这正是它们的构建目的。

数据库

您可以设置一个由您的排序键索引的表，将所有记录插入数据库，然后创建一个按您的键排序的游标并迭代游标，将现在排序的记录一次写入您的新文件时间。然后，完成后删除数据库。

---

分块内存排序，手动合并

或者，您可以进行分块排序，将数据分成可放入内存的较小片段，对每个片段进行排序，将每个排序后的 block 写入磁盘，然后合并所有 block 并读取下一条记录从每个 block 到内存中，从所有 block 中找到最低的一个，将其写入最终输出文件，从该 block 读取下一条记录并重复。使用此方案，合并一次只需要在内存中有 N 条记录，其中 N 是您拥有的已排序 block 的数量(可能少于原始分块 block 排序)。

正如 juvian 提到的，这里概述了像这样的“外部排序”是如何工作的:https://en.wikipedia.org/wiki/External_sorting .

分块内存排序的一个关键方面是确定分块的大小。有许多策略。最简单的方法可能是根据一些简单的测试或什至只是猜测您确定是安全的(一次选择较小的数字来处理就意味着您将将数据拆分到更多文件中)。然后，只需将那么多记录读入内存，对它们进行排序，然后将它们写入已知文件名。重复该过程，直到您读取了所有记录，然后所有记录都位于磁盘上具有已知文件名的临时文件中。

然后，打开每个文件，从每个文件中读取第一条记录，找到您读入的每个记录的最低记录，将其写入最终文件，从该文件中读取下一条记录并重复该过程。当你到达一个文件的末尾时，只需将它从你正在比较的数据列表中删除，因为它现在已经完成了。当没有更多数据时，您就完成了。

---

仅在内存中对键进行排序

如果所有排序键本身都适合内存，但关联数据不适合，那么您可以创建自己的索引并对其进行排序。有许多不同的方法可以做到这一点，但这里有一个方案。

通读整个原始数据，为每条记录将两件事捕获到内存中，排序键和存储该数据的原始文件中的文件偏移量。然后，一旦内存中有所有排序键，就对它们进行排序。然后，一个一个地遍历排序的键，寻找文件中的写入点，读取该记录，将其写入输出文件，前进到下一个键并重复，直到每个键的数据按顺序写入。

---

BTree 键排序

如果所有的排序键都不适合内存，那么你可以得到一个基于磁盘的 BTree 库，它可以让你对大于内存的东西进行排序。您将使用与上述相同的方案，但您会将排序键和文件偏移量放入 BTree 中。

当然，将文件中的实际数据本身放入 BTree 中只是更进一步，然后您就拥有了一个数据库。