Способы хранения иерархических данных.

Рассмотрим 2 способа хранения иерархических данных. Пусть есть сущность для экземпляров которой установлена связь предок-потомок. Есть 2 основных подхода для хранения таких данных. При первом подходе создается таблица с полями для обозначения идентификаторов сущности и ее родителя. При втором подходе в одном столбце хранится идентификатор сущности, а другом - информация обо всех родителях данной сущности. Изучим эффективность этих подходов при решении задач извлечения данных. Для тестирования создадим отдельную базу данных:

_­­­­­­­create database HierData

go

use HierData

go

Создадим таблицу для хранения деревьев в виде идентификатора и его родителя:

create table dbo.HierPoints

(

    iRootPointId        int not null,

    iRootPointParentId  int null,

    constraint PK_HierPoints_iRootPointId primary key clustered ( iRootPointId asc ) on [PRIMARY],

       constraint FK_HierPoints_iRootPointId_Hier foreign key ( iRootPointParentId ) references dbo.HierPoints ( iRootPointId )

             on update no action on delete no action

) on [PRIMARY]

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

set nocount on

declare @LvlNum int = 26, @CurLvl int = 1, @lvlCnt int, @maxRP int

while @CurLvl <= @LvlNum

begin

    if not exists

    (

        select 1

        from dbo.HierPoints

    )

    begin

        insert into dbo.HierPoints with ( tablock ) ( iRootPointId, iRootPointParentId )

            values ( 1, null )

        set @lvlCnt = @@rowcount

    end

    else

    begin

        set @maxRP = (

            select max ( iRootPointId )

            from dbo.HierPoints

        )

        insert into dbo.HierPoints with ( tablock ) ( iRootPointId, iRootPointParentId )

            select 2 * @lvlCnt + iRootPointId - 1, ( 2 * @lvlCnt + iRootPointId - 1 ) / 2

            from

            (

                select top ( @lvlCnt ) iRootPointId

                from dbo.HierPoints

                order by iRootPointId

            ) data

        set @lvlCnt = @@rowcount

        insert into dbo.HierPoints with ( tablock ) ( iRootPointId, iRootPointParentId )

            select 3 * @lvlCnt + iRootPointId - 1, ( 3 * @lvlCnt + iRootPointId - 1 ) / 2

            from

            (

                select top ( @lvlCnt ) iRootPointId

                from dbo.HierPoints

                order by iRootPointId

            ) data

        set @lvlCnt += @@rowcount

    end

    set @CurLvl += 1

end

Код отрабатывает за полчаса на ноутбуке, наполняя таблицу примерно 67-ю миллионами записей. Объем таблицы составил 1 Гб. Необходимо отметить что использование хинта tablock на маломощных компьютерах обязательно, так как иначе быстрее чем произойдет эскалация блокировок может возникнуть ошибка, связанная с нехваткой памяти для хранения информации о блокировках.

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

create nonclustered index IX_iRootPointParentId on dbo.HierPoints ( iRootPointParentId asc ) on [PRIMARY]

Объем индекса составил 0.9 Гб. Теперь можно создать 2 хранимые процедуры. Одна извлекает информацию обо всех родителях данного экземпляра, а вторая извлекает все поддерево для заданного узла:

create proc dbo.GetParentPoints

(

    @iRootPointId int

)

as

begin

    set nocount, xact_abort on

    ;

    with RP

    as

    (

        select iRootPointId, iRootPointParentId, 0 Lvl

        from dbo.HierPoints

        where iRootPointId = @iRootPointId

            union all

        select hier.iRootPointId, hier.iRootPointParentId, RP.Lvl + 1

        from

            dbo.HierPoints hier

                inner join

            RP on hier.iRootPointId = RP.iRootPointParentId

    )

    select *

    from RP

    option ( maxrecursion 0 )

end

go

create proc dbo.GetChildPoints

(

    @iRootPointId int,

    @IsParentIncl bit = 0

)

as

begin

    set nocount, xact_abort on

    declare @num int, @lvl int = 0

    if object_id ( N'tempdb..#HierData', N'U' ) is not null

        drop table #HierData

    create table #HierData

    (

        iRootPointId        int not null,

        iRootPointParentId  int not null,

        iLevel              int not null,

        primary key clustered ( iLevel asc, iRootPointId asc ) on [PRIMARY]

    ) on [PRIMARY]

    insert into #HierData ( iRootPointId, iRootPointParentId, iLevel )

        select iRootPointId, iRootPointParentId, @lvl

        from dbo.HierPoints

        where iRootPointId = @iRootPointId

    set @num = 1

    while @num <> 0

    begin

        insert into #HierData ( iRootPointId, iRootPointParentId, iLevel )

            select hier.iRootPointId, hier.iRootPointParentId, @lvl + 1

            from

                #HierData tmp

                    inner join

                dbo.HierPoints hier on

                    tmp.iLevel = @lvl and

                    tmp.iRootPointId = hier.iRootPointParentId

        set @num = @@rowcount

        set @lvl += 1

    end

    if @IsParentIncl = 1

    begin

        select iRootPointId, iRootPointParentId, iLevel

        from #HierData

    end

    else

    begin

        select iRootPointId, iLevel

        from #HierData

    end

end

go

Во второй процедуре для извлечения поддерева используется цикл а не рекурсивный CTE. Это связано с тем, что при написании рекурсивного CTE в его рекурсивной части не получится просто соединить CTE на таблицу: появятся дублирующиеся записи. Для их исключения надо еще раз добавить условие на CTE. Однако в рекурсивном CTE нельзя упоминать его имя более одного раза.

Теперь создадим таблицу для хранения идентификаторов с избыточной информацией обо всех родителях.

create table dbo.HierPaths

(

    iRootPointId int                    not null,

    hPath        hierarchyid            not null,

    iLevel       as hPath.GetLevel ()   persisted,

)

go

Здесь мы используем новый для MS SQL 2008 CLR-тип данных hierarchyid, который содержит всю необходимую информацию о предках для iRootPointId. В качестве уровня дерева используется вычисляемое поле на основе метода GetLevel. Для облегчения работы запросов понадобятся индексы:

create unique clustered index IX_hPath on dbo.HierPaths ( hPath asc ) on [PRIMARY]

create unique nonclustered index IX_iLevel_hPath on dbo.HierPaths ( iLevel asc, hPath asc ) on [PRIMARY]

create unique  nonclustered index IX_iRootPointId on dbo.HierPaths ( iRootPointId asc ) on [PRIMARY]

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

set nocount on

declare @LvlNum int = 26, @CurLvl int = -1, @lvlCnt int, @maxRP int

while @CurLvl <= @LvlNum

begin

    if not exists

    (

        select 1

        from dbo.HierPaths

    )

    begin

        insert into dbo.HierPaths with ( tablock ) ( iRootPointId, hPath )

            values ( 1, hierarchyid::Parse ( N'/1/' ) )

    end

    else

    begin

        insert into dbo.HierPaths with ( tablock ) ( iRootPointId, hPath )

            select data.iMaxRootPointId + data.num, hierarchyid::Parse ( paths.hPath.ToString() + cast ( data.iMaxRootPointId + data.num as nvarchar ( 100 ) ) + N'/' )

            from

            (

                select data.iRootPointId, data.iMaxRootPointId, row_number () over ( order by data.iRootPointId ) num

                from

                (

                    select iRootPointId, max ( iRootPointId ) over ( order by iLevel ) iMaxRootPointId

                    from dbo.HierPaths

                    where iLevel = @CurLvl

                        union all

                    select iRootPointId, max ( iRootPointId ) over ( order by iLevel ) iMaxRootPointId

                    from dbo.HierPaths

                    where iLevel = @CurLvl

                ) data

            ) data

                inner join

            dbo.HierPaths paths on data.iRootPointId = paths.iRootPointId

    end

    set @CurLvl += 1

end

Для создания дочерних узлов можно использовать метод GetDescendant, однако при массовой загрузке удобнее использовать статический метод Parse, поскольку можно самостоятельно быстро определять идентификаторы и родителей. Конечно, за счет избыточности код сгенерировал больший объем данных. Размер таблицы с индексами составил 27 Гб. И на моем домашнем ноутбуке работал очень долго, целые сутки. Теперь в следующих процедурах можно посмотреть как осуществляется поиск родителей и поддеревьев:

create proc dbo.GetParentPaths

(

    @iRootPointId int

)

as

begin

    declare @hier hierarchyid =

    (

        select hPath

        from dbo.HierPaths with ( nolock )

        where iRootPointId = @iRootPointId

    )

    ;

    with Data

    as

    (

        select @hier.GetAncestor ( 0 ) hier, @hier.GetAncestor ( 0 ).GetLevel() iLevel, 0 RecLevel

            union all

        select @hier.GetAncestor ( RecLevel + 1 ), @hier.GetAncestor ( RecLevel + 1 ).GetLevel(), RecLevel + 1

        from Data

        where iLevel > 0

    )

    select paths.iRootPointId, Data.iLevel, hier.ToString () hPathStr

    from

        Data

            inner join

        dbo.HierPaths paths with ( nolock ) on Data.hier = paths.hPath

    where Data.iLevel > 0

    order by paths.hPath

end

go

create proc dbo.GetChildPaths

(

    @iRootPointId int

    @IsParentIncl bit = 0

)

as

begin

    set nocount, xact_abort on

    if @IsParentIncl = 1

    begin

        select child.iRootPointId, child.hPath, child.hPath.ToString(), child.iLevel

        from

            dbo.HierPaths roots with ( nolock )

                inner join

            dbo.HierPaths child with ( nolock ) on

                roots.iRootPointId = @iRootPointId and

                child.hPath.IsDescendantOf ( roots.hPath ) = 1

    end

    else

    begin

         select child.iRootPointId, child.iLevel

         from

             dbo.HierPaths roots with ( nolock )

                 inner join

             dbo.HierPaths child with ( nolock ) on

                 roots.iRootPointId = @iRootPointId and

                 child.hPath.IsDescendantOf ( roots.hPath ) = 1

    end

end

go

Для поиска родителей просто применяется в цикле метод GetAncestor. А для поиска поддерева применяется метод IsDescendantOf. Поэтому видно что поиск поддерева более простой и элегантный. Протестируем теперь скорость работы процедур. Процедуры для поиска цепочки родителей работают одинаково быстро, тут ничего сложного нет. Рассмотрим работу процедур для поиска поддерева. В случае, если глубина искомого поддерева невелика, то обе процедуры dbo.GetChildPoints и dbo.GetChildPaths работают одинаково быстро. А вот если глубина поддерева становится больше 10, то dbo.GetChildPoints начинает заметно отставать. Это выполняется при условии, что данные для dbo.GetChildPaths есть в буферном пуле. Например, такой код: exec dbo.GetChildPaths 20 ищет поддерево из 21 уровня. Тесты я проводил на домашнем компьютере с одним 4-х ядерным процессором и 6-ю Гб памяти. В первый раз код отрабатывает за примерно за полторы минуты. А вот в последующие разы код работает в 2 раза быстрее, 43 сек. Процедура dbo.GetChildPoints при этом параметре всегда работает более полутора минут.
Таким образом если у вас часто выполняются одни и те же запросы на поиск достаточно глубоких поддеревьев, на жестких дисках достаточно места, то использование CLR-типа данных hierarchyid обеспечивает более высокую производительность чем рекурсия.