C/C++: Как хранить данные в файле в дереве B
Кажется мне, что один способ хранить данные в B-дереве как файл может быть сделан эффективно с C, использующим двоичный файл с последовательностью (массив) структур с каждой структурой, представляющей узел. Можно таким образом соединить отдельные узлы с подходом, который будет аналогичным созданию связанных списков с помощью массивов. Но затем проблемой, которая поддерживает, было бы удаление узла, поскольку стирающий только несколько байтов в середине в огромном файле не возможно.
Один способ удалить мог состоять в том, чтобы отслеживать 'пустые' узлы, пока пороговое сокращение не достигнуто, и затем сделайте другой файл, который отбросит пустые узлы. Но это утомительно.
Существует ли лучший подход с точки зрения простоты/эффективности для удаления или даже представления B-дерева в файле?
TIA,-Sviiya
3 ответа
Я сделал очень быстрый поиск и выкопал это: http://people.csail.mit.edu/jaffer/wb C Источник: http: //cvs.savannah.gnu.org/viewvc/wb/wb/c/ - Кажется, предлагает базы данных B-деревьев на основе дисков - хотя выглядят взглянуть на «Delete.c», казалось, что Вы удалите узел все, от него было бы извлечено - если это правильное поведение, то это звучит как то, что может помочь?
Также - B-деревья часто используются в файловых системах - не могли бы вы взглянуть на некоторую файловую систему код?
Моя собственная наклона - это файловая система - если у вас есть B-дерево фиксированного размера, всякий раз, когда вы «удалите» узел, а не пытаясь удалить ссылку, просто установите значение для того, чтобы ничего не значит в ваш код. Затем проготайте поток очистки, которая проверяет, имеет ли у кого-то файл открытый для чтения, и если все тихие блокируют файл и вкладки.
Для внедрения B-деревьев в файле вы можете использовать смещение файла вместо указателей. Кроме того, вы можете реализовать «Диспетчер памяти файла», чтобы вы могли повторно использовать удаленные элементы в файле.
Чтобы полностью восстановить удаленные блоки в файле B-дерева, вам придется воссоздать B-дерево в новом файле. Также помните, что большинство ОС нет методов для усеченных файлов. Портативный метод для усечения файла - написать новый файл и уничтожить старый.
Другое предложение состоит в том, чтобы разделить файл в разделе B-деревьев и раздел данных (элемент). Раздел B-дерева будет содержать страницы. Страницы листьев будут содержать смещения к элементам данных. Раздел данных будет разделом в файле, содержащем элементы данных. Вы можете в конечном итоге создавать более одного из каждого раздела, и разделы могут быть переплетены.
Я потратил много времени, играя с b-деревом на основе файлов, пока я не сдался и решил позволить программе базы данных (или Server) обрабатывать данные для меня.
Вы также можете использовать Berkley DB. Она хорошо работает с программами на Си и реализует дерево B+.