Podrías tener un índice. Te propongo un formato, que te permite tener bloques de tamaños indefinidos:
<numero de bloques (INT 4 bytes) />
<tamaño del bloque 1(INT 4 bytes) />
<posicion en el archivo del bloque 1 (en bytes) (INT 4 bytes) />
<tamaño del bloque N (INT 4 bytes) />
<posicion en el archivo del bloque N (INT 4 bytes) />
<...>
<bloque 1 />
<bloque n />
<...>
Si los bloques son de, por ejemplo, 256 bytes, puedes hacer:
<bloque 1>
<bytes del bloque (CHAR 1 byte) />
<datos>
</bloque 1>
<bloque 2>
...
</bloque 2>
Si no te gustan esos formatos, haz otro que esté acorde a lo que buscas.