大数据集的搜索和排序

Question

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

1. 描述如何对从无限流中一次读取一个的整数进行排序

2. 对大量元素进行搜索就是一个搜索空间。IE 你被要求设计一个存储结构和搜索算法来搜索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的数据。当您想要进行搜索时，您让每台机器在其数据集中搜索匹配的记录，并将这些结果传送到某个中心位置，由该位置进行排序并删除重复项。

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

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

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

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