Как представить древовидную структуру в БД

Question

Я начинаю проект, и я нахожусь в стадии проектирования: то есть, я еще не определился с тем, какую среду БД я собираюсь использовать. У меня будет код, который создает структуру, похожую на «лес». То есть много деревьев, где каждое дерево является стандартным: узлы и ребра. После того, как код создает эти деревья, я хочу сохранить их в БД. (а потом их вытащить)

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

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

Спасибо

Answer 1

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

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

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

Answer 2

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

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

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