C / C ++: как хранить данные в файле в дереве B

Question

Мне кажется, что один способ хранения данных в B-дереве в виде файла может быть эффективно реализован с помощью C с использованием двоичного файла с последовательностью (массивом) структур, где каждая структура представляет узел. Таким образом, можно связать отдельные узлы с подходом, который будет аналогичен созданию связанных списков с использованием массивов. Но тогда проблема, которая поддерживает, будет удалением узла, так как стирание всего нескольких байтов в середине в огромном файле невозможно.

Одним из способов удаления может быть отслеживание «пустых» узлов до достижения порогового значения, а затем создание другого файла, который будет отбрасывать пустые узлы. Но это утомительно.

Есть ли лучший подход с точки зрения простоты / эффективности для удаления или даже представления B-дерева в файле?

ТИА, -Sviiya

Answer 1

Для реализации B-деревьев в файле вы можете использовать смещение файла вместо указателей. Кроме того, вы можете реализовать «диспетчер файловой памяти», чтобы вы могли повторно использовать удаленные элементы в файле.

Чтобы полностью восстановить удаленные блоки в файле B-Tree, вам придется воссоздать B-Tree в новом файле. Также помните, что большинство ОС не имеют методов для усечения файлов. Переносимый метод усечения файла - написать новый файл и уничтожить старый.

Другим предложением является разбиение файла на раздел B-Tree и раздел данных (элемент). Раздел B-Tree будет содержать страницы. Листовые страницы будут содержать смещения к элементам данных. Раздел данных будет разделом в файле, содержащем элементы данных. В конечном итоге вы можете создать более одного раздела и разделы могут чередоваться.

Я провел много времени, играя с файловым B-Tree, пока не сдался и решил позволить программе базы данных (или серверу) обрабатывать данные для меня.

Answer 2

Я сделал очень быстрый поиск и выкопал это: http://people.csail.mit.edu/jaffer/WB Источник C: http://cvs.savannah.gnu.org/viewvc/wb/wb/c/ - похоже, он предлагает базы данных в стиле B-дерева на основе дисков, хотя взглянул на "delete".c "казалось, что если вы удаляете узел, все, что находится внизу, будет удалено - если это правильное поведение, то это звучит как что-то, что может помочь?

Также - B-деревья часто используются вфайловые системы - не могли бы вы взглянуть на некоторый код файловой системы?

Я склоняюсь к файловой системе - если у вас B-дерево фиксированного размера, всякий раз, когда вы «удаляете» узел, а не пытаетесь удалить ссылку, просто установите любое значениеничего не значит в вашем коде.Затем запустите поток очистки, который проверяет, есть ли у кого-нибудь файл, открытый для чтения, и все ли в тишине блокирует файл и приводит в порядок.

Answer 3

Вы также можете использовать Berkley DB. Он хорошо работает с программами на C и реализует дерево B +.