小编Arp*_*pit的帖子

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

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

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

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