Какие есть варианты хранения иерархических данных в реляционной базе данных?

Question

Хорошие обзоры

Вообще говоря, вы принимаете решение между временем быстрого чтения (например, вложенным множеством) или временем быстрой записи (списком смежности). Обычно вы получаете комбинацию из приведенных ниже вариантов, которые лучше всего соответствуют вашим потребностям. Следующее обеспечивает некоторое углубленное чтение:

• Еще одно сравнение вложенных интервалов и списка смежности: лучшее сравнение списка смежности, материализованного пути, вложенного набора и вложенного интервала, которое я нашел.
• Модели для иерархических данных: слайды с хорошими объяснениями компромиссов и примера использования
• Представление иерархий в MySQL: очень хороший обзор Nested Set, в частности
• Иерархические данные в РСУБД: наиболее полный и хорошо организованный набор ссылок, которые я когда-либо видел, но не так много для объяснения

Опции

Я знаю об общих чертах:

1. Список смежности:
   • Столбцы: ID, ParentID
   • Легко реализовать.
   • Дешевый узел перемещается, вставляется и удаляется.
   • Дорого, чтобы найти уровень, происхождение и потомков, путь
   • Избегайте N+1 с помощью общих табличных выражений в базах данных, которые их поддерживают
2. Вложенный набор (он же модифицированный обход дерева предзаказа)
   • Столбцы: слева, справа
   • Дешевое происхождение, потомки
   • Очень дорого O(n/2) перемещает, вставляет, удаляет из-за изменчивой кодировки
3. Таблица Мостов (также известные как Закрытие таблицы / триггеры)
   • Использует отдельную таблицу соединений с: предком, потомком, глубиной (необязательно)
   • Дешевое происхождение и потомки
   • Пишет расходы O(log n) (размер поддерева) для вставки, обновления, удаления
   • Нормализованное кодирование: хорошо для статистики СУБД и планировщика запросов в соединениях
   • Требуется несколько строк на узел
4. Столбец Lineage (он же Материализованный путь, Перечисление пути)
   • Колонка: происхождение (например, /parent/child/ внучат /etc...)
   • Дешевые потомки с помощью префиксного запроса (например, LEFT(lineage, #) = '/enumerated/path')
   • Пишет расходы O(log n) (размер поддерева) для вставки, обновления, удаления
   • Нереляционный: использует тип данных Array или сериализованный формат строки
5. Вложенные интервалы
   • Как и вложенный набор, но с реальным /float/decimal, чтобы кодирование не было изменчивым (недорогое перемещение / вставка / удаление)
   • Имеет реальное / плавающее / десятичное представление / проблемы с точностью
   • Вариант матричного кодирования добавляет кодирование предка (материализованный путь) для "свободного", но с добавленной хитростью линейной алгебры.
6. Плоский стол
   • Модифицированный список смежности, который добавляет столбец уровня и ранга (например, порядок) к каждой записи.
   • Дешево перебирать / разбивать на страницы
   • Дорогой переместить и удалить
   • Полезное использование: обсуждение темы - форумы / комментарии блога
7. Несколько столбцов линии
   • Столбцы: по одному для каждого уровня происхождения, относятся ко всем родителям вплоть до корня, уровни ниже уровня элемента установлены в NULL.
   • Дешевые предки, потомки, уровень
   • Дешево вставить, удалить, переместить листья
   • Дорогая вставка, удаление, перемещение внутренних узлов
   • Жесткий предел того, насколько глубокой может быть иерархия

Примечания к базе данных

MySQL

• Используйте переменные сеанса для списка смежности

оракул

• Используйте CONNECT BY для прохождения списков смежности

PostgreSQL

• Тип данных дерева для Материализованного Пути

SQL Server

• Общее резюме
• 2008 предлагает тип данных HierarchyId, который помогает с подходом Lineage Column и расширяет глубину, которую можно представить.

Answer 1

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

До сих пор проблема заключалась в том, что метод покрытия из списка смежности для вложенных наборов был ужасно медленным, потому что большинство людей используют экстремальный метод RBAR, известный как "Push Stack", для выполнения преобразования и считался дорогостоящим. достичь Нирваны простоты обслуживания с помощью Списка Смежности и потрясающей производительности Вложенных Наборов. В результате большинству людей приходится довольствоваться тем или иным, особенно если их число превышает, скажем, 100000 паршивых узлов или около того. Использование метода push-стека может занять целый день, чтобы выполнить преобразование того, что MLM'еры посчитали бы иерархией с небольшим миллионом узлов.

Я решил дать Селко немного конкуренции, придумав метод преобразования Списка смежности во вложенные множества на скоростях, которые кажутся просто невозможными. Вот производительность метода push-стека на моем ноутбуке i5.

Duration for     1,000 Nodes = 00:00:00:870 
Duration for    10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10)
Duration for   100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) 
Duration for 1,000,000 Nodes = 'Didn't even try this'

А вот продолжительность нового метода (с методом push-стека в скобках).

Duration for     1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870)
Duration for    10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783)
Duration for   100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730)
Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)

Да, это правильно. 1 миллион узлов преобразуется менее чем за минуту, а 100000 узлов - менее чем за 4 секунды.

Вы можете прочитать о новом методе и получить копию кода по следующему URL. http://www.sqlservercentral.com/articles/Hierarchy/94040/

Я также разработал "предварительно агрегированную" иерархию, используя похожие методы. MLM'еры и люди, делающие списки материалов, будут особенно заинтересованы в этой статье. http://www.sqlservercentral.com/articles/T-SQL/94570/

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

Answer 2

Модель смежности + модель вложенных множеств

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

+-------------+----------------------+--------+-----+-----+
| category_id | name                 | parent | lft | rgt |
+-------------+----------------------+--------+-----+-----+
|           1 | ELECTRONICS          |   NULL |   1 |  20 |
|           2 | TELEVISIONS          |      1 |   2 |   9 |
|           3 | TUBE                 |      2 |   3 |   4 |
|           4 | LCD                  |      2 |   5 |   6 |
|           5 | PLASMA               |      2 |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |      1 |  10 |  19 |
|           7 | MP3 PLAYERS          |      6 |  11 |  14 |
|           8 | FLASH                |      7 |  12 |  13 |
|           9 | CD PLAYERS           |      6 |  15 |  16 |
|          10 | 2 WAY RADIOS         |      6 |  17 |  18 |
+-------------+----------------------+--------+-----+-----+

• Каждый раз, когда вам нужны все дети любого родителя, вы просто запрашиваете parent колонка.
• Если вам нужны все потомки любого из родителей, вы запрашиваете элементы, которые имеют свои lft между lft а также rgt родителя.
• Если вам нужны все родители любого узла вплоть до корня дерева, вы запрашиваете элементы, имеющие lft ниже, чем у узла lft а также rgt больше, чем узел rgt и сортировать по parent,

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

Единственная проблема состоит в том, чтобы исправить left а также right столбцы при вставке новых элементов. ну, я создал для него хранимую процедуру и вызывал ее каждый раз, когда вставлял новый элемент, что в моем случае было редкостью, но действительно быстро. Я получил идею из книги Джо Селко, а хранимая процедура и то, как я ее придумал, описаны здесь в DBA SE https://dba.stackexchange.com/q/89051/41481

Answer 3

Этот дизайн еще не был упомянут:

Несколько столбцов линии

Хотя у него есть ограничения, но если вы можете вынести их, это очень просто и очень эффективно. Особенности:

• Столбцы: по одному для каждого уровня происхождения, относятся ко всем родителям вплоть до корня, уровни ниже уровня текущих предметов установлены в NULL.
• Ограничить насколько глубоко может быть иерархия
• Дешевые предки, потомки, уровень
• Дешево вставить, удалить, переместить листья
• Дорогая вставка, удаление, перемещение внутренних узлов

Ниже приведен пример - таксономическое древо птиц, поэтому иерархия - Класс / Порядок / Семейство / Род / Вид - вид - самый низкий уровень, 1 строка = 1 таксон (что соответствует видам в случае узлов листа):

CREATE TABLE `taxons` (
  `TaxonId` smallint(6) NOT NULL default '0',
  `ClassId` smallint(6) default NULL,
  `OrderId` smallint(6) default NULL,
  `FamilyId` smallint(6) default NULL,
  `GenusId` smallint(6) default NULL,
  `Name` varchar(150) NOT NULL default ''
);

и пример данных:

+---------+---------+---------+----------+---------+-------------------------------+
| TaxonId | ClassId | OrderId | FamilyId | GenusId | Name                          |
+---------+---------+---------+----------+---------+-------------------------------+
|     254 |       0 |       0 |        0 |       0 | Aves                          |
|     255 |     254 |       0 |        0 |       0 | Gaviiformes                   |
|     256 |     254 |     255 |        0 |       0 | Gaviidae                      |
|     257 |     254 |     255 |      256 |       0 | Gavia                         |
|     258 |     254 |     255 |      256 |     257 | Gavia stellata                |
|     259 |     254 |     255 |      256 |     257 | Gavia arctica                 |
|     260 |     254 |     255 |      256 |     257 | Gavia immer                   |
|     261 |     254 |     255 |      256 |     257 | Gavia adamsii                 |
|     262 |     254 |       0 |        0 |       0 | Podicipediformes              |
|     263 |     254 |     262 |        0 |       0 | Podicipedidae                 |
|     264 |     254 |     262 |      263 |       0 | Tachybaptus                   |

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

Answer 4

Это очень частичный ответ на ваш вопрос, но я надеюсь, все еще полезно.

Microsoft SQL Server 2008 реализует две функции, которые чрезвычайно полезны для управления иерархическими данными:

• тип данных HierarchyId.
• общие табличные выражения, использующие ключевое слово with.

Посмотрите "Моделирование ваших иерархий данных с SQL Server 2008" Кента Тегелса на MSDN для начала. См. Также мой собственный вопрос: рекурсивный запрос из одной таблицы в SQL Server 2008

Answer 5

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

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

У меня есть полное описание использования массивов для материализованных путей, если вам интересно.

Answer 6

Это действительно квадратный колышек, вопрос круглой дыры.

Если реляционные базы данных и SQL являются единственным молотком, который у вас есть или вы хотите использовать, то ответы, опубликованные до сих пор, являются адекватными. Однако почему бы не использовать инструмент, предназначенный для обработки иерархических данных? Граф базы данных идеально подходит для сложных иерархических данных.

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

Рассмотрим спецификацию как общую иерархическую структуру данных.

class Component extends Vertex {
    long assetId;
    long partNumber;
    long material;
    long amount;
};

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

Сходство: Какова степень сходства между двумя сборками? Выполните обход на обоих поддеревьях, вычисляя пересечение и объединение двух поддеревьев. Процент подобный - это пересечение, деленное на союз.

Транзитивное закрытие: пройдитесь по поддереву и суммируйте интересующее вас поле (поля), например, "Сколько алюминия содержится в подсборке?"

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

Answer 7

Я использую PostgreSQL с таблицами закрытия для своих иерархий. У меня есть одна универсальная хранимая процедура для всей базы данных:

CREATE FUNCTION nomen_tree() RETURNS trigger
    LANGUAGE plpgsql
    AS $_$
DECLARE
  old_parent INTEGER;
  new_parent INTEGER;
  id_nom INTEGER;
  txt_name TEXT;
BEGIN
-- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG)
-- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE)
-- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT)
    IF TG_OP = 'INSERT' THEN
    EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT $1.id,$1.id,0 UNION ALL
      SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW;
    ELSE                                                           
    -- EXECUTE does not support conditional statements inside
    EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW;
    IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN
      EXECUTE '
      -- prevent cycles in the tree
      UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2]
        || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM '
        || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id);
      -- first remove edges between all old parents of node and its descendants
      DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN
        (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id)
        AND ancestor_id IN
        (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id);
      -- then add edges for all new parents ...
      INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) 
        SELECT child_id,ancestor_id,d_c+d_a FROM
        (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child
        CROSS JOIN
        (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' 
        || TG_ARGV[2] || ') AS parent;' USING OLD, NEW;
    END IF;
  END IF;
  RETURN NULL;
END;
$_$;

Затем для каждой таблицы, где у меня есть иерархия, я создаю триггер

CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');

Для заполнения таблицы закрытия из существующей иерархии я использую эту хранимую процедуру:

CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void
    LANGUAGE plpgsql
    AS $$
BEGIN
    EXECUTE 'TRUNCATE ' || tbl_closure || ';
    INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) 
        WITH RECURSIVE tree AS
      (
        SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || '
        UNION ALL 
        SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t
        JOIN tree ON child_id = ' || fld_parent || '
      )
      SELECT * FROM tree;';
END;
$$;

Таблицы закрытия определяются тремя столбцами: ANCESTOR_ID, DESCENDANT_ID, DEPTH. Можно (и я даже советую) хранить записи с одинаковым значением для ANCESTOR и DESCENDANT и нулевым значением для DEPTH. Это упростит запросы для поиска иерархии. И они действительно очень просты:

-- get all descendants
SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0;
-- get only direct descendants
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1;
-- get all ancestors
SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0;
-- find the deepest level of children
SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;

Answer 8

MySQL теперь поддерживает тип данных JSON:

https://dev.mysql.com/doc/refman/8.0/en/json.html