сохранение Btrees в файл на диске и чтение его

Question

Я хочу сохранить Btree (не обязательно двоичное) в файле на диске. а затем прочитать его в память. некоторый обход уровня порядка может быть хорошим способом для двоичного Btree. но если это не бинарный. Я создаю Btree от листового узла до корневого узла в памяти. Я считаю, что мне нужно определить некоторые структуры в файле диска и вывести узлы дерева. использовать какой-то дополнительный тег для идентификации узла в файле? как обход может быть ключевой проблемой здесь. Я не могу найти хороший способ сохранить узлы и указатели. и затем прочитайте это. Построить дерево в памяти. какие-нибудь хорошие идеи? Большое спасибо.

Answer 1

Обычный метод для B-Trees состоит в том, чтобы гарантировать, что размер узла равен размеру блока диска, и отобразить файл на диске. Вы не указываете, на каком языке программирования вы работаете, так что это может быть так же просто, как приведение в C или что-то более сложное, например, создание объектов типа flyweight для упаковки java.nio.IntBuffer. В любом случае, большое преимущество B-дерева заключается в том, что вам не нужно загружать все сразу, но вы можете довольно быстро его обойти.

Answer 2

Если вы действительно хотите сделать что-то подобное, вы можете просто назначить каждому узлу идентификатор и сохранить узлы в этом формате:

[значение id-узла left-node-id right-node-id]

, а затем посетите дерево с поиском в ширину.

Когда вы хотите восстановить дерево, создайте идентификатор карты-> узел и затем прочитайте назад файл: так, когда вы читаете запись, создаете узел, регистрируете его на карте и назначаете левый и правый узел, извлекающий узлы из карты.

Answer 3

Возможно, вы захотите проверить Буферы протокола . Они компактны, двоичны, расширяемы, легко читаются и пишутся, доступны на C ++, Java и Python (а также в сторонних реализациях на других языках).

Вы можете определить сообщение буфера протокола для узла BTree с смещениями файлов для дочерних узлов и просто сериализовать его на диск очевидным образом.

Answer 4

Для каждого узла определите некоторую структуру данных, которая будет хранить для вас ту же информацию, которую имеет узел, и добавьте в эту структуру дополнительное поле, которое пометит для вас смещение в файле для следующего сына. И сделайте верхнее поле этой структуры реальным размером, так как вы не знаете, какое дерево вы сейчас смотрите. Теперь, перепрыгивая через файл, вы сможете восстановить свое дерево. Я уверен, что мое решение не является окончательным, но я надеюсь, что это может быть хорошей звездой для вас.