Подтвердить что ты не робот

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

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

вы можете получить всех потомков node:

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

Здесь триггер insert:

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

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

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

Ответ 5

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

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

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

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

Объединение других таблиц в запросы оракула

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

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

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

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

Наконец, вы можете посмотреть плагины "act_as_tree" (read-heavy) и "act_as_nested_set" (write-heavy). У меня нет хорошей ссылки, сравнивающей их.

Ответ 6

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

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

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

    б. В нижней части дерева.

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

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

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

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

Если дерево HUGE (миллионы узлов), то вы находитесь в мире болей, независимо от того, что вы пытаетесь сделать.

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

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

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

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

Ответ 7

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

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

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

Ответ 8

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

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

Легко поддерживать и очень масштабируемо.

Ответ 9

Google для "материализованного пути" или "генетических деревьев"...

Ответ 10

В Oracle есть инструкция SELECT... CONNECT BY для извлечения деревьев.

Ответ 11

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

Ответ 12

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

ID | ParentCommentID

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

ID | ParentCommentID | TopCommentID

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