搜索和排序大数据集
Searching and sorting large data set
我一直在为面试练习一些算法问题，并偶然发现了各种问题，这些问题涉及对来自无限流的数据进行排序，并设计一个数据结构来搜索数十亿条记录
Describe how to sort integers read one at a time from an infinite stream
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.
以上是我的想法，如有错误或有更好的解决方法请指正
对于从无限流中一次读取一个整数进行排序，我们可以使用插入排序吗？插入排序的最坏情况是 O(n2) 对未排序的列表进行排序，但在这种情况下 运行 时间可以降低到 O(logn)。当要将新元素插入到已排序的流中时，我们可以只对新元素执行二进制搜索并在 logn 时间内插入它。但是我们需要将所有项目向右移动 1，这将导致 O(N)。
我仍然不确定这是否正确
我们会使用 Balanced BST，插入和搜索的最坏情况是 logN，或者我们可以只使用 HashMap，它理想地在 O(1) 中执行查找并在 O(1) 中执行插入(1).然而，当我们处理 1000 亿条记录时，我们对 HashMap 的最坏情况查找将是 O(N) 与链表实现。
对于这些问题，我仍然没有一个明确的答案。如果有人能提供更多见解，那就太好了！
谢谢！
要对大量数据进行排序，通常分两步进行：
- 缓冲数据，直到您收到一些（通常非常大的）数据项。然后对它们进行排序并将排序后的块写入磁盘。您继续执行此操作，直到收到所有数据并对其进行排序。
- 对所有块进行排序后，对排序的块进行 k 向合并以创建单个排序文件。
如果你有足够的能力，缓冲和排序可以并行完成。当接收到每个块时，您启动一个线程对其进行排序，同时主线程继续接收新块中的数据。当然，这不是无限可扩展的，因为对大缓冲区进行排序比接收要花费更长的时间。因此，您可能必须在收到每个块时将其写入磁盘，并有固定数量的后台线程对这些块进行排序。基本算法是一样的，不过...只是延迟了一点时间。
如果您可以使用多台机器进行搜索，您通常会将数据分散到多台机器上。所以如果你有 4 台机器，每台机器得到 1/4 的数据。当你想进行搜索时，你让每台机器搜索其数据集以查找匹配的记录，并将这些结果传送到某个中心位置，该位置排序并删除重复项。
现在，如果您想维护来自潜在无限流的排序数据结构（即能够在接收数据时随时进行搜索），那么您需要更动态的东西。一种简单的方法是拥有主要的排序结构，以及 "not yet sorted" 缓冲区。因此，例如，假设您已经收到了 10 亿个项目，您已经对其进行了排序和存储，并且您的缓冲区大小为 100 万个项目。接收到数据后，您会在内存中存储一百万个项目，然后再将它们与主数据结构合并。
当你收到一个搜索查询时，你会搜索主要结构，如果你使用二进制搜索，这将是 O(log N)，然后你依次搜索你的接收缓冲区。当然顺序搜索有点慢，因为它是顺序的，但所有数据都在内存中，因此您不必支付 I/O.
的成本
当您的缓冲区填满时，您使用高效算法将其与存储的结构合并。
这是基本思想。有很多方法可以通过多级合并或使用比二叉树或类似的更好的数据结构来提高效率。
我一直在为面试练习一些算法问题，并偶然发现了各种问题，这些问题涉及对来自无限流的数据进行排序，并设计一个数据结构来搜索数十亿条记录
Describe how to sort integers read one at a time from an infinite stream
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.
以上是我的想法，如有错误或有更好的解决方法请指正
对于从无限流中一次读取一个整数进行排序，我们可以使用插入排序吗？插入排序的最坏情况是 O(n2) 对未排序的列表进行排序，但在这种情况下 运行 时间可以降低到 O(logn)。当要将新元素插入到已排序的流中时，我们可以只对新元素执行二进制搜索并在 logn 时间内插入它。但是我们需要将所有项目向右移动 1，这将导致 O(N)。 我仍然不确定这是否正确
我们会使用 Balanced BST，插入和搜索的最坏情况是 logN，或者我们可以只使用 HashMap，它理想地在 O(1) 中执行查找并在 O(1) 中执行插入(1).然而，当我们处理 1000 亿条记录时，我们对 HashMap 的最坏情况查找将是 O(N) 与链表实现。
对于这些问题，我仍然没有一个明确的答案。如果有人能提供更多见解，那就太好了！
谢谢！
要对大量数据进行排序，通常分两步进行：
- 缓冲数据，直到您收到一些（通常非常大的）数据项。然后对它们进行排序并将排序后的块写入磁盘。您继续执行此操作，直到收到所有数据并对其进行排序。
- 对所有块进行排序后，对排序的块进行 k 向合并以创建单个排序文件。
如果你有足够的能力，缓冲和排序可以并行完成。当接收到每个块时，您启动一个线程对其进行排序，同时主线程继续接收新块中的数据。当然，这不是无限可扩展的，因为对大缓冲区进行排序比接收要花费更长的时间。因此，您可能必须在收到每个块时将其写入磁盘，并有固定数量的后台线程对这些块进行排序。基本算法是一样的，不过...只是延迟了一点时间。
如果您可以使用多台机器进行搜索，您通常会将数据分散到多台机器上。所以如果你有 4 台机器，每台机器得到 1/4 的数据。当你想进行搜索时，你让每台机器搜索其数据集以查找匹配的记录，并将这些结果传送到某个中心位置，该位置排序并删除重复项。
现在，如果您想维护来自潜在无限流的排序数据结构（即能够在接收数据时随时进行搜索），那么您需要更动态的东西。一种简单的方法是拥有主要的排序结构，以及 "not yet sorted" 缓冲区。因此，例如，假设您已经收到了 10 亿个项目，您已经对其进行了排序和存储，并且您的缓冲区大小为 100 万个项目。接收到数据后，您会在内存中存储一百万个项目，然后再将它们与主数据结构合并。
当你收到一个搜索查询时，你会搜索主要结构，如果你使用二进制搜索，这将是 O(log N)，然后你依次搜索你的接收缓冲区。当然顺序搜索有点慢，因为它是顺序的，但所有数据都在内存中，因此您不必支付 I/O.
的成本当您的缓冲区填满时，您使用高效算法将其与存储的结构合并。
这是基本思想。有很多方法可以通过多级合并或使用比二叉树或类似的更好的数据结构来提高效率。