а вот насчёт необходимости перезаписи всего файла при смене одного байта - это как-то странно звучит
Почему странно ? Он ведь сжатый ! При добавлении информации в сжатый файл вполне логичен пересмотр всей структуры сжатого файла. Попробуй добавить файл в любой существуй архив типа зип,рар и тп. - принципы те же самые.