c++ - 搜索巨大的排序数据 block

Question

我在磁盘中有大量数据记录，这些数据记录是根据某些键按排序顺序排列的。 一次将数据一个 block (数千条记录)读入内存。 我必须搜索并显示与某个键匹配的所有记录。 我在考虑一些基于二进制搜索的算法，但我在这里有一些限制。

1. 只能从 block 的开头在 block 内按顺序查找记录。
2. 具有相同键的记录可以跨越多个 block (如图所示 - 8 个跨度)。在二进制搜索中，如果我正在加载中间 block 并且如果第一条记录匹配，那么我必须 扫描匹配 block 之前的 block 。

谁能帮我设计一个可以在 C++ 中运行的有效策略。使用线性搜索方法是否有效。

+---+
| 1 | Block1
| 3 |
| 3 |
| 4 |
+---+
| 4 | Block2
| 6 |
| 7 |
| 8 |
+---+
| 8 | Block3
| 8 |
| 8 |
| 8 |
+---+
| 8 | Block4
| 14|
| 15|
| 16|
+---+

Answer 1

您可以构建一个由每个 block 中的第一个条目组成的辅助数组，然后对该数组运行二进制搜索。数组的索引应直接与 block 索引对应，使其成为 O(1) 查找以获取相应的 block 。

它将最坏的情况从 O(n) 减少到 O(logn)，并且仍然相对简单。