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

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

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

• Еще одно сравнение вложенных интервалов и списка смежности : лучшее сравнение списка смежности, материализованного пути, вложенного набора и вложенного интервала, которое я нашел.
• Модели для иерархических данных : слайды с хорошими объяснениями компромиссов и примера использования
• Представление иерархий в 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 и расширяет глубину, которую можно представить.

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

До сих пор проблема заключалась в том, что метод покрытия из списка смежности для вложенных наборов был ужасно медленным, потому что большинство людей используют экстремальный метод RBAR, известный как «Push Stack», для выполнения преобразования и считался дорогостоящим. достичь Нирваны простоты обслуживания с помощью Списка Смежности и потрясающей производительности Вложенных Наборов. В результате большинству людей приходится довольствоваться тем или иным, особенно если их число превышает 100 000, скажем, паршивых узлов. Использование метода 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 миллион узлов преобразуется менее чем за минуту, а 100 000 узлов - менее чем за 4 секунды.

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

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

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

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

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

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

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

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

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

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

• Столбцы: по одному для каждого уровня происхождения, относятся ко всем родителям вплоть до корня, уровни ниже уровня текущего элемента установлены в 0 (или 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                   |

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

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

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

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

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

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

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

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

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

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

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

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

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

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

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

Я использую 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;
$$;

Таблицы закрытия определяются 3 столбцами - 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;