大型数据集的搜索和排序

Question

我一直在为面试练习一些算法问题，偶然发现了各种各样的问题，这些问题涉及到对来自无限流的数据进行排序，以及设计一个数据结构来搜索数十亿条记录。

1. 描述如何从无限流中一次读取一个整数。
2. 通过大量的元素进行搜索是一个搜索空间。也就是说，你被要求设计一个存储结构和搜索算法来搜索1000亿个数据记录。您可以有多个服务器和多个线程。

以下是我的想法，如果我错了或者有更好的解决方案，请纠正我。

1. 对于从无限流一次读取一个整数的排序，我们可以使用插入排序吗？插入排序的最坏情况是O(n2)对未排序的列表进行排序，但在这种情况下，运行时间可以降到O(logn)。当要将新元素插入到已排序的流中时，我们只需执行对新元素的二进制搜索，并在logn时间插入它。但是我们需要把所有的项目移到1的右边，这样才能得到O(N)。不过，我仍然不确定这是否正确。
2. 我们将使用一个平衡的BST，其中插入和搜索的最坏情况是logN，或者我们只使用一个HashMap，它理想地在O(1)中执行查找，在O(1)中执行插入。然而，当我们处理1000亿条记录时，我们对HashMap的最坏的情况查找将是O(N)和链表实现。

对于这些问题，我仍然没有一个明确的答案。如果有人能提供更多的洞察力，那就太好了！

谢谢!

Answer 1

要对大量数据进行排序，通常分两个步骤进行：

1. 缓冲数据，直到收到一些(通常是非常多)的数据项。然后对这些数据进行排序，并将排序后的块写入磁盘。您将继续这样做，直到收到并排序了所有的数据。
2. 在对所有块进行排序之后，对已排序的块进行k路合并，以创建单个排序文件。

缓冲和排序可以并行进行，如果你有足够的马力。当接收到每个块时，您可以旋转一个线程来对其进行排序，而主线程则继续在一个新块中接收数据。当然，这并不是无限可伸缩的，因为排序一个大缓冲区所需的时间要比接收的时间长得多。因此，您可能必须在接收到的时候将每个块写入磁盘，并有固定数量的后台线程对这些块进行排序。基本算法是一样的，尽管.只是稍微延迟了一下。

如果可以使用多台机器进行搜索，通常会在多台机器之间传播数据。所以如果你有4台机器，每台机器都会得到1/4的数据。当您想要进行搜索时，请让每台机器搜索其数据集以进行匹配记录，并将这些结果传递到某个中心位置，后者对重复项进行排序和删除。

现在，如果您想从一个潜在的无限流中维护一个排序的数据结构(即能够在接收数据时随时进行搜索)，那么您需要一些更动态的东西。一种简单的方法是让您的主排序结构，以及您的“尚未排序”缓冲区。例如，假设您已经收到了数十亿项，您已经对其进行了排序和存储，并且缓冲区大小为100万项。当接收到数据时，在将它们与主数据结构合并之前，将它们存储在内存中。

当收到搜索查询时，搜索主结构，如果使用二进制搜索，将是O(log )，然后按顺序搜索接收缓冲区。当然，顺序搜索有点慢，因为它是顺序的，但是所有的数据都在内存中，所以您不必支付I/O的成本。

当缓冲区填充时，可以使用有效的算法将其与存储的结构合并。

这是基本的想法。有许多方法可以通过多个层次的合并来提高效率，或者使用比二叉树或类似的数据结构更好的数据结构。