Структура данных и алгоритм для представления / выделения свободного места в файле

У меня есть файл с «дырами» в нем и хочу заполнить их данными; мне также нужно иметь возможность освободить «используемое» пространство и освободить свободное пространство.

Я думал об использовании двумерной карты, которая отображает смещение и длину . Однако, Я не уверен, что это лучший подход, если в файле действительно крошечные пробелы. Растровое изображение будет работать, но я не знаю, как его можно легко переключить динамически для определенных областей пространства. Может быть, лучше использовать какое-то дерево счисления?

Что бы это ни стоило, я хорошо разбираюсь в дизайне современных файловых систем (ZFS, HFS +, NTFS, XFS, ext ...), и я нахожу их решения ужасно неадекватно.

Моя цель - иметь довольно хорошую экономию места (отсюда и беспокойство по поводу небольших фрагментов). Если бы меня это не волновало, я бы просто выбрал два растянутых дерева ... Одно отсортировано по смещению, а другое отсортировано по длине с разрывом связей по смещению. Обратите внимание, что это дает вам амортизированный журнал (n) для всех операций с рабочим установленным временем журнала (m) ... Чертовски хорошо ... Но, как упоминалось ранее, не решает проблем, связанных с высокой фрагментацией.