Обход дерева
Одно из решений было предложено Joe Celko (см. ). Он рекомендовал добавить в таблицу два дополнительных целочисленных поля: Left и Right, в которые заносятся результаты обхода дерева, начиная с корня. Обход организуется следующим образом: каждый раз, при прохождении какого-нибудь элемента указателем, счетчик увеличивается на единицу; при попадании в терминальный элемент, указатель возвращается в родителя и ищет следующего ребенка. В поле Left записывается значение счетчика при первом прохождении элемента, а в поле Right - при последнем. При таком варианте, наша таблица подразделений выглядела бы следующим образом:
create table Departments ( Id int not null identity primary key, Parent int not null references Departments(Id), Name varchar(32) not null, Left int not null, Right int not null )
| Departments | ||||
| Id | Parent | Name | Left | Right |
| 1 | 0 | A1 | 1 | 11 |
| 2 | 1 | B1 | 2 | 4 |
| 3 | 1 | B2 | 6 | 10 |
| 4 | 2 | C1 | 3 | 3 |
| 5 | 3 | C2 | 7 | 7 |
| 6 | 3 | C3 | 9 | 9 |
Комбинируя эти поля и сравнивая их с такими же полями других элементов, такая схема позволяет получить ответы на все поставленные вопросы.
Терминальные элементы заметно сразу - у них Left = Right.
Отношения предок - потомок вычисляются тоже легко: Left потомка всегда больше чем у предка, а Right - меньше.
Информацию об уровне заданного элемента можно узнать, получив количество его предков.
Количество потомков = (Right - Left) / 2.
Главный недостаток этого решения в том, что при изменении в структуре дерева, приходится заново пересчитывать значения полей Left и Right во всей таблице. То есть, такой способ годится только для небольших, редко изменяемых таблиц.
