Поиск огромных отсортированных блоков данных

У меня есть огромный набор записей данных на диске, которые упорядочены в отсортированном порядке на основе некоторого ключа (ключей). Данные считываются в память блоком (тысячи записей) за раз. Мне нужно найти и отобразить все записи, соответствующие ключу. Я думал о каком-то алгоритме, основанном на бинарном поиске, но у меня здесь есть некоторые ограничения.

1. Записи можно искать только последовательно в пределах блока с начала блока.
2. Записи с одним и тем же ключом могут охватывать несколько блоков ( как показано на рисунке - 8 пролетов). В двоичном поиске, если я загружаю средний блок и если первая запись совпадает, то мне нужно сканировать блоки, предшествующие совпавшему блоку.

Может ли кто-нибудь помочь мне разработать эффективную стратегию, которая могла бы работать на C ++. Будет ли эффективен метод линейного поиска.

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