Фиксированное дерево
Для того чтобы устранить недостатки простого дерева, нужно иметь указатель не только на непосредственного предка, но и на всех остальных предков выше по иерархии. Если максимальная глубина дерева ограничена, то это можно сделать в той же самой таблице путем введения дополнительных полей-ссылок. Если еще добавить поле для хранения уровня узла (что поможет в реализации операций с деревом), то получим следующую структуру (в данном случае максимальная глубина дерева равна 5):
Таблица MainTable
ID | Autoincrement | Первичный ключ |
Lev | Integer | Уровень текущего узла |
Parent1 | Integer | Ссылка на родителя 1-го уровня (корень) |
Parent2 | Integer | Ссылка на родителя 2-го уровня |
Parent3 | Integer | Ссылка на родителя 3-го уровня |
Parent4 | Integer | Ссылка на родителя 4-го уровня |
Parent5 | Integer | Ссылка на родителя 5-го уровня |
Name | Char | Название узла |
Поле Lev может принимать значения от 1 (корень дерева) до 5 (узел максимально возможной глубины). Значение поля ParentN для любого N равно:
- значению первичного ключа предка уровня N (при N < Lev);
- значению первичного ключа текущего узла (при N = Lev);
- 0 (при N > Lev).
Как видно из приведенных примеров, в реализации всех операций удалось уйти от рекурсии. Количество запросов не зависит ни от количества узлов в дереве, ни от его глубины. Да и сама реализация стала несколько проще за исключением процедуры SetParent. На самом деле в ней не так все страшно, как кажется. Просто я попытался в одну процедуру запихнуть обработку нескольких различных ситуаций, которые, по уму, должны обрабатываться самостоятельно. На всякий случай (если кому-то сложно разбирать мои паскалевские каракули) хочу привести примеры запросов, которые реализуют эту операцию для различных ситуаций (запросы не сработают на Local SQL).
Ситуация 1. При изменении родителя происходит уменьшение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 1. В результате выполнения операции уровень всех узлов поддерева Node уменьшится на 1. UPDATE MainTable AS T1,MainTable AS T2 SET T1.Lev=T1.Lev-1,T1.Parent1=T2.Parent1,T1.Parent2=T1.Parent3, T1.Parent3=T1.Parent4,T1.Parent4=T1.Parent5,T1.Parent5=0 WHERE (T1.Parent3=Node) AND (T2.ID=Parent);
Ситуация 2. При изменении родителя происходит увеличение уровня узла. Пусть мы узлу Node уровня 2 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node увеличится на 1. Если в поддереве узла Node имеются узлы уровня 5, то они должны быть предварительно удалены, так как выйдут за пределы допустимой глубины дерева. DELETE FROM MainTable WHERE (Parent2=Node) AND (Lev>=5); UPDATE MainTable AS T1,MainTable AS T2 SET T1.Parent5=T1.Parent4,T1.Parent4=T1.Parent3,T1.Parent3=T1.Parent2, T1.Parent2=T2.Parent2,T1.Parent1=T2.Parent1,T1.Lev=T1.Lev+1 WHERE (T1.Parent2=Node) AND (T2.ID=Parent);
Ситуация 3. При изменении родителя не происходит изменение уровня узла. Пусть мы узлу Node уровня 3 назначаем родителем узел Parent уровня 2. В результате выполнения операции уровень всех узлов поддерева Node не меняется. UPDATE MainTable AS T1,MainTable AS T2 SET T1.Parent1=T2.Parent1,T1.Parent2=T2.Parent2 WHERE (T1.Parent2=Node) AND (T2.ID=Parent);
Кстати, фиксированное дерево -- единственный вариант представления дерева, для которого мне удалось в полном объеме решить вставшую изначально проблему: вывести все узлы поддерева в нужном порядке одним запросом.