По материалам статьи Eugene Lepekhin: Trees in SQL databases
Перевод Александра Гладченко

Статья рассказывает о том, как улучшить производительность деревьев в SQL.

Введение

Рано или поздно в своём проекте баз данных Вы столкнетесь с необходимостью хранения иерархической информации. Например: структура предприятия, категории товаров, каталог изделий или папок с документами; всё это хорошие примеры иерархических структур. Конечно же, можно реализовать их хранение в виде самосвязанной таблицы. Проблемы начнутся, когда нужно будет создавать запросы к иерархическим данным. Например: "Что, если мы имеем дело со структурой предприятия, и хотим узнать, сколько служащих подчиняются менеджеру X?". Такие решения подобных проблем уже были описаны. Например, можно посмотреть книгу и статьи Joe Celko, в которых есть подробные описания таких решений.
Упомянутые выше методы хороши, когда необходимо только читать данные, но когда потребуется изменять дерево, может наблюдаться значительное снижение производительности.
Автор собирается предложить свой метод, сравнимый по производительности чтения, но более производительный при модификации дерева.

[В начало]

Идея

Предположим, что мы имеем следующую таблицу:

Где: NodeId - первичный ключ, ParentId - внешний ключ и NodeName - некоторое дополнительное поле. Чтобы упростить последующие примеры, давайте предположим, что NodeName имеет ограничение уникальности.
Для всех представленных ниже примеров автор будет использовать следующее дерево:

Создадим ещё одну таблицу, имеющую две связи с таблицей Node:

В этой таблице NodeId и ParentId - внешние ключи, ссылающиеся на таблицу Node.
Каждая запись в таблице Tree означает, что указанный в поле Tree.NodeId узел имеет предка, указанного в поле Tree.ParentId. Под предком автор понимает любой другой узел, расположенный на пути от узла к корню дерева, то есть прямого родителя или главного родителя или самого главного родителя и так далее.
Теперь давайте убедимся, что справедлив один простой инвариант: все предки каждого узла таблицы Node перечислены в таблице Tree.
Например, для узла 4 они могут быть 2 и 1.
Непосредственный вывод из этого инварианта: очень просто можно получить полный путь от узла до корня дерева. Для этого нужно получить всё записи из таблицы Tree, связанные с искомым узлом. Давайте составим соответствующий запрос. Предположим, что мы должны найти путь к корню от узла 7.

Запрос 1:

select p.*
from Node n, Tree t, Node p
where n.NodeName=7
    and n.NodeId = t.NodeId
    and t.ParentId = p.NodeId

Получился простой и понятный запрос, не правда ли?
Второй вывод из упомянутого выше инварианта: мы можем получить всех потомков узла. Из-за этого в таблице Tree перечисляются все предки для каждого узла в таблицы Node, включая конечно же всех предков искомого узла. Чтобы получить полное поддерево узла, достаточно запросить все узлы, которые имеют искомый узел в качестве предка.

Запрос 2:

select c.*
from Node n, Tree t, Node c
where n.NodeName=2
    and n.NodeId = t.ParentId
    and t.NodeId = c.NodeId

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

[В начало]

Реализация

Перед тем, как двигаться дальше, автор хотел бы сделать два примечания.

№ 1: Из своего опыта, автор считает, что очень удобно иметь еще одно поле в таблице Tree, которое бы хранило величину удаления в дереве между узлами, указанными в NodeId и ParentId, другими словами - уровень предка. Поэтому, предлагаемая фактическая структура включает поле Level:


№ 2: Самыми распространёнными задачами, являются задачи, использующие поддеревья узла или путь к узлу от корня, включая сам этот узел. Так что было бы полезно иметь в таблице Tree непосредственно и сам узел в качестве собственного предка с уровнем 0.

Можно реализовать описанный инвариант в виде хранимой процедуры или в виде триггеров. Автор предпочитает делать это в одном триггере.
Давайте начнём с триггера на вставку (INSERT) для таблицы Node. Для примеров автор будет использовать MS SQL Server.
Прежде всего, триггер должен создать запись, удовлетворяющую примечанию № 2. Это можно сделать следующей инструкцией:

    insert into Tree(NodeId, ParentId, Level)
    select NodeId, NodeId, 0
    from inserted

После этого можно добавить список всех предков вставленного узла. Имея ввиду, что родитель каждого вставляемого узла уже имеет список всех своих предков, поэтому мы можем использовать их за основу. Но мы должны заменить NodeId родителя на id нового узла и увеличить уровень.

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

Таким образом, код триггера будет иметь следующий вид:

create trigger NodeInsert on Node for insert as
begin
    set nocount on

    insert into Tree(NodeId, ParentId, Level)
    select NodeId, NodeId, 0
    from inserted

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId
end
go

Теперь пришло время продумать триггер на UPDATE, который позаботится о родителе изменяемого узла. Цель триггера на UPDATE состоит в том, чтобы удалить все устаревшие записи в таблице Tree и заменить их новыми. Чтобы минимизировать изменения, совершаемые этим триггером, давайте повторно использовать ту информацию, которая уже имеется в таблице Tree, аналогично тому способу, который мы использовали в триггере на вставку записи. Но разве нельзя просто изменить родителя узла?
Очевидно, что непосредственно для изменяемого узла только одна запись удовлетворяет примечанию № 2. У потомков будут правильными те записи о предках, которые расположены ниже изменяемого узла, включая и сам этот узел. В то же время, каждый находящийся выше изменяемого узла предок будет устаревшим.
Например, если мы изменяем родителя для узла 4, тогда для узлов 5, 6 и 7 будут изменены только те предки, которые выше узла 4, то есть 1 и 2.
На первом шаге мы копируем всех потомков изменяемых узлов вот в такую таблицу:

    declare @child table(NodeId int, Level int)

Туда мы вставляем первичные ключи всех потомков и уровни каждого из них относительно изменяемых узлов. Условие, что t.Level > 0, позволяет исключать изменяемый узел из вставки в таблицу @child.

insert into @child(NodeId, Level) select t.NodeId, t.Level from inserted n, Tree t where n.NodeId = t.ParentId and t.Level > 0

Второй шаг удаляет все устаревшие строки у всех потомков:

    delete Tree
    where
        Tree.NodeId in(select NodeId from @child)
        and Tree.ParentId in(
            select t.ParentId
            from inserted n, Tree t
            where n.NodeId = t.NodeId and t.Level > 0
        )

Условие, что t.Level > 0, исключает удаление изменяемых узлов.
Третий шаг удаляет устаревшие записи изменённых узлов:

    delete Tree
    where Tree.NodeId in(select NodeId from inserted)
        and Tree.Level > 0

Следующие два шага заполняют таблицу Tree новой информацией. Соответственно, это будет так:

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

Всё это делается так же, как мы это делали в триггере на вставку.
И, наконец, пятый шаг:

    insert into Tree(NodeId, ParentId, Level)
    select c.NodeId, t.ParentId, t.Level + c.Level
    from inserted n, Tree t, @child c
    where n.NodeId = t.NodeId and t.Level > 0

Может показаться странным, что тут не используются какие-либо соединения с таблицей @child. Но эта инструкция - именно то, что нам здесь нужно, потому что мы собираемся повторить информацию о предке для каждого детишки. Также обратите внимание на то, как мы добавляем уровень детишек, хранящийся в таблице @child, который скорее всего только 1.
Весь триггер будет таким:

create trigger NodeUpdate on Node for update as
if update(ParentId)
begin
    set nocount on

    declare @child table(NodeId int, Level int)

    insert into @child(NodeId, Level)
    select t.NodeId, t.Level
    from inserted n, Tree t
    where n.NodeId = t.ParentId and t.Level > 0

    delete Tree
    where
        Tree.NodeId in(select NodeId from @child)
        and Tree.ParentId in(
            select t.ParentId
            from inserted n, Tree t
            where n.NodeId = t.NodeId and t.Level > 0
        )

    delete Tree
    where Tree.NodeId in(select NodeId from inserted) and Tree.Level > 0

    insert into Tree(NodeId, ParentId, Level)
    select n.NodeId, t.ParentId, t.Level + 1
    from inserted n, Tree t
    where n.ParentId = t.NodeId

    insert into Tree(NodeId, ParentId, Level)
    select c.NodeId, t.ParentId, t.Level + c.Level
    from inserted n, Tree t, @child c
    where n.NodeId = t.NodeId and t.Level > 0
end
go

Как Вы можете видеть, это будет работать только если изменялся ParentId, и все другие изменения таблицы Node будут отфильтрованы самым первым оператором в условии.

[В начало]

Ограничения использования

Если Вы собираетесь одновременно вставлять или изменять более одного узла, убедитесь, что Вы не делаете это более чем для одного уровня дерева. С практической точки зрения это - не сильное ограничение.

[В начало]

Дополнительные шаги

Для завершения функциональности, нужно иметь возможность полностью очищать таблицу Tree и заполнять её заново. Хорошая идея, написать для этого хранимую процедуру, но автор не собирается портить Вам удовольствие создать её самостоятельно.

[В начало]

Примеры

Вы можете загрузить по указанной ниже ссылке необходимый SQL-код, который поможет создать обе таблицы и триггеры, а также команды для заполнения тестовыми данными таблицы Node. В загружаемом файле также содержатся запросы 1 и 2 и скрипт для изменения родителя узла.

• Download example - 1 Kb

[В начало]