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

Question

Я пытаюсь сохранить данные в дереве разбиения двоичного пространства в реляционной базе данных. Сложность этой структуры данных состоит в том, что она имеет два разных типа узлов. Первый тип, который мы называем узлом данных, просто содержит определенное количество элементов. Мы определяем максимальное количество предметов, которое можно удерживать как 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. Разделение узла требует снятия флажка листа, вставки двух новых узлов листа и обновления всех элементов данных в узле, чтобы они указывали на соответствующий дочерний узел, изменяя их значения листьев.

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