Ищу алгоритм удаления
Вспомнил проблемку которую давно решил, но совершенно не помню как.
Что имеем?
Некий файл, хранилище данных, данные туда записываются поблочно, типа 100, 200, 500 байт. Этих блоков может быть дофига, миллионы и больше.
Каждый блок имеет свой адрес (смещение от начала файла). Этот адрес может записываться в другие блоки, то бишь блоки желательно не перемещать.
С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.
Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.
Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.
Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.
Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.
И что?
Раз вы решили управление файлами вынести на более высокий уровень прикладного кода, то и создавайте на этом уровне что-то вроде файловой таблицы. Только вместо файлов в ней будут ваши блоки.
А почему, собственно, пишете в один файл, вместо того, чтобы по файлу на блок?
это классическая задача аллокаторов памяти. В каждый блок в начале записываете структурку, которая связана соседями линейным двухсвязанным списком (чтобы детектировать, что соседний блок удалили и надо объединить свободное пространство), а в каждый удаленный - дополнительно пишем структуру динамически балансируемого дерева, в котором все отсортировано по размеру этого свободного пространства.
При запросе на новый блок в за логарифмическое время находите первый блок по размеру, который удовлетворяет (или если нет, то пишем в конец).
При удалении пользуемся линейным списком чтобы понять соседа и, если сосед пустой, объединяем (еще два реквеста в бинарное дерево).
Если программа имеет информация о блоках и при удалении может сказать еще размер блока, то двухсвязанный список можно не хранить, чтобы память сэкономить, но тогда надо иметь еще одно бинарное дерево, в котором сортировка уже идет по местоположению в памяти.
Так устроенный аллокатор памяти реально ускоряет алгоритмы, в которых часто надо аллоцировать-деаллоцировать, и последний раз я проверял в линуксе и винде несколько лет назад, ускорение было разы по сравнению со штатными системными средствами.
Стандартно - блоки помечаются - удаленные.
Ну пометил, а как искать? не лазить же по всему файлу.
проводится ужимание
каким образом? Позицию "занятых" блоков менять нельзя, разве что системные блоки, которые еще можно контролировать как то.
блобы вполне подходят
В базе? нет, никакой прослойки, быстродействие резко упадет думаю.
Вот как раз проблема перед глазами. Была отличная прога каталогизатор файлов с бинарным сохранением данных.
Сделали новую и решили пользовать SQLite. Пользоваться прогой невозможно стало и медленней и размеры сохранённых данных увеличились
а как искать?
-------
по индексу перестроенному после изменения
менять нельзя
------
Можно. Разумеется с коррекцией ссылок.
Можно подумать над чем-то похожим на FAT (FAT16,FAT32,FAT64)
быстродействие резко упадет думаю
-----
Не-а...
Пока ты добъешься такого же - последняя весна закончится
невозможно стало
-----
Кури доку на sqlite.Я об нем ничего не знаю
Что Я знаю на 100% - нормальный сервер БД с большим объемом данных работает быстрее самописок.
С единственным исключением - когда данные статичны и денормализованны - самописка будет быстрее. Но! Статичных данных у нас не бывает.
а как искать? ------- по индексу перестроенному после изменения
Так как раз в дополнительных данных и проблема, как их сделать динамическими?
Можно. Разумеется с коррекцией ссылок.
Ссылки менять не могу - это прерогатива пользователя.
Не-а...Пока ты добъешься такого же - последняя весна закончится
очень сомневаюсь
нормальный сервер БД с большим объемом данных работает быстрее самописок
многое зависит от данных и их организации
Ну так как проблема как раз в этом дереве. На каждый удаленный блок пишется дополнительная структура. Блок взяли а что делать со структурой?
проблемы-то нет. Каждая структура (или класс, если на С++) листка этого бинарного дерева сидит в блоке со свободной памятью - вы же ее удалить не можете, так как после нее есть блок с занятой памятью. Очевидно, если блок был в конце файла, то лучше его просто удалить и из бинарного дерева и из файла. А вот головка, или корень этого бинарного дерева - это несколько десятков байт, и их можно в оперативке сохранить.
Самописный код бинарного дерева
380 725 7945 bintree.c
83 191 1942 bintree.h
463 916 9887 итого
меньше 500 строк сишника, в современном С++ есть соответствующий класс, и не надо велосипед выдумывать. Предполагаю, что в других языках и бинарное дерево, и двухсвязанные списки тоже в стандартных библиотеках имеются. Весь код такого аллокатора:
380 725 7945 bintree.c
83 191 1942 bintree.h
112 216 2158 decmem.c
463 969 11349 dmem.c
93 267 3159 dmem.h
336 592 5963 memc.c
62 170 1358 memc.h
292 1127 7883 memf.f
303 639 6732 quemem.c
2124 4896 48489 итого
у меня в свое время получился слегка больше двух тысяч строк и в 90-х я это примерно за месяц запрограммировал и радовался. Как я говорю, сейчас все это решается стандартными средствами С++, поэтому код дарить не буду, но рассказать-объяснить постараюсь. Если хотите, или так будет проще, могу войсом, тогда в личке телефонами обменяться
надо будет.
и их можно в оперативке сохранить.
В том и дело, что нельзя.
Открыл прогу, добавил данных, ушел.
Открыл прогу удалил данные, ушел.
Открыл прогу, добавил данных, ушел.
и в 90-х я это
Там именно я и об этом. В каком - то журнале было описание процесса сохранения данных, мне так понравилось, что в следующем проекте это и использовал. Было просто и удобно.
Сейчас что подобное хочется, но детали забылись.
поэтому код дарить не буду
Да код и не нужен, спасибо. Главное идея, а уж реализовать дело вторичное.
Относительно телефона нет проблем, но эта не та проблема, на которую нужно еще тратить ваше время. Это если вам, что понадобится просто с кем то обсудить, то всегда пож.
Ну и Си с плюсами я уже давно не пользую. Только С#.
Стандартная и очень частая задача. Ну например ссылки в Яве, DNS (именя в IP адреса) и т.п.
Решается путем введения двух идентификаторв: физического представления блока (смещение) и его логического представления (ссылка на блок), а также отображения между ними. Используется только логические ссылки. Физическое представление только в реализации.
BlockRef // Логический идентификатор, напрмер, int BlockOffset // Физическое расположение например смещение в файле interface Storage BlockRef alloc(size int) delete(BlockRef) resize(new_size int) byte[] read(BlockRef) write(BlockRef, byte[]) class FileStorage implements Storage File file // Здесь все храним Map block_allocation<BlockRef, BlockOffset> // Фактически таблица размещения это главная структура (тоже интерфейс) gc() // Запускаем периодически для сборки мусора, уплотнения и пр. оптимизаций
Главное это как отображать логические ссылки в физическое расположение. В простейшем случае это map. Но в реальности думаю есть миллионы разных способов для разных применений. Как говорится "зависит от контекста". Ну например можно хранить во многих файлах или большие блоки отдельно от маленьких или реализовать очередь запросов в случае конкурентного доступа и т.п. Надо конечно заниматься подсчетом использования ссылок, но это все просто для простых применений, а для сложных можно постепенно улучшать, поскольку интерфейс определен.