Оптимизированный SQL для древовидных структур

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

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

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

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

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

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

Google по запросу "Материализованный путь" или "Генетические деревья" ...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В продукте, над которым я работаю, у нас есть некоторые древовидные структуры, хранящиеся в 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))

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

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

Celko писал об этом (2000):

http://www.dbmsmag.com/9603d06.html

http://www.intelligententerprise.com/001020/celko1_1.jhtml;jsessionid=3DFR02341QLDEQSNDLRSKHSCJUNN2JVN?_requestid=32818

и другие люди спрашивали:

Присоединение к другим таблицам в запросах дерева оракула

Как вычислить сумму значений в дереве с помощью SQL

Как сохранить каталог / иерархию / древовидную структуру в базе данных?

Производительность рекурсивных хранимых процедур в MYSQL для получения иерархических данных

Какой самый эффективный / элегантный способ преобразовать плоскую таблицу в дерево?

наконец, вы можете взглянуть на подключаемые модули rails "plays_as_tree" (с интенсивным чтением) и "actions_as_nested_set" (с большим количеством операций записи). У меня нет хорошей ссылки для их сравнения.

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

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

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

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

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

Не будет работать для всех ситуаций, но, например, с учетом структуры комментариев:

ID | ParentCommentID

Вы также можете сохранить TopCommentID, который представляет собой самый верхний комментарий:

ID | ParentCommentID | TopCommentID

Где TopCommentID и ParentCommentID - это null или 0, когда это самый верхний комментарий. Для дочерних комментариев ParentCommentID указывает на комментарий над ним, а TopCommentID указывает на самого верхнего родителя.