Удалить байты в середине файла без перемещения конца?

Question

Например, если у меня есть много записей данных, хранящихся в файле, каждый с разными размерами, и у меня есть 1000 записей, что делает файл размером около 100 МБ, если я затем хочу удалить запись в середине файла, которыйимеет размер 50 КБ, как я могу удалить эти пустые 50 КБ байтов в файле, не перемещая все конечные байты, чтобы заполнить его?

Я использую такие функции winapi для управления файлами:

CreateFile, WriteFile, ReadFile и SetFilePointerEx

Answer 1

Если вы действительно хотите это сделать, установите флаг в вашей записи.Если вы хотите удалить запись из вашего файла, просто аннулируйте этот флаг ( логическое удаление ) без его физического удаления.В следующий раз, когда вы добавите запись, просто просмотрите файл, найдите первую недействительную запись и перезапишите ее.Если все проверено, добавьте его до конца.O(1) требуется время для удаления записи и O(n) для добавления новой записи, при условии, что чтение / запись одной записи с / на диск является основной операцией.

Вы даже можете оптимизировать ее дальше.В начале файла сохраните битовую карту (1 для недействительных).Например, 0001000... означает, что четвертая запись в вашем файле признана недействительной.Когда вы добавляете запись, ищите первый 1 в битовой карте и используйте Случайный файловый ввод / вывод (в отличие от последовательный файловый ввод / вывод ) чтобы перенаправить указатель файла непосредственно на эту запись для перезаписи.Добавление таким способом занимает всего O(1) раз.

О, я заметил ваш комментарий.Если вы хотите сделать это эффективно с физически удаленной записью, простой способ состоит в том, чтобы поменять запись на удаление с самой последней в вашем файле и удалить последнюю, при условии, что ваши записи не отсортированы,Время также хорошее, что составляет O(1) как для добавления, так и для удаления.

Редактировать: Как упоминал Джо, this requires that all of your entries have the same size.Вы можете реализовать один с переменной длиной записей, но это будет сложнее, чем обсуждаемый здесь.

Answer 2

Вы можете просто пометить неиспользуемое пространство, и через некоторое время, когда внутренняя фрагментация превысит определенное соотношение, вы сможете запустить подпрограмму, которая сожмет файл.С этой схемой удаления были бы быстрыми, но некоторая периодическая реорганизация необходима.Если у вас есть отдельная схема обработки файлов, вы можете разделить файл на несколько частей, а затем отслеживать свободные фрагменты, а при удалении пометить блок как неиспользуемый и отслеживать его, а затем в случае вставки повторно использовать,Эта схема будет зависеть от типа записей в вашем файле, записей фиксированной или переменной длины.

Answer 3

Пусть A = начало файла, B = начало удаляемого блока, C = конец удаляемого блока

CreateFile с флагом FILE_FLAG_RANDOM_ACCESS

SetFilePointerEx для позиционированияC, чтение в EOF в буфер (это может быть большой буфер, учитывая размер вашего файла. Будьте осторожны с гигантскими записями, потому что теперь любая операция File IO должна выделять виртуальную память такого размера, чтобы выполнить любую простую операцию, такую ​​как перемещение).

Копировать буфер в позицию B в файле

Теперь должен быть в позиции B + sizeof (блок C).Вызовите SetEndOfFile, чтобы обрезать файл в этой позиции, затем закройте.

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