Для меня всегда было загадкой почему так сложно найти информацию по построению деревьев в плоских таблицах и оперированию ими в SQL. Эти "тайные знания" наверное передаются из поколения в поколение не будучи задокументироваными. Поэтому я решил описать что известно мне и приглашаю аксакалов править и дополнять.
Способ первый.
Наверное известный всем как ParentId column.
Добавляем в таблицу одну колонку, ParentID в которую записываем ID родителя. Для корневых элементов пишем туда NULL, или свой собственный ID (ParentID=ID). Я предпочитаю второй метод.
Преимущества: минимальная избыточность, +1 поле
Недостатки: для того что бы на стандартном SQL сделать выборку поддерева, а не только child, надо писать цикл. Это очень медленно. Некоторые базы предлагают иерархические запросы, но насколько я понимаю это тот же цикл но спрятаный и слегка может быть оптимизированый.
Способ второй: взят из книги Celko.
http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=133465
В таблицу добавляем 2 поля, LeftNode, RightNode.
LeftNode содержит ID , RightNode ID - последнего потомка.
Выборка поддерева
Code: Select all
select * from MyObjects
where LeftNode>=@id and Rightnode>=@id
Преимущества: легкая выборка поддерева.
Недостатки: при insert надо сделать
update MyObjects set RightNode=RightNode+1 where id>=@insertedID, то есть среднестатистически проапдейтить половину записей в таблице на одну вставку.
И метод третий, мой фаворит. Источник мне неизвестен, увидел на одном крупном проекте а потом и использовал сам.
Допустим у нас иерархия
Code: Select all
a->b->c
|->d
Создаем дополнительную таблицу
Code: Select all
create table MyObject(id, Name, <other columns here>)
create table TreeStructure(ObjectId, ParentId, Level int)
insert into MyObject values(1, 'a')
insert into MyObject values(2, 'b')
insert into MyObject values(3, 'c')
insert into MyObject values(4, 'd')
insert into TreeStructure values(1,1,0) --a
insert into TreeStructure values(2,2,0) --b
insert into TreeStructure values(2,1,1) --b
insert into TreeStructure values(3,3,0) --c
insert into TreeStructure values(3,2,1) --c
insert into TreeStructure values(3,1,2) --c
insert into TreeStructure values(4,4,0) --d
insert into TreeStructure values(4,2,1) --d
insert into TreeStructure values(4,1,2) --d
Как видим иерархия вынесена в отдельнцю таблицу
Для каждого объекта в дополнительной таблице есть столько записей сколько у объекта предков.
Выборка поддерева
Code: Select all
select o.*
from TreeStructure ts
join MyObject o ON o.id=ts.ObjectId
where ts.ParentID=@id
Недостатки: некоторая избыточность, отдельная таблица с 2-мя полями (поле Level не является необходимым)
Несколько более сложный Insert, нужно вставить столько записей сколько предков у объекта.
Преимущества:
Возможность делать выборки с ограниченой по уровню вложеностью (AND Level<=@levels)
Пожалуй этот вариант дает самые гибкие возможности при постоении хитрых выборок. Так как дополнительная таблица содержит только коротикие колонки, обычно типа INT, то она очень быстрая а индексы не очень большие.
Возможность выбрать цепочку предков
Code: Select all
select o.Name
from TreeStructure ts
join MyObject o on o.id=ts.ParentID
where ts.ObjectID=@id
order by ts.Level
Выборка объектов не имеющих потомков (leaf)
Code: Select all
select
from TreeStructure ts
where not exists (
select *
from TreeStructure childs
where childs.ParentID=ts.ObjectID
)
Если известны иные способы, дополняйте!
- а способы, они от задачи зависят.
)
