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

avatar
orangepips
29 октября 2010 в 00:23
284359
7
1435

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

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

Параметры

Известные мне и общие особенности:

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

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

MySQL

Oracle

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

PostgreSQL

SQL Server

  • Общая информация
  • 2008 предлагает тип данных HierarchyId, чтобы помочь с подходом Lineage Column и расширить глубину, которая может быть представлена.
Источник
Gili
1 ноября 2012 в 00:36
9

Согласно slideshare.net/billkarwin/sql-antipatterns-strike-back страница 77, Closure Tables превосходит Adjacency List, Path Enumeration и Nested Sets с точки зрения простоты использования Я тоже угадываю производительность).

Lothar
12 ноября 2015 в 16:22
0

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

orangepips
23 января 2016 в 12:51
0

@Lothar: вопрос - это вики сообщества, так что не стесняйтесь. Я думаю в этом отношении, что я бы сделал это только с теми базами данных, которые поддерживают какую-то структуру блобов, такую ​​как XML, со стабильным языком запросов, таким как XPATH. В противном случае я не вижу хорошего способа запроса, кроме извлечения, десериализации и изменения кода, а не SQL. И если у вас действительно есть проблема, когда вам нужно много произвольных элементов, вам может быть лучше использовать базу данных Node, такую ​​как Neo4J, которую я использовал и любил, хотя никогда не использовался в производстве.

kͩeͣmͮpͥ ͩ
18 октября 2017 в 10:19
3

Ссылка MSDN на «Общее резюме» больше не отображает статью. Это было в выпуске MSDN Magazine за сентябрь 2008 г., который вы можете загрузить в виде файла CHM или просмотреть в веб-архиве по адресу: web.archive.org/web/20080913041559/http://msdn.microsoft.com : 80 /…

Ответы (7)

avatar
TMS
20 июня 2020 в 09:12
30

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

Несколько столбцов происхождения

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

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

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

avatar
azerafati
13 апреля 2017 в 12:42
29

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

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

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

orangepips
23 января 2016 в 12:54
3

+1 это законный подход. По моему собственному опыту, ключевым моментом является решение, согласны ли вы с грязным чтением, когда происходят большие операции обновления. В противном случае это становится проблемой или препятствует тому, чтобы люди напрямую запрашивали таблицы и всегда проходили через API - sprocs / функции БД или код.

Thomas
16 марта 2016 в 17:44
2

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

azerafati
17 марта 2016 в 06:25
4

@Thomas, есть разница между children и descendants. left и right используются для поиска потомков.

avatar
1 августа 2016 в 14:33
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;
$$;

Таблицы замыкания определены с 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;
avatar
30 сентября 2014 в 13:45
11

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

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

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

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

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

class PartOf extends Edge {
};

class AdjacentTo extends Edge {
};

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

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

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

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

orangepips
6 января 2015 в 13:58
7

Этот ответ был бы намного полезнее, если бы варианты использования продемонстрировали или, еще лучше, противопоставили, как запрашивать базу данных графа, например, с помощью SPARQL вместо SQL в СУБД.

djhallx
7 января 2015 в 16:05
1

SPARQL относится к базам данных RDF, которые являются подклассом более крупной области графических баз данных. Я работаю с InfiniteGraph, которая не является базой данных RDF и в настоящее время не поддерживает SPARQL. InfiniteGraph поддерживает несколько различных механизмов запросов: (1) API-интерфейс навигации по графу для настройки представлений, фильтров, квалификаторов путей и обработчиков результатов, (2) язык сопоставления шаблонов сложных путей в графах и (3) Gremlin.

avatar
15 мая 2013 в 04:35
15

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

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

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

avatar
Jeff Moden
4 марта 2013 в 02:22
84

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

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

Я подумал, что дам Celko немного посоревноваться, придумав метод преобразования списка смежности во вложенные наборы на скоростях, которые просто кажутся невозможными. Вот производительность метода 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 stack в скобках).

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/

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

David Mann
9 июля 2019 в 19:25
1

Что такое MLMer?

Jeff Moden
10 июля 2019 в 20:47
1

MLM = «Многоуровневый маркетинг». Amway, Shaklee, ACN и т. Д. И т. Д.

avatar
CesarGon
29 октября 2010 в 00:34
32

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

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

Для начала ознакомьтесь с «Моделируйте свои иерархии данных с помощью SQL Server 2008» Кента Тегельса в MSDN. См. Также мой собственный вопрос: Рекурсивный запрос той же таблицы в SQL Server 2008

orangepips
29 октября 2010 в 00:38
3

Интересно, что HierarchyId не знал об этом: msdn.microsoft.com/en-us/library/bb677290.aspx

CesarGon
29 октября 2010 в 00:41
1

Действительно. Я работаю с большим количеством рекурсивно иерархических данных и считаю очень полезными общие табличные выражения. См. Введение в msdn.microsoft.com/en-us/library/ms186243.aspx.