Как представить дерево данных в SQL?

Question

Я пишу древовидную структуру данных, которая объединена из Tree и TreeNode. Дерево будет содержать корень и действия верхнего уровня на данных. Я использую библиотеку пользовательского интерфейса, чтобы представить дерево в форме окна, где я могу связать дерево с TreeView.

Мне нужно сохранить это дерево и узлы в БД. Что будет лучшим способом сохранить дерево и получить следующие возможности:

1. Интуитивно понятная реализация.
2. Легкая привязка. Будет легко перейти от дерева к структуре БД и обратно (если есть)

У меня было 2 идеи. Первый заключается в сериализации данных в одну строку в таблице. Второе - сохранить в таблицах, но затем при переходе к объектам данных я потеряю состояния строк в таблице на измененных узлах.

Есть идеи?

Answer 1

Самая простая реализация - список смежностей структура:

id  parent_id  data

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

Другая модель вложенных наборов :

id lft rgt data

, где lft и rgt - произвольные значения, которые определяют иерархию (lft, rgt любого дочернего элемента должно быть в пределах lft, rgt) любого родителя

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

Однако в MySQL это можно улучшить с помощью SPATIAL abitilies.

Смотрите эти статьи в моем блоге:

• Список смежных и вложенных множеств: PostgreSQL
• Список смежных и вложенных множеств: SQL Server
• Список смежных и вложенных множеств: Oracle
• Список смежных и вложенных множеств: MySQL

для более подробных объяснений.

Answer 2

Я поставил в закладки этот слайдшоу об SQL-Antipatterns, в котором обсуждаются несколько альтернатив: http://www.slideshare.net/billkarwin/sql-antipatterns-strike-back?src=embed

Рекомендация оттуда заключается в использовании таблицы закрытия (это объясняется на слайдах).

Вот резюме (слайд 77):

                  | Query Child | Query Subtree | Modify Tree | Ref. Integrity
Adjacency List    |    Easy     |     Hard      |    Easy     |      Yes
Path Enumeration  |    Easy     |     Easy      |    Hard     |      No
Nested Sets       |    Hard     |     Easy      |    Hard     |      No
Closure Table     |    Easy     |     Easy      |    Easy     |      Yes

Answer 3

Я удивлен, что никто не упомянул решение материализованный путь , которое, вероятно, является самым быстрым способом работы с деревьями в стандартном SQL.

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

Взгляните на таблицу примеров узел :

+---------+-------+
| node_id | path  |
+---------+-------+
| 0       |       |
| 1       | 1     |
| 2       | 2     |
| 3       | 3     |
| 4       | 1.4   |
| 5       | 2.5   |
| 6       | 2.6   |
| 7       | 2.6.7 |
| 8       | 2.6.8 |
| 9       | 2.6.9 |
+---------+-------+

Чтобы получить дочерние элементы узла x , вы можете написать следующий запрос:

SELECT * FROM node WHERE path LIKE CONCAT((SELECT path FROM node WHERE node_id = x), '.%')

Имейте в виду, что столбец path должен быть проиндексирован, чтобы выполнить быстро с предложением LIKE .

Answer 4

Если вы используете PostgreSQL, вы можете использовать ltree, пакет в расширении contrib (поставляется по умолчанию), который реализует древовидную структуру данных.

Из документов :

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING GIST (path);
CREATE INDEX path_idx ON test USING BTREE (path);

Вы можете делать запросы, такие как:

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)

Answer 5

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

Если вы хотите сохранить каждый элемент в виде строки, сначала прочитайте Управление иерархическими данными в MySQL (специфично для MySQL, но этот совет применим и для многих других баз данных).

Если вы когда-либо обращаетесь только к целому дереву, модель списка смежности затрудняет получение всех узлов в корне без использования рекурсивного запроса. Если вы добавите дополнительный столбец, который ссылается на заголовок, вы можете сделать SELECT * WHERE head_id = @id и получить все дерево одним нерекурсивным запросом, но он денормализует базу данных.

Некоторые базы данных имеют пользовательские расширения, упрощающие хранение и извлечение иерархических данных, например, Oracle имеет CONNECT BY .

Answer 6

Поскольку это лучший ответ на вопрос "sql trees" в поиске Google, я постараюсь обновить его с точки зрения сегодняшнего дня (декабрь 2018 года).

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

Начиная с версии 8 (опубликовано в апреле 2018 г.) MySQL поддерживает рекурсивные выражения общих таблиц (CTE) . MySQL немного опоздал на шоу, но это открывает новую опцию.

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

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

В блоге здесь приведены некоторые измерения (которые смещены и для postgres вместо MySQL), но, тем не менее, показывают, что списки смежности не должны быть медленными.

Итак, мой вывод сегодня:

• Простой список смежности может быть достаточно быстрым, если ядро ​​базы данных поддерживает рекурсию.
• Сделайте тест с вашими данными и вашим собственным движком.
• Не доверяйте устаревшим рекомендациям, указывающим на «лучший» метод.

Answer 7

Я думаю, что лучший способ - дать каждому узлу идентификатор и parent_id, где родительский идентификатор - это идентификатор родительского узла. Это имеет пару преимуществ

1. Когда вы хотите обновить узел, вам нужно только переписать данные этого узла.
2. Когда вы хотите сделать запрос только к определенному узлу, вы можете получить именно ту информацию, которая вам нужна, тем самым уменьшая затраты на соединение с базой данных
3. Многие языки программирования имеют функции для преобразования данных mysql в XML или json, что облегчит открытие приложения с помощью API.

Answer 8

Что-то вроде таблицы «узлов», где каждая строка узла содержит родительский идентификатор (в дополнение к обычным данным узла). Для root родитель является NULL.

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