Ищу алгоритм удаления
это классическая задача аллокаторов памяти. В каждый блок в начале записываете структурку, которая связана соседями линейным двухсвязанным списком (чтобы детектировать, что соседний блок удалили и надо объединить свободное пространство), а в каждый удаленный - дополнительно пишем структуру динамически балансируемого дерева, в котором все отсортировано по размеру этого свободного пространства.
При запросе на новый блок в за логарифмическое время находите первый блок по размеру, который удовлетворяет (или если нет, то пишем в конец).
При удалении пользуемся линейным списком чтобы понять соседа и, если сосед пустой, объединяем (еще два реквеста в бинарное дерево).
Если программа имеет информация о блоках и при удалении может сказать еще размер блока, то двухсвязанный список можно не хранить, чтобы память сэкономить, но тогда надо иметь еще одно бинарное дерево, в котором сортировка уже идет по местоположению в памяти.
Так устроенный аллокатор памяти реально ускоряет алгоритмы, в которых часто надо аллоцировать-деаллоцировать, и последний раз я проверял в линуксе и винде несколько лет назад, ускорение было разы по сравнению со штатными системными средствами.