Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 деревья. как бы заменить рекурсию  [new]
НожФрауМюллер
Guest 		есть таблица в которой хранится дерево в виде:

[id pk, id_parent fk, p, l], где id, id_parent тут все понятно, p - путь от корня до вершины id (чтобы выделять поддеревья по like...), l уровень вложенности вершины id. В дереве не много элементов не думаю даже в перспективе будет больше 100. Сейчас можно встретить максимум 32.

Нужно: обходить дерево сверху вниз по ярусам. И сравнивать коэффициенты приписанные потомкам с коэффициентами соответствующего предка и считать всякие штуки...

+ гавнакод

drop table #tree;

create table #tree(id int, id_parent int, p varchar(100), l int);
go

create unique index uix_id on #tree(id) include (id_parent);
go

create index ix_id_parent on #tree(id_parent) include(id);
go

insert into #tree(id, id_parent, p, l)
values
(2097,	NULL, '/', 0),
(2098,	NULL, '/', 0),
(2100,	NULL, '/', 0),
(2104,	NULL, '/', 0),
(2116,	NULL, '/', 0),
(2121,	NULL, '/', 0),
(2122,	NULL, '/', 0),
(2124,	NULL, '/', 0),
(2138,	NULL, '/', 0),
(2139,	NULL, '/', 0),
(2140,	NULL, '/', 0),
(2141,	NULL, '/', 0),
(2142,	NULL, '/', 0),
(2143,	NULL, '/', 0),
(2144,	NULL, '/', 0),
(2145,	NULL, '/', 0),
(2146,	NULL, '/', 0),
(2147,	NULL, '/', 0),
(2148,	NULL, '/', 0),
(2149,	NULL, '/', 0),
(2150,	NULL, '/', 0),
(2151,	NULL, '/', 0),
(2152,	NULL, '/', 0),
(2153,	NULL, '/', 0),
(2154,	NULL, '/', 0),
(2168,	NULL, '/', 0),
(2170,	NULL, '/', 0),
(2190,	NULL, '/', 0),
(2191,	NULL, '/', 0),
(2176,	2116, '/2116', 1),
(2171,	2176, '/2176', 1)
go

set statistics io on;

with t0 as
(
	select
		id,
		id_parent
	from
		#tree
	where
		id_parent is null

		union all

	select
		t1.id,
		t0.id_parent
	from
		#tree t1
			inner join
		t0 on t1.id_parent = t0.id
)
select *
from t0

set statistics io off;




очень много чтений :(

Table '#tree__00000000000A'. Scan count 32, logical reads 64, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 2, logical reads 131, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.


Все бы ничего, но метод вызывается часто (вышележащая логика). 855 вызовов в 15 секунд. Он использует рекурсию, много чтений. можно ли уменьшить чтений? Нельзя ли как-то на основе колонки p сделать нерекурсивный обход сверху вниз - в голову запрос из #tree с сортировкой по p + '/' + cast(id as varchar(100)). И идем нот первой к последней, но надо делать некий аналог стека :(
20 дек 13, 20:51    [15325719]     Ответить | Цитировать Сообщить модератору
 Re: деревья. как бы заменить рекурсию  [new]
Crimean
Member

Откуда:
Сообщений: 13147
 		а меняется это дерево часто? если нет - может посмотреть в сторону хранения всей иерархии сбоку?
20 дек 13, 22:27    [15326070]     Ответить | Цитировать Сообщить модератору
 Re: деревья. как бы заменить рекурсию  [new]
НожФрауМюллер
Guest 		Crimean,

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

пока что смотрю в сторону такого вот выкрутаса:

set statistics io on;

declare
	@n varchar(max) = '';

select @n += '@' + p
from
	#tree
order by p-- + iif(p = '/', '', '/') + cast(id as varchar(100))

print @n

set statistics io off;


этот "цикл" посещает ярусы правильно. по крайней мере с этим можно что-то делать и привлекает количество чтений.
нужно только какой-то массив в котором будет "стек", чтобы восстанавливать коэффициенты парентов... :( как бы его замутить.

Table '#tree___00000000000A'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.


т. е. цикл пробегается сверху вниз по вот такому дереву. вершины отсортированы по p:

idid_parentplvl
1null/10
21/1/21
42/1/2/42
52/1/2/52
62/1/2/62
31/1/31
73/1/3/72


при пробежке по строкам при увеличении l запихиваем в "стек" коэффициенты парента, или вытаскиваем из стека при уменьшении l. может стеком сделать строковую переменную :(. также известно что уровень вложенности не вырастет больше 25. может впилить 25 переменных. кто что думает?
21 дек 13, 08:52    [15326943]     Ответить | Цитировать Сообщить модератору
 Re: деревья. как бы заменить рекурсию  [new]
Mnior
Member

Откуда: Кишинёв
Сообщений: 6723
 		HierarchyID
23 дек 13, 03:17    [15331694]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить