Подтвердить что ты не робот

Как представить структуру дерева в db

Я начинаю проект, и я нахожусь на этапе проектирования: I.e., я еще не решил, на какой базе db я буду использовать. У меня будет код, который создает структуру типа "лес". То есть, многие деревья, где каждое дерево является стандартным: узлы и ребра. После того, как код создает эти деревья, я хочу сохранить их в db. (а затем в конце концов вытащить их)

Наивный подход к представлению данных в db является реляционным db с двумя таблицами: узлами и ребрами. То есть таблица узлов будет иметь данные node id, node и т.д. И таблица ребер будет отображением node id на node id.

Есть ли лучший подход? Или учитывая (ограниченные) предположения, которые я даю, это лучший подход? Как насчет того, добавим ли мы предположение, что деревья относительно малы - лучше ли сохранить все дерево как blob в db? Какой тип db следует использовать в этом случае? Прокомментируйте скорость/масштабируемость.

Спасибо

4b9b3361

Ответ 1

Я показал решение, подобное вашим узлам и красным таблицам, в ответе на вопрос StackOverflow: Каков наиболее эффективный/элегантный способ разобрать плоскую таблицу в дерево? Я называю это решение "Закрытие таблицы".

Я сделал презентацию о различных методах хранения и использования деревьев в SQL, Модели для иерархических данных с SQL и PHP. Я продемонстрировал, что с правильными индексами (в зависимости от запросов, которые вам нужно выполнить) дизайн Closure Table может иметь очень хорошую производительность даже при больших наборах ребер (около 500 Кб в моей демонстрации).

Я также рассмотрел дизайн в моей книге SQL Antipatterns: избегайте ошибок программирования баз данных.

Ответ 2

Обязательно используйте какое-то низкоуровневое кодирование для сущности, предназначенной для предотвращения циклирования. Объект может быть частью, темой, папкой и т.д.

С файлом Entity и Entity-Xref вы можете прокрутить одну из двух двух отношений между двумя файлами: родительское и дочернее.

Уровень - это уровень, который сущность найдена в дереве. Низкоуровневый код для объекта - это самый низкий уровень, который сущностей можно найти в любом дереве в любом месте. Убедитесь, что код низкого уровня объекта, который вы хотите создать, меньше или равен, чтобы предотвратить цикл. после добавления объекта в качестве дочернего объекта он станет как минимум на один уровень ниже.