Ищу алгоритм удаления
Назад
Вспомнил проблемку которую давно решил, но совершенно не помню как.
Что имеем?
Некий файл, хранилище данных, данные туда записываются поблочно, типа 100, 200, 500 байт. Этих блоков может быть дофига, миллионы и больше.
Каждый блок имеет свой адрес (смещение от начала файла). Этот адрес может записываться в другие блоки, то бишь блоки желательно не перемещать.
С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.
Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.
Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.
Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.