Лучшая структура базы данных для реализации дерева графов

Question

Я пытаюсь создать базу данных с пирамидальными отношениями. Например, это мои данные:

Ну, как я могу и хранить эти цифры и держать их отношения?

---

В настоящее время я делаю это так:

// myTree 
+----+------+--------+ 
| id | node | parent | 
+----+------+--------+ 
| 1 | 8 | Null | 
| 2 | 10 | 8  | 
| 3 | 3 | 8  | 
| 4 | 14 | 10  | 
| 5 | 6 | 3  | 
| 7 | 1 | 3  | 
| 8 | 13 | 14  | 
| 9 | 7 | 6  | 
| 10 | 4 | 6  | 
+----+------+--------+ 

Но в этом случае я могу выбрать только один уровень графа по одному запросу. Хотя мне нужно выбрать целую ветку для узла. Foe нелогич-:

$node = 14; 

Ожидаемый результат:

[8, 10, 14, 13] 

Примечание: Узлов являются уникальными.

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

Answer 1

Если вы ДОЛЖНЫ сделать это в MySQL, @philipxy предоставил вам хорошую ссылку, но вы должны знать, что MySQL - это плохой выбор для иерархических/древовидных данных.
Другие СУБД, такие как Oracle, SQL Server и PostgreSQL, несколько лучше подходят для подхода списка смежности, поскольку они, по крайней мере, поддерживают итеративные («рекурсивные») запросы.
Для хорошей посадки, я предлагаю вам взглянуть на neo4j

Answer 2

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

Answer 3

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

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

У меня был идеальный прецедент: образовательные стандарты всех штатов, округ Колумбия и территории США. Образовательные стандарты меняются не чаще одного раза в год, и большинство государств меняют их гораздо реже, чем это. Во всяком случае, как только школьные годы начинаются, стандарты, действующие в данный момент, остаются в силе в течение продолжительности. Поэтому, когда списки создаются в начале года, они не меняются до начала следующего года.

Представьте, что вы можете запрашивать информацию, содержащуюся только в поддереве любого узла дерева. Абсолютная сила!

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

Под «изменениями» обратите внимание, что я ссылаюсь на изменения, которые управляют структурой дерева: вставка нового узла, перемещение узла из одного места в другое, удаление узла и т. Д. Обновления содержимого узла являются не проблема.

Также обратите внимание, что у меня было несколько недель, чтобы поиграть, чтобы ознакомиться со структурой. Вы можете написать некоторые радикальные запросы, но потребуется некоторое время, чтобы узнать об этом в системе.

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