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

Ответ 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

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

Ответ 2

Я добавил в закладки этот slideshare о 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

Ответ 3

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

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

Посмотрите на таблицу примеров node:

+---------+-------+
| 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 |
+---------+-------+

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

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

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

Ответ 4

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

Из docs:

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)

Ответ 5

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

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

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

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

Ответ 6

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

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

Ответ 7

Лучший способ, я думаю, действительно состоит в том, чтобы дать каждому node id и parent_id, где родительский id является идентификатором родительского node. Это имеет несколько преимуществ

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

Ответ 8

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

В этом случае, какой лучший способ?

Винсент

Ответ 9

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

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

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

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

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

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

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

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