Индекс графа. Часть 1. Логическая архитектура (гипердеревья, фундаментальная группа).

Введение.

Графы представляются весьма занятным математическим объектом. Пожалуй, самая известная задача о графах это поиск маршрутов, соединяющих 2 точки. Первое что приходит в голову, когда думаешь о задаче поиска маршрута между двумя вершинами, это цикл. В этом цикле сначала ищутся все ребра, инцидентные первой вершине. А затем, на каждой итерации выполняется поиск всех ребер, инцидентных ребрам, найденным на предыдущем шаге. При этом надо следить за тем, чтобы не включались ребра, инцидентные уже найденным. Метод простой, однако, рассматривая произвольные графы, с разнообразными циклами и большим числом вершин и ребер, обнаруживается, что метод работает медленно. Это неудивительно, ведь описанный цикл, по сути дела, ищет все маршруты, выходящие из определенной вершины. Это число маршрутов, при обилии ребер, может начать расти с экспоненциальной скоростью относительно числа вершин и тут уж ничто не спасет. Каждый маршрут можно мыслить как упорядоченное подмножество среди всех вершин и число возможных комбинаций может быть факториальным. И даже, если циклов не так много, то при большом числе вершин, поиск станет экспоненциальным. А ведь в ходе работы цикла каждый найденный маршрут надо хранить, поскольку он может оказаться искомым. Таким образом, на хранение этих маршрутов требуется дополнительная память, объем которой также может оказаться огромным, так что даже на жестком диске может не хватить места.

Я долго размышлял о том, как можно оптимизировать поиск маршрутов по аналогии с тем как обычные индексы для таблиц позволяют оптимизировать поисковые запросы. В этой работе я буду рассматривать случай произвольных графов, то есть в них могут быть любые циклы. Будет реализовано 2 алгоритма поиска маршрутов. Первый из них основан на вышеописанных рассуждениях с циклами. Второй будет основан на ином принципе хранения данных. Будет создана новая структура данных, позволяющая индексировать граф и выполнять мгновенные поиски маршрутов. Также будут созданы процедуры, которые позволят быстро выполнять операции вставки и удаления ребер, при которых структура, позволяющая быстро искать маршруты, будет сохраняться. Это показывает, что методика подходит и для работы в многопользовательской среде, в системах OLTP.
После реализации будет создан достаточно большой граф и оба метода будут протестированы на скорость поиска маршрутов между различными парами вершин. Дополнительно будет создана процедура, которая позволит выполнять конвертацию традиционного способа хранения графа (проиллюстрированного на рисунке выше) к оптимизированному, при котором возможен быстрый поиск. Оговорюсь, что мы не будет искать кратчайший путь, а первый попавшийся, который соединяет заданные вершины.
Думаю, что описываемый метод мог бы найти применение при разработке социальных сетей. Поскольку в социальных сетях используются графы для хранения отношений дружбы между людьми. Например, можно было бы ввести опцию: для любых заданных участников быстро определять наличие цепочки участников, соединяющих их, в которой каждые два соседних элемента являются друзьями. Созданная ниже архитектура хранения позволила бы мгновенно находить такие цепочки.


Реализация традиционного способа поиска маршрутов в графе.

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

if object_id ( N'dbo.Edges', N'U' ) is not null

begin

    ; throw 50000, N'Таблица уже существует.', 1

end

create table dbo.Edges

(

    StartId int not null,

    EndId   int not null,

    constraint PK_Edges_StartId primary key clustered ( StartId asc ) on [PRIMARY],

    constraint AK_Edges_EndId unique nonclustered ( EndId asc ) on [PRIMARY],

    constraint CH_Edges check ( StartId < EndId )

) on [PRIMARY]

Теперь создадим хранимую процедуру, которая получает в качестве параметра 2 вершины и выдает список последовательных ребер, которые соединяют вершины. Процедура в точности реализует цикл, который был описан в начале статьи:

if object_id ( N'dbo.RecursiveFindPath', N'P' ) is null

       exec ( N'create proc dbo.RecursiveFindPath as return' )

go

alter proc dbo.RecursiveFindPath

(

       @StartId     int,

       @EndId       int

)

as

begin

       set nocount, xact_abort on

      

       declare @Lev int, @num int, @PathExists bit

      

       if @StartId = @EndId

       begin

             ; throw 50000, N'Вершины не могут совпадать.', 1

             return

       end

      

       if not exists

       (

             select *

             from dbo.Edges

             where StartId = @StartId

       ) and not exists

       (

             select *

             from dbo.Edges

             where EndId = @StartId

       )

       begin

             ; throw 50000, N'Одна из вершин не входит в ребро.', 1

             return

       end

      

       if not exists

       (

             select *

             from dbo.Edges

             where StartId = @EndId

       ) and not exists

       (

             select *

             from dbo.Edges

             where EndId = @EndId

       )

       begin

             ; throw 50000, N'Одна из вершин не входит в ребро.', 1

             return

       end

      

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

             drop table #Paths

       create table #Paths

       (

             StartId int not null,

             EndId  int not null,

             Lev          int not null,

             primary key clustered ( Lev asc, StartId asc, EndId asc ) on [PRIMARY],

             unique nonclustered ( Lev asc, EndId asc, StartId asc ) on [PRIMARY],

             unique nonclustered ( StartId asc, EndId asc ) on [PRIMARY],

             unique nonclustered ( EndId asc, StartId asc ) on [PRIMARY]

       ) on [PRIMARY]

      

       insert into #Paths ( StartId, EndId, Lev )

             select @StartId, EndId, 1

             from dbo.Edges

             where StartId = @StartId

      

       insert into #Paths ( StartId, EndId, Lev )

             select @StartId, StartId, 1

             from dbo.Edges

             where EndId = @StartId

      

       set @PathExists = 1

       set @Lev = 1

       while not exists

       (

             select *

             from #Paths

             where Lev = @Lev and EndId = @EndId

       )

       begin

             set @num = 0

             insert into #Paths ( StartId, EndId, Lev )

                    select min ( front.EndId ), edge.EndId, @Lev + 1

                    from

                           #Paths front

                                  inner join

                           dbo.Edges edge on

                                  front.Lev = @Lev and

                                  front.EndId = edge.StartId

                    where not exists

                           (

                                  select *

                                  from #Paths oldpath

                                  where oldpath.StartId = edge.EndId

                           ) and

                           not exists

                           (

                                  select *

                                  from #Paths oldpath

                                  where oldpath.EndId = edge.EndId

                           )

                    group by edge.EndId

             set @num += @@rowcount

            

             insert into #Paths ( StartId, EndId, Lev )

                    select min ( front.EndId ), edge.StartId, @Lev + 1

                    from

                           #Paths front

                                  inner join

                           dbo.Edges edge on

                                  front.Lev = @Lev and

                                  front.EndId = edge.EndId

                    where not exists

                           (

                                  select *

                                  from #Paths oldpath

                                  where oldpath.StartId = edge.StartId

                           ) and

                           not exists

                           (

                                  select *

                                  from #Paths oldpath

                                  where oldpath.EndId = edge.StartId

                           )

                    group by edge.StartId

             set @num += @@rowcount

             if @num = 0

             begin

                    set @PathExists = 0

                    break

             end

             set @Lev += 1

       end

      

       if @PathExists = 1

       begin

             ;

             with Data

             as

             (

                    select StartId, EndId, Lev

                    from #Paths

                    where Lev = @Lev and EndId = @EndId

                           union all

                    select paths.*

                    from

                           Data

                                  inner join

                           #Paths paths on

                                  paths.Lev = Data.Lev - 1 and

                           paths.EndId = Data.StartId

             )

             select *

             from Data

             order by Lev

             option ( maxrecursion 0 )

       end

end

go

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

В начале делается обработка ошибок: начальная и конечная вершины не должны совпадать. И она должны быть концами ребер. Строго говоря, таблица dbo.Edges не позволяет хранить изолированные вершины. Но несложно создать дополнительную таблицу, которая бы их хранила. Все запросы используют созданные индексы для поиска.

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

Выполним вставку:

insert into dbo.Edges ( StartId, EndId )

    values

        ( 1, 2 ),

        ( 1, 3 ),

        ( 1, 5 ),

        ( 2, 4 ),

        ( 2, 7 ),

        ( 3, 6 ),

        ( 5, 6 ),

        ( 5, 7 ),

        ( 6, 8 ),

        ( 6, 9 ),

        ( 6, 13 ),

        ( 7, 9 ),

        ( 9, 10 ),

        ( 9, 11 ),

        ( 9, 12 ),

        ( 10, 12 ),

        ( 10, 13 ),

        ( 11, 14 ),

        ( 12, 13 ),

        ( 12, 14 )

Продемонстрируем работу процедуры:

exec dbo.RecursiveFindPath 14, 1

Результаты такие:

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

Для генерации графа выполним такой код:

declare @maxLevel int = 18, @curLevel int = 1, @num int

while @curLevel <= @maxLevel

begin

    set @num = power ( 3, @curLevel )

    insert into dbo.Edges with ( tablock ) ( StartId, EndId )

        select

            data.num,

            (

                ( data.num + ( @num - 3 ) / 2 ) - 1

             ) / 3

        from

        (

            select top ( power ( 3, @curLevel ) ) row_number () over ( order by ( select 1 ) ) as num

            from

                master.dbo.spt_values val1

                    cross join

                master.dbo.spt_values val2

                    cross join

                master.dbo.spt_values val3

        ) data

    set @curLevel += 1

end

В этом коде осуществляется последовательное заполнение уровней дерева. Как и всегда для маломощных компьютеров следует использовать хинт tablock, чтобы не исчерпать память при хранении блокировок. Код работал на моем ноутбуке (6 Gb RAM, AMD A10-4600M APU, 4 Cores, Win 7 64 bit) около 12 часов, объем таблицы dbo.Edges вырос до 17 Гб. Приступим к тестированию. При поиске маршрута между вершинами, расстояние между которыми составляет не более 10 ребер, время поиска небольшое. Например, такой запрос на горячем кэше работает 4 секунды:

exec dbo.RecursiveFindPath 3, 15132

Однако, если запустить такой запрос в 10 соединениях:

waitfor time '15:05:00'

select sysdatetime ()

exec dbo.RecursiveFindPath 3, 15132

select sysdatetime ()

, то время работы составляет уже от 8 до 23 сек.

При этом при увеличении числа работающих соединений возрастает расход оперативной памяти. Однако это мелочи по сравнению с поиском маршрута между вершинами, которые отделены друг от друга десятками ребер. Например, я запустил такой код:

exec dbo.FindPath 3, 28000000

Ждал полтора часа, и, не дождавшись результата, отключил. За полтора часа маршрут не был найден, зато объем места на диске уменьшился на 10 Гб, уровень потребления оперативной памяти возрос до 95%, прикасаясь к ноутбуку, я боялся обжечься. Пришлось еще и около часа ждать отката последней вставки, которая выполнялась в процедуре. Когда процедура работала, я выполнил такой запрос, для определения числа записей в локальной временной таблице (#Paths), используемой процедурой:

select *

from tempdb.sys.partitions with ( nolock )

where [object_id] = (

       select top 1 [object_id]

       from tempdb.sys.tables with ( nolock )

       where name like '#Paths%'

)

, получилось что-то вроде нескольких десятков миллионов.

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

Индекс графа. Концепции (фундаментальная группа, гипердерево).

Ускорение поиска маршрутов, которое достигается в рамках описываемого подхода, достигается за счет изменения архитектуры хранения, за счет внесения избыточности. Для примера, описанного выше, оно будет необычайно значительным. Тот маршрут, который не был найден традиционным способом, будет вычислен за 20 миллисекунд в рамках нового подхода, причем одновременно для 10 соединений. Мне хотелось создать архитектуру хранения, напоминающую индексы, которые ускоряют поиск записей в таблицах.
Конечно, когда такая избыточность вносится в данные, встает вопрос о том как ее сохранить при модификации графа, при этом желательно как можно меньшей ценой. Ведь в идеале хочется, чтобы быстро работал поиск, и чтобы при этом была возможность оперативно удалять и добавлять ребра и вершины. Эта проблема долгое время не давала мне покоя, но сейчас, кажется, удалось найти разумный баланс. Итак, приступим к описанию методики.

Французский математик Анри Пуанкаре ввел важное для современной алгебры и топологии понятие фундаментальной группы топологического пространства. На графе также можно ввести простую топологию и описать фундаментальную группу. В ходе этой операции доказывается, что в каждом графе существует максимальное поддерево. Это дерево обязательно содержит все вершины. Таким образом, любой связный граф может быть представлен как дерево, в котором есть дополнительные ребра, соединяющие вершины дерева. Рассмотрим пример:

Теперь становится ясной идея поиска маршрута: если есть две вершины в максимальном поддереве, то путь между ними определяется пересечением путей, которые соединяют вершины с корнем. Эта операция очень быстра. На рисунке ниже показан способ поиска маршрута между вершинами под номерами 11 и 7:

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

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

Если же пользователи выполняют операции удаления или добавления вершин и ребер, то рассмотренного дерева недостаточно. Например, если в примере выше удалить ребро, соединяющее вершины 5 и 6, то у нас вместо одного дерева получится 2 дерева. Возможно, эти деревья соединены внешними ребрами, возможно, что нет.

Может так случиться, что после присоединения к графу очередного ребра произойдет присоединение некоторого поддерева A к другому поддереву B. Причем вершина, по которой происходит соединение с поддеревом B, не является для B корнем. Тогда чтобы из объединения A и B получить новое дерево необходимо переопределить отношения между всеми вершинами. Это значит что потребуется выполнять операции записи для всех вершин в B, число которых может экспоненциально расти относительно числа уровней.

Начнем разбираться с этими вопросами по порядку.

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

Сначала попробуем порассуждать о том, в каком направлении можно двигаться, чтобы осуществить операции удаления/добавления ребер.

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

Предположим нам надо соединить ребром 2 вершины из этих графов:

Как мы выяснили, обновление дерева B с целью изменения корня на новую вершину q является слишком дорогой операцией. Поэтому единое дерево строить не будем. Вместо этого просто будем рассматривать A и B как "вершины". И именно эти вершины (являющиеся деревьями) будут храниться в базе данных. Эти вершины будут вершинами второго уровня. Необходимо хранить данные о ребрах, соединяющих эти вершины, а также вершинах предыдущего уровня, которые инцидентны ребрам, соединяющим вершины нового типа.

Предположим теперь что необходимо удалить ребро максимального поддерева. Пусть q это дочернее ребро. После удаления ребра у нас возникают 2 дерева: исходное и новое дерево с корнем в вершине q:

При этом для хранения нового дерева не нужно выполнять переориентацию его вершин на новый корень q. Ведь это дерево является поддеревом исходного дерева. И для сохранения данных о новом корне достаточно сохранить информацию о том, что q теперь корень. Если в дальнейшем возникнет необходимость для вершины поддерева найти корень, то потребуется просто выполнить цикл по его потомкам на высших уровнях. На каждой итерации надо будет проверять, является ли очередной потомок корнем. И истинным корнем будет первый потомок с признаком корневого элемента.
После удаления ребра мы уже не можем построить маршрут из поддерева в исходное дерево, который бы пролегал в пределах максимального поддерева. Однако может найтись внешнее ребро (то есть то, которое не входило в исходное максимальное поддерево), которое соединяет некоторую вершину исходного дерева с другой вершиной поддерева (на рисунке выше отмечена синим цветом). В результате из вершин поддерева все-таки можно добраться до вершин дерева. Только путь не будет полностью внутри дерева, а будет пролегать через внешнее ребро. Информацию об этом надо сохранить, чтобы можно было строить маршруты. Поскольку изменение корня для поддерева с вершины q на вершину внешнего дерева дорогая операция, то вновь требуется смотреть на дерево и поддерево как на вершины второго уровня, которые соединены внешним ребром. В базе сохраняется информация о наличии новых вершин второго уровня и о ребре, их соединяющем. Также сохраняется информация об исходных вершинах первого уровня, по которым внешнее ребро соединяет дерево и поддерево. В результате нескольких операций удаления и вставки ребер может получиться несколько вершин второго уровня, которые образуют граф. Этот граф не будет содержать циклов, то есть будет дизъюнктным объединением деревьев. Почему? Дело в том, что при соединении ребром двух вновь появившихся вершин второго уровня (когда эти вершины еще являются изолированными) одно из них объявляется корнем. То есть получается дерево из двух вершин и одного ребра. Если затем вершина p какого-то дерева первого уровня соединяется ребром E с вершиной q из дерева второго уровня, то выполняется следующая проверка. Для вершины p ищется ее образ PP на втором уровне, то есть ищется вершина второго уровня, которая образована деревом первого уровня, содержащем p. После этого, используя иерархию родитель-потомок, делается проверка принадлежности вершины PP дереву QQ второго уровня, которое образовано деревом, возникающим из вершины q. Если PP входит в QQ, то уже и так понятно, что можно строить маршруты между вершинами, "входящими" в QQ и теми вершинами, которые входят в деревья, образующие остальную часть дерева. И при добавлении E не требуются дополнительные действия. Если же PP не входит в QQ, то к дереву QQ добавляется новая вершина второго уровня PP (на листовом уровне). В результате, циклов не возникает. Процесс, иллюстрирующий приведенный выше пример показан на рисунке ниже:

Достаточно ли для быстрого выполнения всех операций приведенных выше лесов (то есть дизъюнктного объединения деревьев) первого и второго уровня. Оказывается, нет. Предположим, то в ходе операций удаления и добавления ребер у нас получилось 2 непересекающихся дерева второго уровня: P и Q. И надо соединить ребром 2 вершины первого уровня, которые находятся в разных деревьях второго уровня (P и Q):

Так как P и Q не имеют пересечений, то данные о новом ребре должны прописываться, так как оно дает новые маршруты из вершин, находящихся внутри P в вершины первого уровня Q. Опять-таки вполне может так быть, что концы нового ребро не совпадают с корнями P и Q. А значит, при попытке построения единого дерева второго уровня потребовалось бы выполнять операцию переориентации всех вершин одного из деревьев на новый корень. Чтобы этого избежать необходимо поступить так же как и при построении деревьев второго уровня. То есть деревья второго уровня P и Q сами становятся вершинами третьего уровня. Одно из них объявляется корнем. При этом надо сохранить данные об идентификаторе ребра E, которое соединяет вершины P и Q. Также надо хранить данные о вершинах предыдущего, второго, уровня, в которых лежат концы ребра E. То есть хранить данные о вершинах второго уровня s и w. При повторном выполнении таких операций может появиться несколько непересекающихся деревьев третьего уровня, и число вершин третьего уровня в них может расти. И снова может возникнуть потребность соединить вершиной деревья третьего уровня. И это снова по аналогии с рассмотренными случаями приводит к необходимости создания дерева четвертого уровня. Таким образом уровней теоретически может быть сколько угодно (в зависимости от того насколько интенсивно происходят операции удаления ребер).

Итак, мы поняли как в результате будет выглядеть граф. Он будет представлять собой несколько дизъюнктных деревьев уровня k. Возможно, также будет некоторое количество внешних ребер, которые не будут использоваться до поры до времени (пока не произойдет очередного удаления ребер). При этом вершины в деревьях уровня k являются сами деревьями уровня k-1. А вершины в уровне k-1 являются деревьями уровня k-2. И так далее пока не получим уровень 1, где вершины уже будут истинными вершинами графа. На рисунке ниже приведен пример графа, где максимальный уровень равен 5:

Зная как выглядит граф в общем виде, можно сформулировать точные алгоритмы добавления и удаления ребер, которые были бы достаточно быстрыми и при этом сохраняли бы описанную выше структуру.

Алгоритм добавления ребра:

1. Требуется соединить ребром вершины p и q.
2. Требуется начать процесс поиска образов вершин на высших уровнях деревьев
3. Когда для каждой из вершин процесс пункта 2 останавливается, то для p и q найдены максимальные уровни:  pk и ql
4. Если pk и ql совпадают, и образы p и q на этих уровнях лежат в одном дереве, то надо просто сохранить данные о новом ребре и дальнейшие действия не требуются, так как новое ребро не дает новых знаний о наличии маршрутов.
5. Если pk меньше чем ql, и образ p на уровне pk не лежит в дереве того же уровня, содержащего образ q, то дерево уровня pk для вершины p становится вершиной уровня pk + 1 и присоединяется как новая вершина к дереву уровня pk +  1 для вершины q.
6. Если pk и ql совпадают, но деревья этих уровней для p и q различны, то создается дерево уровня pk + 1 из двух вершин, соответствующих деревьям высших уровней для p и q. Новое ребро соединяет эти вершины уровня pk + 1.

Рисунок ниже демонстрирует алгоритм:

Алгоритм удаления ребер:

1. Предположим, что требуется удалить ребро E, соединяющее вершины p и q.
2. Выполняется поиск дерева минимального уровня, которое содержит образы вершин p и q (для этого в цикле происходит вычисление образов p и q на высших уровнях, на каждой итерации которого проверяется корень текущего дерева для обоих образов).
3. Пусть найдено дерево R уровня k, о котором говорится в пункте 2. В данном дереве образы p и q соединяются ребром.
4. Пусть для определенности образ q является родительским для образа p. Если уровень k является последним, то достаточно обновить образ p, проставив для этой вершины признак корня. В результате, дерево R распадется на 2 дерева: исходное R и новое R1.
5. Если существует ребро уровня k, которое входит в вершину уровня k, принадлежащую поддереву, образованному образом вершины p, то поддерево, образованное образом вершины q (за вычетом поддерева, образованного образом вершины p), будет новой вершиной уровня k + 1. В противном случае, новая вершина уровня k + 1 строится по вершине, являющейся образом вершины p.
6. Итак, у нас два дерева на уровне k. Предположим, что данный уровень не является максимальным. То есть имеется уровень k + 1. Все вершины уровня k + 1, инцидентные вершине R делятся на 2 части. Для всех вершин уровня k + 1, которые являются дочерними для вершины нового поддерева, надо изменить родителя с дерева R на R1. Поддерево можно быстро найти, используя некластерный индекс на поле с идентификатором родительской вершины.
7. После выполнения пунктов 5 и 6 получается, что и дерево уровня k + 1 разбивается на 2 части. Это значит, что надо подняться на уровень k + 2 и повторить пункты 5 и 6 на этом уровне. То есть дерево уровня k + 1, в котором мы из одной вершины сделали 2, само является вершиной уровня k + 2. Поскольку имело место раздвоение вершин в дереве уровня k +1, то это индуцирует раздвоение вершины уровня k +2, являющейся образом дерева, с которым мы работали на уровне k + 1. И нужно повторить процедуру с ребрами из пункта 6.
8. После того как пункты 5 и 6 выполнены на всех уровнях. У нас есть 2 непересекающихся дерева (обозначим их R и T), которые содержат вершины p и q (на первом уровне). Теперь мы не можем построить маршрут из p в q. А что если такой маршрут по-прежнему существует. То есть может найтись внешнее ребро (которое до сих пор не использовалось) которое соединяет вершины из R и T. Поиск такого ребра осуществляется с помощью соединения двух подзапросов, каждый из которых получается с помощью рекурсивных общетабличных выражений, идущих от корней R и T, с использованием оператора cross apply для перехода на низший уровень.
9. Если ребро найдено, то для его концов надо найти образы на том уровне. на котором существуют деревья R и T, и образовать новое дерево следующего уровня, которое состоит из вершин-деревьев R и T.
10. В самом начале алгоритма также необходимо проверить является ли удаляемое ребро внешним и неиспользуемым. И в этом случае его надо просто удалить. Больше ничего не потребуется.

Рисунок ниже описывает процесс удаления ребра:

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

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

1. Требуется найти маршрут между вершинами p и q.
2. Необходимо начать цикл, на каждой итерации которого происходит поиск образов вершин p и q на следующем уровне.
3. Если в цикле из пункта 2 мы оказались на максимальном уровне, то надо проверить лежат ли образы вершин p и q в одном дереве на этом уровне (для этого надо проверить совпадают ли корни для образов p и q). Если деревья различны, то это значит, что граф несвязный и маршрута между p и q нет. Если же дерево одно, то для него надо найти маршрут, идущий из образа p в образ q. в пределах дерева на данном уровне. Этот поиск осуществляется тем же методом, о котором говорилось в начале данной главы.
4. Пусть в пункте 3 найден маршрут между образами p и q на уровне k: e1, e2, ..., en. Теперь надо конвертировать этот маршрут на уровень k - 1. Делается это так. Ребро e1 идет из образа p. Для начала вершины e1 прописана вершина предыдущего уровня, которая соответствует началу ребра e1. Надо взять образ вершины p на уровне k - 1 и образ начала ребра e1 на уровне k - 1. Эти вершины находятся в одном дереве уровня k - 1. Значит можно найти маршрут между ними. Теперь надо для каждого числа i от 1 до n-1 найти маршрут между образом конца ребра e(i-1) на уровне k - 1 и началом ребра ei на уровне k - 1. Эти вершины находятся в одном дереве уровня k - 1. Этот процесс надо осуществлять по всем уровням, пока не дойдем до первого уровня.

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

В следующей части данного цикла работ будет показан пример физической реализации рассмотренного подхода.