Как сохранить дерево разбиения двоичного пространства в реляционной базе данных?

Question

Я пытаюсь сохранить данные в binary space partitioning tree в реляционной базе данных. Сложная часть этой структуры данных состоит из двух разных типов узлов. Первый тип, который мы называем узлом данных, просто содержит определенное количество элементов. Мы определяем максимальное количество элементов, которые можно удерживать как t. Второй тип, который мы называем узлом-контейнером, содержит два других дочерних узла. Когда элемент добавляется к дереву, узлы рекурсируются до тех пор, пока не будет найден узел данных. Если количество элементов в узле данных меньше t, то элемент вставляется в узел данных. В противном случае узел данных разбивается на два других узла данных и заменяется одним из узлов контейнера. Когда элемент удаляется, должен выполняться обратный процесс.

Я немного потерян. Как я должен выполнять эту работу с использованием реляционной модели?

Answer 1

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

Узел таблица будет иметь такие столбцы: id primary key, parentid references node, leaf boolean и, кроме того, некоторые столбцы для описания пространственных буферов узла и того, как он будет/был разделен. (Я не знаю, работаете ли вы в 2D или 3D, поэтому я не задавал детали геометрии.)

Таблица данных имела бы id primary key, leafid references node и любые данные.

Вы можете перемещаться по дереву вниз, выдавая SELECT * FROM node WHERE parentid = ? запросов на каждом уровне и проверяя, с какого ребенка спускаться. Добавление элемента данных к листу - это просто INSERT. Разделение узла требует сброса флажка листа, вставки двух новых листовых узлов и обновления всех элементов данных в узле, чтобы указать на соответствующий дочерний узел, изменив их значения leafid.

Обратите внимание, что командировки SQL могут быть дорогими, поэтому, если вы хотите использовать это для реального приложения, подумайте об использовании относительно большого t в БД, создающем более мелкое дерево в памяти интересующих вас листьев после того, как у вас есть элементы данных.