powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Дерево. Большое и сложное. Как?
11 сообщений из 11, страница 1 из 1
Дерево. Большое и сложное. Как?
    #32049286
Lesorub
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Нужно выбрать в таблицу упорядоченное дерево из таблиц с данными.
Данные представлены так:

"Родительский номер" | "Свой номер"

Надо получить такое:

"Уровень" | "Свой номер"

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

Уров | номер
0001 | 1243123252345
0002 | 2343342602834
0002 | 2356223904745
0003 | 1357000478453
0002 | 2343495872457
0001 | 2343495872457
0001 | 2343495872200
0002 | 2324564560896
0003 | 2343000763447
0004 | 2343243472457
0004 | 2345788211122
0002 | 2343495874557

Думаю понятно. Таблица с данными большая (пол миллиона записей) результат может достигать 30 уровней вложенности и 200-250 тыс строк. Ркурсивной функцией. если проходить по каждому элементу получается очень долго. Может кто предложит другой алгоритм.
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049293
Tulkin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Классическая реализация деревьев, при которой в таблице хранится ID родителя, имеет ряд существенных недостатков, в числе которых и один самый существенный - невозможность ‘раскрутить’ дерево в одном запросе. Схема Joe Celko также имеет ряд ограничений (например, сложности с изменением родителя у какой-либо ветки среднего уровня). Предлагаемый мной механизм лишен этого, а также многих других недостатков, хотя требует дополнительного места в БД. Основой механизма является таблица следующей структуры (пример дерева отделов-Departments):



Таблица TreeDepartments

Название поля/Назначение/Ключ/индекс

DepID/Идентификатор/Форейн на Departments&Первичный ключ + кластерный индекс

ParentDep/ Идентификатор родителя / Форейн на Departments
Level/ Уровень относительно корня

ParentLevel/ Уровень родителя относительно корня




Т.е. в этой таблице описываются все родственные отношения в дереве. Таким образом, для того, чтобы получить набор записей, содержащий фрагмент дерева, подчиненный какому-либо ID, достаточно выбрать из таблицы TreeDepartments все записи с ParentDep, равным этому ID. Для того, чтобы получить всех детей первого уровня достаточно добавить условие Level = ParentLevel+1. В принципе, при такой организации дерева просто реализовываются практически любые фантазии относительно получения фрагментов дерева или информации о родителях.

Недостатком такой организации является необходимость ее поддержки, т.е. содержание данных таблицы TreeDepartments в актуальном состоянии. Один из вариантов – реализация на триггерах таблицы Departments. Т.е. при изменении данных в таблице Departments, добавляются/удаляются соответствующие записи в таблице TreeDepartments.

Ниже приводится рабочий скрипт, который на базе существующей таблицы Departments создаст вышеописанные таблицы и триггера, а также инициализирует таблицу, заполнив ее на основании существующих данных. Единственным условием является Null в поле ParentDep у всех ROOTов таблицы Departments. Триггера выполняют все необходимые действия для того, чтобы работа с деревом была абсолютно прозрачной. Триггер на добавление вставляет необходимый набор записей в таблицу Departments, ориентируясь по ParentDep всавленных записей, триггер на удаление соответственно удаляет все неактуальные записи из TreeDepartments, а триггер на обновление меняет родителей в TreeDepartments.


Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
[/src]
print 'Creating table TreeDepartments... '

go

create table TreeDepartments

(

DepID smallint not null,

ParentDep smallint default( 0 ), 

Level smallint default( 0 ),

ParentLevel smallint default( 0 ),

constraint pkTreeDepartments primary key clustered (DepID,ParentDep), 

constraint fkTreeDepartments foreign key (DepID) references Departments, 

constraint fkTreeDepartmentParent foreign key (ParentDep) references Departments

)

go

print 'Creating tr_TreeDepartmentsIns'

go

if exists (select * from sysobjects where name = 'tr_TreeDepartmentsIns')

drop trigger tr_TreeDepartmentsIns

go

create trigger tr_TreeDepartmentsIns on Departments FOR INSERT

as

begin

declare @e int,@level int,@DepID int,@Parent int

 /*Принятие решения об использовании курсора сделано во избежание использования подзапроса на таблицу    TreeDepartments для выяснения собственного уровня (заменено @@rowcownt )*/ 

declare tr cursor local fast_forward for

select DepID,ParentDep from inserted 

open tr

while ( 1 = 1 )

   begin

        fetch tr into @DepID,@Parent

        if (@@fetch_status<> 0 ) break

        select @DepID a ,r.ParentDep b , 0  c ,r.ParentLevel d into #t

        from TreeDepartments r 

        where r.DepID=@Parent and @DepID<>r.DepID and r.DepID<>r.Parentdep

 

        select @level=@@rowcount,@e = @@error 

    

        insert into TreeDepartments (DepID,ParentDep,Level,ParentLevel)

        select a,b,@level+ 1 ,d from #t 

    

        if (@e !=  0 )

            begin

                deallocate tr

                rollback 

                tran raiserror ('tr_TreeDepartmentsIns: Вставка родственных связей',  16 , - 1 ) 

                return 

            end    

    

        insert into TreeDepartments (DepID,ParentDep,Level,ParentLevel)

        Values(@DepID,@Parent,@Level+ 1 ,@Level)

        if (@@error !=  0 )

            begin

                deallocate tr

                rollback tran 

                raiserror ('tr_TreeDepartmentsIns: Вставка родственных связей',  16 , - 1 ) 

                return 

            end

  end

Close tr

deallocate tr

end

go

 

print 'Creating tr_TreeDepartmentsDel'

go

if exists (select * from sysobjects where name = 'tr_TreeDepartmentsDel')

drop trigger tr_TreeDepartmentsDel

go

create trigger tr_TreeDepartmentsDel on Departments INSTEAD OF Delete as

begin

    If exists (select top  1  * from deleted d inner join TreeDepartments r on d.DepID=r.ParentDep)

        begin 

            rollback tran 

            raiserror ('tr_TreeDepartmentsDel: Нарушение целосности ',  16 , - 1 ) 

            return 

        end

    delete t from deleted d inner join TreeDepartments t on d.DepID=t.DepID

    if (@@error !=  0 )

        begin

            deallocate tr

            rollback tran 

            raiserror ('tr_TreeDepartmentsDel: Удаление родственных связей',  16 , - 1 ) 

            return 

        end

    delete t from deleted d inner join Departments t on d.DepID=t.DepID

    if (@@error !=  0 )

        begin

            deallocate tr

            rollback tran 

            raiserror ('tr_TreeDepartmentsDel: Удаление родственных связей',  16 , - 1 ) 

            return 

        end

end

go

 

print 'Creating tr_TreeDepartmentsUpd'

go

if exists (select * from sysobjects where name = 'tr_TreeDepartmentsUpd')

drop trigger tr_TreeDepartmentsUpd

go

 

create trigger tr_TreeDepartmentsUpd on Departments FOR Update  as

begin

IF UPDATE(ParentDep) 

    begin

    If exists (select top  1  * from deleted d inner join TreeDepartments r on d.DepID=r.ParentDep)

        begin 

            rollback tran 

            raiserror ('tr_TreeDepartmentsUpd: Нарушение целосности ',  16 , - 1 ) 

            return 

        end

    delete t from deleted d inner join TreeDepartments t on d.DepID=t.DepID 

    if (@@error !=  0 )

    begin

        deallocate tr

        rollback tran 

        raiserror ('tr_TreeDepartmentsUpd: Удаление родственных связей',  16 , - 1 ) 

        return 

    end

 

    declare @e int,@level int,@DepID int,@Parent int

    declare tr cursor local fast_forward for

    select DepID,ParentDep from inserted

    open tr

    while ( 1 = 1 )

    begin

        fetch tr into @DepID,@Parent

        if (@@fetch_status<> 0 ) break

        select @DepID a ,r.ParentDep b , 0  c ,r.ParentLevel d into #t

        from TreeDepartments r

        where r.DepID=@Parent and @DepID<>r.DepID and r.DepID<>r.Parentdep

 

        select @level=@@rowcount,@e = @@error

 

        insert into TreeDepartments (DepID,ParentDep,Level,ParentLevel)

 

        select a,b,@level+ 1 ,d from #t 

    

        if (@e !=  0 )

        begin

        deallocate tr

        rollback tran 

        raiserror ('tr_TreeDepartmentsIns: Вставка родственных связей',  16 , - 1 ) 

        return 

        end

        insert into TreeDepartments (DepID,ParentDep,Level,ParentLevel)

        Values(@DepID,@Parent,@Level+ 1 ,@Level)

 

        if (@e !=  0 )

        begin

        deallocate tr

        rollback tran 

        raiserror ('tr_TreeDepartmentsIns: Вставка родственных связей',  16 , - 1 ) 

        return 

        end

    end

    Close tr

    deallocate tr

    end

end

go

 /*Инициализируем таблицу TreeDepartments */ 

insert into TreeDepartments(DepID,ParentDep,Level,ParentLevel)

select DepID,DepID, 0 , 0  from Departments where ParentDep is Null

 

declare @rc int,@c int,@c1 int

select @rc= 1 ,@c= 1 

 

while @rc> 0 

    begin

    select @c1= 1 

 

    insert into TreeDepartments(DepID,ParentDep,Level,ParentLevel)

    select d.DepID,d.ParentDep,@c,@c- 1  

    from TreeDepartments t inner join Departments d

        on t.DepID=d.ParentDep and t.Level=@c- 1  and d.DepID<>d.ParentDep

 

    select @rc=@@Rowcount

    while @c1<=@c

        begin

 

        insert into TreeDepartments(DepID,ParentDep,Level,ParentLevel)

        select t.DepID,d.ParentDep,t.Level,d.ParentLevel 

        from TreeDepartments t inner join TreeDepartments d

            on d.DepID=t.ParentDep and  t.level=@c- 1  and d.ParentLevel=@c1- 1   

            where t.DepID<>t.ParentDep and not exists

            (select * from TreeDepartments t1 where t1.DepID=t.DepID

            and t1.ParentDep=d.ParentDep)

 

 

        select @rc=@rc+@@Rowcount

        select @c1=@c1+ 1 

    end

    select @c=@c+ 1 

end

 

[src]
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049297
Lesorub
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Все просто класно описано. Спасибо. Есть только один проблемс. Таблицы с хранимыми данными. Нам дают как есть. Делать с ними я ничего не могу. Надо выбирать из существующей. :(

В этом то вся и проблема.
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049298
Фотография ВладимирМ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Посмотри ответ SergSuper от 24 июля 2002 11:29\r
\r
/topic/10197
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049301
Tulkin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Так исходная таблица абсолютно не меняется. Просто добавляется еще одна.
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049306
Фотография alexeyvg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2Tulkin
Эта схема замечательная, и не тяжёлая для сервера, однако в ней есть большой недостаток - не обеспечивается необходимая сортировка. Если в доп. таблице держать и её, то тогда обновление станет проблемой.

2Lesorub
Ещё год назад здесь был предложен достаточно эффективный метод запроса поддерева:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
CREATE FUNCTION dbo.CT_GetTreeSort(@root int)
RETURNS @tree TABLE (id int, parent_id int, [level] int, [order] varchar( 2000 ))
AS
BEGIN
	declare @level int set @level =  0 

	insert @tree (id, parent_id, [level], [order])
	select @root, null, @level, ''

	while  1  =  1 
	begin
		insert @tree (id, parent_id, [level], [order])
		select	tr.ID, tr.ParentID, @level +  1 , t.[order] + '::' + tr.Name + convert(varchar, tr.ID)
		from tblCatalogGroup as tr
			join @tree as t on t.id = tr.ParentID and t.level = @level

		if @@rowcount =  0  break
		
		select @level = @level +  1 
	end

	return
END
GO
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049309
Tulkin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2 alexeyvg
А что ты понимаешь под обеспечением необходимой сортировки?
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049351
Фотография alexeyvg
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
2Tulkin
Вывод дерева в том порядке, в котором он виден на экране. Это актуально, например, для веб-приложений - можно из рекордсета тупо генерить хэ-тэ-мэ-эль; например:

исходное дерево:
ID ParentID level name
1 null 0 Rasha
2 1 1 Piter
3 1 1 Moscow
4 1 1 Xabarovsk
5 3 2 Tverskaya
6 3 2 Leninskyi

Вывод с сортировкой:
ID ParentID level name
1 null 0 Rasha
3 1 1 Moscow
5 3 2 Tverskaya
6 3 2 Leninskyi
2 1 1 Piter
4 1 1 Xabarovsk
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049382
Lesorub
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Все варианты которые я смотрел - довольно не плохие. У меня у самого есть 2 работающих варианта - один шустро но нет структуры (выбирет все варианты которые с ним связаны) и медленный - рекурсивный. Зато строит красивое дерево и все что надо учитывает.

Проблема еще заключается в том что из полученных данных придется уитавать возможность отбрасывания НЕ ПОСЛЕДНИХ элементов. последние элементы могут быть на любом уровне и в любом порядке.

Мне кажется что ни один вариант пока из мною просмотренных не дает возможности сделать такой анализ без дополнительного запроса по каждому элементу на принадлежность его к КОНЦУ (запрос узнает есть ли такой номер в родительском поле.)
...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32049648
amarat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
сделать это можно так - с использованием временной таблицы.

здесь TABLENAME - таблица из которой необходимо сделать выборку. структура таблицы
ID int
OwnerID int

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
		
		create table #t_Tree
		(
		        ID int,
		        OwnerID int,
		        NeedToAddChilds bit,
		        TreeLevel int
		)
		create table #t_TreeChilds
		(
		        ID int,
		        OwnerID int,
		        NeedToAddChilds bit,
		        TreeLevel int
		)

		declare @TotalTreeRecCount int
		select 
		        @TotalTreeRecCount = count(*)
		from 
			TABLENAME tr

		 /*=======================================================*/ 
		declare crTreeItems scroll cursor for select ID, OwnerID, NeedToAddChilds  from #t_Tree
		declare @ProcessedRecCount int
		declare @ID int
		declare @OwnerID int
		declare @NeedToAddChilds bit
		declare @OldLevel int
		declare @CurrentLevel int
		insert 
		        into #t_Tree
				(ID,
				OwnerID,
				NeedToAddChilds,
				TreeLevel)
			select 
			        tr.ID, 
			        tr.OwnerID, 
		        	 1  as NeedToAddChilds, 
			         0  as TreeLevel
			from 
				 TABLENAME tr
			where 
				(tr.OwnerID is null)
			order by
				tr.Name

		 /*=======================================================*/ 
		set @ProcessedRecCount =  0 
		set @CurrentLevel =  0 
		while @ProcessedRecCount <> @TotalTreeRecCount
	        begin
	                open crTreeItems
	                set @CurrentLevel = @CurrentLevel +  1 
	                fetch first from crTreeItems into @ID, @OwnerID, @NeedToAddChilds
	                delete from #t_TreeChilds
	                while @@fetch_status =  0 
                        begin
				select @OldLevel = TreeLevel from #t_Tree tr where tr.ID = @ID
	                        insert into #t_TreeChilds(ID, OwnerID, NeedToAddChilds, TreeLevel) values(@ID, @OwnerID,  0 , @OldLevel)
	                        if(@NeedToAddChilds =  1 )
	                        begin	
	                        	insert into #t_TreeChilds(ID, OwnerID, NeedToAddChilds, TreeLevel) select tr.ID, tr.OwnerID,  1  as NeedToAddChilds, @CurrentLevel as TreeLevel from TABLENAME tr where (tr.OwnerID = @ID) order by tr.Name
					set @ProcessedRecCount = @ProcessedRecCount +  1 
				end
				fetch next from crTreeItems into @ID, @OwnerID, @NeedToAddChilds

			end
			delete from #t_Tree
			insert into #t_Tree(ID, OwnerID, NeedToAddChilds, TreeLevel) select ID, OwnerID, NeedToAddChilds, TreeLevel from #t_TreeChilds
			close crTreeItems
		end 

		 /*=======================================================*/ 
		select
			tr1.TreeLevel,
		        tr2.ID,
			tr2.OwnerID
		from
		        #t_Tree tr1  
		join 
			TABLENAME tr2 on (tr2.ID = tr1.ID)



		deallocate crTreeItems
		drop table #t_Tree
		drop table #t_TreeChilds

...
Рейтинг: 0 / 0
Дерево. Большое и сложное. Как?
    #32050854
Фотография Гнездин Петр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Предложу еще один вариант с сортировкой:
http://www.pwr.ru/items/?id=3
...
Рейтинг: 0 / 0
11 сообщений из 11, страница 1 из 1
Форумы / Microsoft SQL Server [игнор отключен] [закрыт для гостей] / Дерево. Большое и сложное. Как?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]