搜索大量排序的数据块

Question

我在磁盘中有一个巨大的设置数据记录,它按照某些键排序.数据一次被读入一个块(数千条记录).我必须搜索并显示与键匹配的所有记录.我在想一些基于二进制搜索的算法,但我在这里有一些限制.

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

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

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

Answer 1

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

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