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

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

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

Опции

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

  1. Список смежности :
    • Столбцы: ID, ParentID
    • Простота реализации.
    • Дешевый узел перемещает, вставляет и удаляет.
    • Дорого, чтобы найти уровень, родословную & amp; потомки, путь
    • Избегайте N + 1 через Общих табличных выражений в базах данных, которые их поддерживают
  2. Вложенный набор (a. к. Модифицированный обход дерева предзаказа )
    • Колонны: слева, справа
    • Дешевое происхождение, потомки
    • Очень дорого O(n/2) перемещает, вставляет, удаляет из-за изменчивой кодировки
  3. Мостовой стол (а. к. а. Закрытие таблицы / ш триггеров )
    • Использует отдельную таблицу соединения с: предком, потомком, глубиной (необязательно)
    • Дешевые предки и потомки
    • Записывает затраты O(log n) (размер поддерева) для вставки, обновления, удаления
    • Нормализованное кодирование: хорошо для статистики RDBMS & amp; планировщик запросов в соединениях
    • Требуется несколько строк на узел
  4. Колонна Линии (а. к. а. Материализованный путь , перечисление пути)
    • Колонка: происхождение (эл. г. / Родитель / ребенок / внучат / и т.д.. , , )
    • Дешевые потомки с помощью префиксного запроса (e. г. LEFT(lineage, #) = '/enumerated/path')
    • Записывает затраты O(log n) (размер поддерева) для вставки, обновления, удаления
    • Нереляционный: использует тип данных Array или сериализованный формат строки
  5. Вложенные интервалы
    • Как вложенный набор, но с вещественным / плавающим / десятичным, чтобы кодирование не было изменчивым (недорогое перемещение / вставка / удаление)
    • Имеет реальное / плавающее / десятичное представление / вопросы точности
    • Вариант матричного кодирования добавляет кодирование предка (материализованный путь) для «свободного», но с добавленной хитростью линейной алгебры.
  6. Плоский стол
    • Модифицированный список смежности, который добавляет уровень и ранг (например, г. порядок) столбец для каждой записи.
    • Дешево повторять / разбивать на страницы в течение
    • Дорогой переместить и удалить
    • Хорошо использовать: обсуждение темы - форумы / комментарии в блоге
  7. Несколько столбцов линии
    • Столбцы: по одному для каждого уровня линии, относится ко всем родителям вплоть до корня, уровни ниже уровня элемента установлены в NULL
    • Дешевые предки, потомки, уровень
    • Дешево вставить, удалить, переместить листья
    • Дорогая вставка, удаление, перемещение внутренних узлов
    • Жесткий предел того, насколько глубокой может быть иерархия.

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

MySQL

Oracle

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

PostgreSQL

SQL Server

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

7 ответов


  • 36 рейтинг

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

    Проблема до сих пор заключалась в том, что метод покрытия из списка смежности для вложенных наборов был ужасно медленным, потому что большинство людей используют экстремальный метод 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. ru / статьи / иерархия / 94040/

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

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

    ответ дан Jeff Moden, с репутацией 2238, 4.03.2013
  • 23 рейтинг

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

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

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

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

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

    ответ дан TMS, с репутацией 32648, 18.01.2014
  • 22 рейтинг

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

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

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

    ответ дан CesarGon, с репутацией 11797, 29.10.2010
  • 15 рейтинг

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

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

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

    ответ дан azerafati, с репутацией 10002, 5.11.2015
  • 11 рейтинг

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

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

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

    ответ дан Adam Sanderson, с репутацией 381, 15.05.2013
  • 7 рейтинг

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

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

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

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

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

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

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

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

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

    ответ дан djhallx, с репутацией 6, 30.09.2014
  • 5 рейтинг

    Я использую 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;
    
    ответ дан IVO GELOV, с репутацией 2534, 1.08.2016