algorithm - 搜索和排序大数据集

Question

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

1. Describe how to sort integers read one at a time from an infinite stream

2. Search through a tremendous number of elements is a search space. I.E. You're asked to design a storage structure and search algorithm to search through 100 billion data records. You can have multiple servers and multiple threads.

以上是我的想法，如有错误或有更好的解决办法请指正

1. 要对从无限流中一次读取一个整数进行排序，我们可以使用插入排序吗？插入排序的最坏情况是 O(n2) 来对未排序的列表进行排序，但在这种情况下，运行时间可以降低到 O(logn)。当要将新元素插入到已排序的流中时，我们可以只对新元素执行二进制搜索并在 logn 时间内插入它。但是我们需要将所有项目向右移动 1，这将导致 O(N)。 我仍然不确定这是否正确

2. 我们将使用 Balanced BST，它的插入和搜索最坏情况为 logN，或者我们可以只使用 HashMap，理想情况下它会在 O(1) 中执行查找并在 O(1) 中执行插入。然而，当我们处理 1000 亿条记录时，我们对 HashMap 的最坏情况查找将是 O(N) 和链表实现。

对于这些问题，我仍然没有明确的答案。如果有人可以提供更多见解，那就太好了!

谢谢!

Answer 1

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

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

如果你有足够的能力，缓冲和排序可以并行完成。当接收到每个 block 时，您启动一​​个线程对其进行排序，同时主线程继续接收新 block 中的数据。当然，这不是无限可扩展的，因为对大缓冲区进行排序比接收要花费更长的时间。因此，您可能必须在收到每个 block 时将其写入磁盘，并有固定数量的后台线程对这些 block 进行排序。基本算法是相同的，但...只是延迟了一点时间。

如果您可以使用多台机器进行搜索，您通常会将数据分散到多台机器上。所以如果你有 4 台机器，每台机器得到 1/4 的数据。当您想要进行搜索时，您可以让每台机器搜索其数据集以查找匹配的记录，并将这些结果传送到某个中央位置，中央位置将对重复项进行排序和删除。

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

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

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

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