Оптимизированный SQL для древовидных структур - PullRequest
35 голосов
/ 25 ноября 2008

Как бы вы получили древовидные данные из базы данных с наилучшей производительностью? Например, скажем, у вас есть папка-иерархия в базе данных. Где строка-папка-база данных имеет столбцы ID , Имя и ParentID .

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

Или вы бы использовали много обращений к базе данных и вроде бы получали структуру, сделанную непосредственно из базы данных?

Может быть, есть разные ответы в зависимости от количества строк в базе данных, глубины иерархии или чего-то еще?

Редактировать : Я использую Microsoft SQL Server, но интересны и другие перспективы.

Ответы [ 12 ]

16 голосов
/ 25 ноября 2008

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

Один умный метод - дать каждому узлу идентификатор строки, где идентификатор родителя является предсказуемой подстрокой дочернего элемента. Например, родительский объект может быть «01», а дочерние - «0100», «0101», «0102» и т. Д. Таким образом, вы можете выбрать целое поддерево из базы данных одновременно с помощью:

SELECT * FROM treedata WHERE id LIKE '0101%';

Поскольку критерием является исходная подстрока, индекс столбца ID ускорит запрос.

15 голосов
/ 17 декабря 2008

Из всех способов хранения дерева в RDMS наиболее распространенными являются списки смежности и вложенные множества. Вложенные наборы оптимизированы для чтения и могут извлекать все дерево за один запрос. Списки смежности оптимизированы для записи и могут быть добавлены с помощью простого запроса.

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

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

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

Мои исследования этого метода начались в этой статье: Управление иерархическими данными в MySQL .

13 голосов
/ 25 ноября 2008

посмотрите на модель иерархии вложенных множеств . это довольно круто и полезно.

6 голосов
/ 25 ноября 2008

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

tblTreeNode
TreeID = 1
TreeNodeID = 100
ParentTreeNodeID = 99
Hierarchy = ".33.59.99.100."
[...] (actual data payload for node)

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

вы можете получить всех потомков узла таким образом:

SELECT * FROM tblNode WHERE Hierarchy LIKE '%.100.%'

Вот триггер вставки:

--Setup the top level if there is any
UPDATE T 
SET T.TreeNodeHierarchy = '.' + CONVERT(nvarchar(10), T.TreeNodeID) + '.'
FROM tblTreeNode AS T
    INNER JOIN inserted i ON T.TreeNodeID = i.TreeNodeID
WHERE (i.ParentTreeNodeID IS NULL) AND (i.TreeNodeHierarchy IS NULL)

WHILE EXISTS (SELECT * FROM tblTreeNode WHERE TreeNodeHierarchy IS NULL)
    BEGIN
        --Update those items that we have enough information to update - parent has text in Hierarchy
        UPDATE CHILD 
        SET CHILD.TreeNodeHierarchy = PARENT.TreeNodeHierarchy + CONVERT(nvarchar(10),CHILD.TreeNodeID) + '.'
        FROM tblTreeNode AS CHILD 
            INNER JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID
        WHERE (CHILD.TreeNodeHierarchy IS NULL) AND (PARENT.TreeNodeHierarchy IS NOT NULL)
    END

и вот триггер обновления:

--Only want to do something if Parent IDs were changed
IF UPDATE(ParentTreeNodeID)
    BEGIN
        --Update the changed items to reflect their new parents
        UPDATE CHILD
        SET CHILD.TreeNodeHierarchy = CASE WHEN PARENT.TreeNodeID IS NULL THEN '.' + CONVERT(nvarchar,CHILD.TreeNodeID) + '.' ELSE PARENT.TreeNodeHierarchy + CONVERT(nvarchar, CHILD.TreeNodeID) + '.' END
        FROM tblTreeNode AS CHILD 
            INNER JOIN inserted AS I ON CHILD.TreeNodeID = I.TreeNodeID
            LEFT JOIN tblTreeNode AS PARENT ON CHILD.ParentTreeNodeID = PARENT.TreeNodeID

        --Now update any sub items of the changed rows if any exist
        IF EXISTS (
                SELECT * 
                FROM tblTreeNode 
                    INNER JOIN deleted ON tblTreeNode.ParentTreeNodeID = deleted.TreeNodeID
            )
            UPDATE CHILD 
            SET CHILD.TreeNodeHierarchy = NEWPARENT.TreeNodeHierarchy + RIGHT(CHILD.TreeNodeHierarchy, LEN(CHILD.TreeNodeHierarchy) - LEN(OLDPARENT.TreeNodeHierarchy))
            FROM tblTreeNode AS CHILD 
                INNER JOIN deleted AS OLDPARENT ON CHILD.TreeNodeHierarchy LIKE (OLDPARENT.TreeNodeHierarchy + '%')
                INNER JOIN tblTreeNode AS NEWPARENT ON OLDPARENT.TreeNodeID = NEWPARENT.TreeNodeID

    END

еще один бит, проверочное ограничение для предотвращения циклической ссылки в узлах дерева:

ALTER TABLE [dbo].[tblTreeNode]  WITH NOCHECK ADD  CONSTRAINT [CK_tblTreeNode_TreeNodeHierarchy] CHECK  
((charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy],(charindex(('.' + convert(nvarchar(10),[TreeNodeID]) + '.'),[TreeNodeHierarchy]) + 1)) = 0))

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

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

2 голосов
/ 25 ноября 2008

Существует несколько распространенных типов запросов к иерархии. Большинство других видов запросов являются вариациями на них.

  1. От родителя найди всех детей.

    а. На конкретную глубину. Например, учитывая моего непосредственного родителя, все дети на глубине 1 будут моими братьями и сестрами.

    б. К низу дерева.

  2. От ребенка найди всех родителей.

    а. На конкретную глубину. Например, мой непосредственный родитель - родители на глубину 1.

    б. На неограниченную глубину.

(а) случаи (определенной глубины) проще в SQL. Особый случай (глубина = 1) тривиален в SQL. Ненулевая глубина сложнее. Конечная, но ненулевая глубина может быть выполнена с помощью конечного числа соединений. Случаи (б), с неопределенной глубиной (сверху, снизу), действительно тяжелые.

Если у вас дерево ОГРОМНОЕ (миллионы узлов), тогда вы находитесь в мире боли независимо от того, что вы пытаетесь сделать.

Если ваше дерево меньше миллиона узлов, просто загрузите все это в память и поработайте там. Жизнь в мире ОО намного проще. Просто извлеките строки и постройте дерево, когда строки будут возвращены.

Если у вас есть Огромное дерево, у вас есть два варианта.

  • Рекурсивные курсоры для обработки неограниченного извлечения. Это означает, что поддержка структуры O (1) - просто обновите несколько узлов, и все готово. Однако выборка O (n * log (n)), потому что вам нужно открыть курсор для каждого узла с дочерними элементами.

  • Умные алгоритмы «нумерации кучи» могут кодировать происхождение каждого узла. После правильной нумерации каждого узла можно использовать тривиальный SQL SELECT для всех четырех типов запросов. Однако изменения в древовидной структуре требуют перенумерации узлов, что делает стоимость изменения довольно высокой по сравнению со стоимостью поиска.

1 голос
/ 25 ноября 2008

В Oracle есть оператор SELECT ... CONNECT BY для получения деревьев.

1 голос
/ 25 ноября 2008

Google для "Материализованного Пути" или "Генетических Деревьев" ...

1 голос
/ 25 ноября 2008

Я фанат простого метода хранения идентификатора, связанного с его parentID:

ID     ParentID
1      null
2      null
3      1
4      2
...    ...

Он прост в обслуживании и очень масштабируем.

1 голос
/ 25 ноября 2008

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

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

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

...