Допаковалось.
Исходный файл был пожат, весил 344 Мб
Он же пожатый RAR5 с максимальным сжатием 367 Мб
Он же отсортированный и пожатый RAR5 с максимальным сжатием 171 Мб

Пошел изучать чудесный bzip2, который жмет лучше RAR`а

PS слать обновления будет намного компактней.

__Avenger__1. Я его сортирую, потом оставляю только паспорта РФ. Другие не интересуют.
Формат сейчас такой: карта по сериям 10000 Int = 80000 байтов + 96 000 000 записей по 4 байта. Итоговый файл занимает 386 мегабайтов. В архиве - WinRar 4.2 - 35 МБ. 7-zip жмет до 50 МБ.

2. Поиск по файлу конкретного паспорта осуществляю методом половинного деления. По серии определяю позиции начала и окончания блока данных в бинарном файле

3. 35 МБ для удаленных офисов - очень большой трафик. Как правило DialUp или GPRS. Поэтому написана утилита которая находит разности между двумя бинарными файлами. На удаленные офисы приходят эти разности. Разность за год по подсчетам должна быть примерно 6 байтов на запись * 40 000 изменений в день * 250 дней = 57 МБ. Сколько это в архиве - не знаю.
ИМХУ надо разделить задачи: на передачу и использование. Т.е. один формат для передачи, второй для поиска. При получении делать конвертацию из первого во второй.

Как понимаю проблемы именно с передачей, как вариант: сделать синхронизацию по типу rsync, т.е. обновление только измененных частей файла.
Только надо исключить операцию удаления, например использовать замену на невалидный номер. Тем более что для данной задачи удаление крайне редкая операция. Тогда все операции сведутся к добавлению и изменению.
Дальше протокол обмена примерно такой:
1. Клиент разбивает свою копию на блоки, посылает хэш каждого и общий размер. Например если разбить на 64 блока и по каждому посчитать MD5, то запрос будет 16*64 = 1024 байта + немного доп.инфы.
2. Сервер в ответ посылает все что добавилось ( > размера копии клиента), проверяет хэши, если у какого-то блока не совпало, сообщает номер блока клиенту.
3. Клиент дописывает хвост, по измененному блоку разбивает его еще на 64 и отправляет хэши серверу.
4. Сервер проверяет и отправляет клиенту блоки по которым хэш не совпал.
и т.д.
Можно просто с rsync разобраться и его использовать. Главное чтобы удалений не было. Т.к. удаление редкость, то в 99% случаев все сведется к отправке добавившегося.

Полную передачу тоже можно оптимизировать. Тут можно утрамбовать все номера в 20 бит, т.е. 3 байта, если использовать такой формат:

т.е. если значение >= 1000000 это следующая серия. Максимум будет 1009999, что меньше 1048576 (2^20).
Так можно использовать три байта на один паспорт, если со сдвигами пошаманить то 5 байт на две записи.

Второй вариант вместо абсолютного номера хранить смещение (дельту от предыдущего номера), как mayton предложил 18742953
Примерно так:


Тут надо реальное распределение смотреть, думаю можно будет подстроится чтобы уложиться в 1-2 байта на номер.

Можно что-то типа репликации использовать:
На сервере все хранить в БД и добавить поле TIMESTAMP или просто счетчик. При каждом добавлении в это поле писать значение счетчика, счетчик увеличивать.
Синхронизация примерно так:
1. Клиент присылает значение TIMESTAMP своей копии
2. Сервер обратно отправляет все записи с большим TIMESTAMP и текущее максимальное значение TIMESTAMP. Дополнительно хэши каждой серии.
3. Клиент добавляет к себе новые данные, запоминает значение TIMESTAMP, проверяет хэши, если по какой-то серии не совпало - запрашивает полное обновление этой серии.

Так удаление можно использовать и хранить уже отсортированное.

PS Серий на сегодня порядка 90*16 = 1440, при 16 байт на хэш будет ~23 Кб

Думаю в качестве хэша можно вместо MD5 можно что-нибудь покороче взять, например CRC32

По удаленным можно отдельную таблицу завести, при удалении переносить туда с установкой TIMESTAMP, и при отправке обновления клиенту из этой таблицы тоже слать список на удаление.