Как реализовать высокопроизводительное представление дерева в SQL Server 2005

Question

Каков наилучший способ построить таблицу, которая будет представлять дерево? Я хочу реализовать выбор, вставку, обновление и удаление, которые будут хорошо работать с большими данными. Например, выбор должен поддерживать «Expand ALL» - получение всех дочерних элементов (и дочерних элементов) для данного узла.

Answer 1

Использование CTE.

Учитывая древовидную структуру таблицы:

id parent name
1  0      Electronics
2  1      TV
3  1      Hi-Fi
4  2      LCD
5  2      Plasma
6  3      Amplifiers
7  3      Speakers

, этот запрос вернет id, parent и уровень глубины, упорядоченный в виде дерева:

WITH    v (id, parent, level) AS
        (
        SELECT  id, parent, 1
        FROM    table
        WHERE   parent = 0
        UNION ALL
        SELECT  id, parent, v.level + 1
        FROM    v
        JOIN    table t
        ON      t.parent = v.id
        )
SELECT  *
FROM    v

id parent name
1  0      Electronics
2  1        TV
4  2          LCD
5  2          Plasma
3  1        Hi-Fi
6  3          Amplifiers
7  3          Speakers

Замените parent = 0 на parent = @parent, чтобы получить только ветку дерева.

При условии наличия индекса на table (parent) этот запрос будет эффективно работать с очень большой таблицей, поскольку он будет рекурсивно использовать INDEX LOOKUP, чтобы найти все chilrden для каждого родителя.

Чтобы обновить определенную ветку, введите:

WITH    v (id, parent, level) AS
        (
        SELECT  id, parent, 1
        FROM    table
        WHERE   parent = 0
        UNION ALL
        SELECT  id, parent, v.level + 1
        FROM    v
        JOIN    table t
        ON      t.parent = v.id
        )
UPDATE  table t
SET     column = newvalue
WHERE   t.id IN
        (
        SELECT  id
        FROM    v
        )

где @parent - корень ветви.

Answer 2

Сначала вы должны задать себе следующие вопросы: 1) Каково соотношение модификаций и чтений? (= в основном статическое дерево или постоянно меняющееся?) 2) Какую глубину и насколько вы ожидаете, что дерево вырастет?

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

Материализованный путь хорошо работает для динамических (изменяющихся) деревьев с ограниченной / предсказуемой глубиной.

Рекурсивные CTE идеальны для очень маленьких деревьев, но операции с ветвями ("получить всех дочерних элементов в этой ветке ..") становятся очень дорогими с глубоким / большим деревом.

Answer 3

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

Answer 4

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

http://www.sqlteam.com/article/more-trees-hierarchies-in-sql

Answer 5

Я удивлен, что никто не упомянул про использование таблицы закрытия . Очень эффективен для чтения и довольно прост для записи.