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

Откуда: Moscow
Сообщений: 1172
Господа доброго времени.

в пятницу на работе рисовал одно задание, смысл которого иерархическая структура элементов.
на входе имеем массив элементов
<item id="1">
   <item id="2" parent="1"/>
   <item id="3" parent="1">
      <item id="5" parent="3"/>
      <item id="6" parent="3"/>
   </item>
</item>
<item id="20">
    <item id="21" parent="20"/>
    <item id="22" parent="20">
       <item id="23" parent="22"/>
          <item id="24" parent="23"/>
       </item>
    </item>
</item>


необходимо было представить в виде таблицы:
idnamelvl
1root1
2test11.1
3test21.2
4test41.2.1
5test51.2.2
20root22
21test212.1
22test222.2
23test232.2.1
24test242.2.1.1


думаю смысл понятен, собственно в реляционном виде реализация выглядит так (не по той модели что я привел выше но смысл тот же):
declare @t table (
val char,
id int,
parent int
)
insert into @t values ('a', 1, 0), ('b', 2, 1), ('c', 3, 1), ('d', 4, 2), ('e', 5, 2), ('f', 6, 3);
insert into @t values ('i', 7, 0), ('j', 8, 7), ('k', 9, 7), ('l', 10, 9), ('m', 11, 9), ('x', 12, 8);
--select * from @t;

with rcte as (
select val,
       id,
       parent,
       1 as [lvl],
       convert(varchar, row_number() over (order by id)) as [lvl_descr]
from @t
where [parent] = 0
union all
select
      t.val,
      t.id,
      t.parent,
      rcte.[lvl]+1 as [lvl], 
      convert(varchar, rcte.[lvl_descr]+'.'+convert(varchar, row_number() over (partition by t.[parent] order by t.[id]))) as [lvl_descr]
from rcte
    join @t t on t.[parent] = rcte.id
)
select * from rcte 
order by convert(binary(16), lvl_descr) option(maxrecursion 0);
--order by convert(int, left(replace(lvl_descr, '.', '')+'000000', 6)) option(maxrecursion 0);


но вот эта сортировка в конце меня как то напрягает, есть у кого мысли как можно элегантнее нарисовать?

нюанс: необходимо что бы сортировка конечного списка элементов была на стороне сервера, в конечном итоге данные получает fastreport с кучей группировок и порядок строк из набора данных играет ключевую роль что бы со стороны сервера иерархия была сразу предоставлена правильно. так что предложение сортировать на стороне клиента не подойдет :)

это вообщем пятничный вопрос: а можно лучше?
21 июл 18, 00:52    [21590472]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
court
Member

Откуда:
Сообщений: 1956
felix_ff,

а "о чём" вообще эта сортировка ? :)
Зачем этот convert в binary ? чем сортировка по convert-у lvl_descr отличается от сортировки просто по lvl_descr ?

Вы заметили, что на таком,
;with cte as (
	select lvl_descr from 
	(values 
		 ('2')
		,('2.1')
		,('2.2')
		,('2.2.1')
		,('2.2.1.1')
		,('2.2.1.10')
		,('2.2.1.2')
		) as T(lvl_descr))
select * from cte order by convert(binary(16), lvl_descr)  

будет "лажать" и с "конвертом" и без
lvl_descr
2
2.1
2.2
2.2.1
2.2.1.1
2.2.1.10
2.2.1.2


------------------------
как-то так можно, в принципе, решить
declare @x xml =
'<item id="1">
   <item id="2" parent="1"/>
   <item id="3" parent="1">
      <item id="5" parent="3"/>
      <item id="6" parent="3"/>
      <item id="7" parent="3"/>
      <item id="8" parent="3"/>
      <item id="9" parent="3"/>
      <item id="10" parent="3"/>
      <item id="11" parent="3"/>
      <item id="12" parent="3"/>
      <item id="13" parent="3"/>
      <item id="14" parent="3"/>
      <item id="15" parent="3"/>
   </item>
</item>
<item id="20">
    <item id="21" parent="20"/>
    <item id="22" parent="20">
       <item id="23" parent="22">
          <item id="24" parent="23"/>
       </item>
    </item>
</item>'

;with cte as (
select 
	id		=t.c.value('@id','int')
	,parent =t.c.value('@parent','int')
	,x		=t.c.query('item')
	,lvl_descr	=cast(row_number()over(partition by t.c.value('@parent','int') order by t.c.value('@id','int')) as varchar(max))
	,lvl	=1	 
	,orderby=cast(1.0*row_number()over(partition by t.c.value('@parent','int') order by t.c.value('@id','int')) as float)
from @x.nodes('item') as t(c)

union all

select
	id		=a.id
	,parent =a.parent
	,x		=a.x
	,lvl_descr	=a.lvl_descr
	,lvl	=cte.lvl+1 
	,orderby=a.orderby 
from cte
cross apply (select  
				id		=t.c.value('@id','int')
				,parent =t.c.value('@parent','int')
				,x		=t.c.query('item')
				,lvl_descr	=cte.lvl_descr+'.'+cast(row_number()over(partition by t.c.value('@parent','int') order by t.c.value('@id','int')) as varchar(max))
				,orderby=cast(cte.orderby+(row_number()over(partition by t.c.value('@parent','int') order by t.c.value('@id','int'))/power(100.0,cte.lvl)) as float)
			from x.nodes('item') as t(c)) a

)
select 
		id		
		,parent
		,lvl_descr 
		,lvl	
		,orderby
from cte 
order by orderby
option(maxrecursion 0);

idparentlvl_descrlvlorderby
1NULL111
211.121,01
311.221,02
531.2.131,0201
631.2.231,0202
731.2.331,0203
831.2.431,0204
931.2.531,0205
1031.2.631,0206
1131.2.731,0207
1231.2.831,0208
1331.2.931,0209
1431.2.1031,021
1531.2.1131,0211
20NULL212
21202.122,01
22202.222,02
23222.2.132,0201
24232.2.1.142,020101
23 июл 18, 10:58    [21593423]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
felix_ff
Member

Откуда: Moscow
Сообщений: 1172
court,

Опачки, да. я что то до десятки в тестовом варианте не добежал, мой вариант - ни о чем, согласен.

с xml можно было не заморачиваться просто она наглядней структуру отражает, но все равно спасибо.
23 июл 18, 11:56    [21593634]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
invm
Member

Откуда: Москва
Сообщений: 9127
felix_ff
а можно лучше?
Не знаю критериев "лучшести", но еще можно, например, так:
+
declare @x xml = N'<item id="1">
   <item id="2" parent="1"/>
   <item id="3" parent="1">
      <item id="5" parent="3"/>
      <item id="6" parent="3"/>
      <item id="7" parent="3"/>
      <item id="8" parent="3"/>
      <item id="9" parent="3"/>
      <item id="10" parent="3"/>
      <item id="11" parent="3"/>
      <item id="12" parent="3"/>
      <item id="13" parent="3"/>
      <item id="14" parent="3"/>
      <item id="15" parent="3"/>
   </item>
</item>
<item id="20">
    <item id="21" parent="20"/>
    <item id="22" parent="20">
       <item id="23" parent="22">
          <item id="24" parent="23"/>
       </item>
    </item>
</item>';

with a as
(
 select
  row_number() over (order by (select 1)) as rn,
  t.n.value('@id', 'int') as id,
  t.n.value('@parent', 'int') as parent
 from
  @x.nodes('//item') t(n)
),
b as
(
 select
  id, parent, cast('/' + cast(row_number() over (order by rn) as varchar(10)) + '/' as hierarchyid) as h
 from
  a
 where
  parent is null

 union all

 select
  a.id, a.parent, cast(b.h.ToString() + cast(row_number() over (order by a.rn) as varchar(10)) + '/' as hierarchyid) as h
 from
  b join
  a on a.parent = b.id
)
select
 id, parent, h.ToString()
from
 b
order by
 h;
23 июл 18, 12:13    [21593708]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
felix_ff
Member

Откуда: Moscow
Сообщений: 1172
invm,

тоже подходит.

в моем понимании "критерий лучшести" был бы выведением колонки сортировки дерева типа int/float с минимальными плясками с бубнами.

id name lvl_descr order
1 root 1 1
2 test1 1.1 2
3 test2 1.2 3
4 test4 1.2.1 4
5 test5 1.2.2 5
20 root2 26
21 test21 2.1 7
22 test22 2.28
23 test23 2.2.19
24 test24 2.2.1.110
23 июл 18, 12:27    [21593754]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
felix_ff
Member

Откуда: Moscow
Сообщений: 1172
Да, решение с hierarсhyid выглядит вроде идеальным.
+

declare @t table (
  val char,
  id int,
  parent int
);
insert into @t values ('a', 1, 0), ('b', 2, 1), ('c', 3, 1), ('d', 4, 2), ('e', 5, 2), ('f', 6, 3);
insert into @t values ('i', 7, 0), ('j', 8, 7), ('k', 9, 7), ('l', 10, 9), ('m', 11, 9), ('x', 12, 8);
insert into @t values ('0', 50, 2), ('1', 51, 2), ('2', 52, 2), ('3', 53, 2), ('4', 54, 2), ('5', 55, 2), ('6', 56, 2), ('7', 57, 2), ('8', 58, 2), ('9', 59, 2);
insert into @t values ('0', 60, 3), ('1', 61, 3), ('2', 62, 3), ('3', 63, 3), ('4', 64, 3);

WITH rcte as (
    SELECT [val],
           [id],
           [parent],
           CAST('/' + CAST(ROW_NUMBER() OVER (ORDER BY [id]) AS VARCHAR) + '/' AS HIERARCHYID) AS [order]
    FROM @t
    WHERE [parent] = 0
    UNION ALL
    SELECT
          t.val,
          t.id,
          t.parent,
          CAST(rcte.[order].ToString() + CAST(ROW_NUMBER() OVER (PARTITION BY t.[parent] ORDER BY t.[id]) AS VARCHAR) + '/' AS HIERARCHYID) as [order]
    FROM rcte
        JOIN @t t ON t.[parent] = rcte.id
)
select [val], [id], [parent], [order].GetLevel() AS [lvl], stuff(replace(left([order].ToString(), len([order].ToString())-1), '/', '.'), 1, 1, '') as [order]--, [order].ToString() as [x], [order] as y
from rcte 
order by [order]
--order by convert(hierarchyid, [order])
option(maxrecursion 0);



я правда не очень понял почему в конце в order by нужно опять делать приведение к hierarchyid, без конверта он сортирует как строку.
23 июл 18, 13:38    [21594167]     Ответить | Цитировать Сообщить модератору
 Re: сортировка дерева  [new]
felix_ff
Member

Откуда: Moscow
Сообщений: 1172
ааа все догнал, я в результирующем наборе алиас вогнал который строку дает :)
23 июл 18, 13:47    [21594199]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить