Неограниченность иерархических ступеней у разделов в каталоге

для редкоизменяемых данных - принцип червя. в яндексе наберите "Joe Celko worm tree".
для часто изменяемых можно использовать две таблицы:
(Parent, Child) - стандартная укладка дерева в реляционную таблицу
(Parents, Childs, Level) - для всех Childs, хранятся все Parents и наоборот - Level - относительный номер уровня.

ПС. и в том и в другом случае придется написать весьма нетривиальный код для заполнения таблиц.

ППС. но дело того стОит. проверено.

 

AlTk В SQL2000 есть готовое решение реализуемое через OLAP-service. В ORACLE все вроде тоже есть.

 

Bob,
"... OLAP-service ..."
"ну вы блин, даете!"
ну ты и загнул - из пушки по воробьям.

 

Почему же? Если имеется лицензия на MSSQLServer то это сервис поставляемый в комплекте без дополнительной оплаты.

 

http://www.bookpool.com/sm/1558609202

 

Bob Поставляется то да, но всеж не для этих целей имхо AlTk прав, только две таблицы нафик не надо, одной достаточно, ну а для статичных данных, что в данном случае не проглядывается, принцип червя.

 

jek
Количество выборок всегда несоизмеримо больше количества вставок
Какие статичные данные?

 

Да а волга впадает в каспийское море. Про OLTP кстати слышали? Статичные данные это справочники и тому подобные данные. Динамичные например список сотрудников, каталог производимой продукции и т.п.

 

Bob
может всетаки не через OLAP-service, а через Data Shaping Service ? Но имхо лучше использовать как уже говорилось табличку с полями ID и IDParent, способ червячка смахивает на сферического коня в вакуме )

 

jek,
"одной достаточно"
тогда придется использовать циклы или рекурсивные запросы.

pegas
"способ червячка смахивает"
ничуть. очень даже хорошо работает.

 

По любому придется для прохождения зараз на неограниченную глубину, а для проваливания на один уровень и так и так не придется. Короче разницы нет.

 

в моем случае не придется.
пример
первая таблица:
1, NULL
1, 2
1, 3
2, 4
2, 5
3, 6
3, 7
5, 8
5, 9
вторая таблица
1, 2, 1
1, 3, 1
1, 4, 2
1, 5, 2
1, 6, 2
1, 7, 2
1, 8, 3
1, 9, 3
2, 4, 1
2, 5, 1
2, 8, 2
2, 9, 2
3, 6, 1
3, 7, 1

 

AlTk
Теперь понял, а то в первом посте неотчетливо было про содержимое второй таблицы. Однако размер растет экспоненциально, для больших данных тоже не сахар. Но интересно, я про такое не читал, ну и не делал соответственно. Сенкс.

 

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

CREATE FUNCTION blablabla ()
RETURNS @t table (id int,idp int,levelid int)
AS
BEGIN

declare @levelid int;

set @levelid=1;

insert into @t (id,idp,levelid)
select id,idp,@levelid from table1


while exists(select 1 from @t where levelid=@levelid)
begin

insert into @t (id,idp,levelid)
select table1.id,t2.idp,@levelid+1 from table1
join @t t2 on (table1.idp=t2.id)
where t2.levelid=@levelid;

set @levelid=@levelid+1;

end;

return;

END
автоматически отпадет проблема с синхронизацией двух таблиц

 

pegas,
" ... имхо твое решение избыточно ..."
я привык все-таки к обращению на вы.
а по-воду избыточности могу сказать, что любое решение, мое и Ваше - это есть в какой-то мере денормализация БД, поэтому всегда нужно исходить из реалий эксплуатации приложения. в случае массовых запросов в Вашем случае будет очень много циклов, выборок и соединений. в моем же нет, так как там все посчитано заранее, скажем так, в триггерах. но в Вашем случае, при малом количестве выборок, решение более простое.

jek,
"... для больших данных тоже не сахар. ..."
я думаю пару тройку миллионов записей в этой таблице нормальный сервер выдержит легко - таблица занимает мало места, простая, индексы тоже будут простые. так что работать будет на ура.

 

Если требуется высокая производительность то не советую вообще использовать RDBMS.

Попробуй JBossTreeCache. Подробней тут
http://www.jboss.com/products/jbosscache

Хотя там и есть cacheloader для реляционных баз данных, лучше использовать вот это
http://www.sleepycat.com


http

 

Скажу больше - точно есть :-) На уровне команды SQL. SELECT ... FROM table CONNECT BY PRIOR table.field1=table.field2 START WITH table.field3=...
То есть любое количество уровней иерархии легко реализуемо в одной таблице с возможностью прохода по любой ветви дерева как сверху вниз так и снизу вверх.

 

кстате MSSQL 2005 тоже получил похожую фишку http://www.rsdn.ru/article/db/TSQLinMSSQL2005.xml#ERHA

 

AlTk По зрелом размышлении все же первая таблица не нужна, она получается путем SELECT'а по второй с условием что level=1.

 

[off]Набежало советчиков)))[/off] :vcrazy:

 

Задача не так проста, как кажется, и она не решена. Ключевой вопрос - как обеспечить выборку данных из СУБД одним запросом так, чтобы гарантированно при проходе по выбранному набору Parent'ы всегда оказывались раньше Child'ов, для построения дерева.

Я собрал всё, что здесь было предложено, и построил на MS SQL 2000 такую конструкцию. Таблица взята простая - Id, IdParent, и позаимствована функция от pegas: CREATE FUNCTION blablabla(), в итоге вышло:
Таблица.
CREATE TABLE [_tblLevelsTest] (
[RowId] [int] IDENTITY (1, 1) NOT NULL ,
[IdParent] [int] NULL ,
[Name] [varchar] (50) COLLATE SQL_Latin1_General_CP1251_CI_AS NOT NULL ,
CONSTRAINT [PK__tblLevelsTest] PRIMARY KEY NONCLUSTERED
(
[RowId]
) ON [PRIMARY] ,
CONSTRAINT [IX__tblLevelsTest_Cl] UNIQUE CLUSTERED
(
[IdParent],
[RowId]
) ON [PRIMARY] ,
CONSTRAINT [FK__tblLevelsTest__tblLevelsTest] FOREIGN KEY
(
[IdParent]
) REFERENCES [_tblLevelsTest] (
[RowId]
)
) ON [PRIMARY]
GO
в неё добавлено 10'000 записей с помощью:
/*
Для тестов по уровням вложенности.
Добавить нужное число записей.
*/
ALTER PROCEDURE [dbo].[_vspLevelsTestInsRandomList]
@count int = 100
as

declare @i int, @par int, @max int, @name varchar(50)
set @i = 0

while (@i < @count)
begin
-- print @i
select @max = max(RowId)
from [dbo].[_tblLevelsTest]

set @par = rand() * (@max - 1) + 1
set @name = CHAR(rand() * 50 + 48)

INSERT INTO [dbo].[_tblLevelsTest]
([IdParent], [Name])
VALUES(@par, @name)

-- next
set @i = @i + 1
end

return 0

И функции.
1-я:
/*
Для тестов по уровням вложенности.
*/
ALTER FUNCTION [dbo].[_fnLevelsTestInsRandomList] ()
RETURNS @t table (
UNIQUE clustered (IdParent, LevelId, RowId),
RowId int, IdParent int, LevelId int
-- , CONSTRAINT ID_CONSTR911CL UNIQUE CLUSTERED (IdParent, RowId, LevelId)
)
AS
BEGIN
declare @levelid int;

set @levelid = 1;

insert into @t (RowId, IdParent, LevelId)
select RowId, IdParent, @levelid
from [dbo].[_tblLevelsTest]


while exists(
select 1
from @t
where LevelId = @levelid
)
begin
insert into @t (RowId, IdParent, LevelId)
select [dbo].[_tblLevelsTest].RowId, t2.IdParent, @levelid + 1
from [dbo].[_tblLevelsTest]
join @t t2 on ([dbo].[_tblLevelsTest].IdParent = t2.RowId)
where t2.LevelId = @levelid;

set @levelid = @levelid + 1;
end

return
end

2-я:
/*
Для тестов по уровням вложенности.

TEST:
SELECT
[IdParent],
[RowId],
[LevelId]
FROM dbo._fnLevelsTestSelList()
order by
IdParent
*/

-- версии

/*
-- VARIANT 2: clustered table
ALTER FUNCTION [dbo].[_fnLevelsTestSelList] ()
RETURNS @t table (
UNIQUE clustered (IdParent, LevelId, RowId),
IdParent int, RowId int, LevelId int
)
BEGIN
insert into @t (IdParent, RowId, LevelId)
select
IdParent,
RowId,
LevelId
FROM [dbo].[_fnLevelsTestInsRandomList]()

return
END
*/

-- VARIANT 1: inline table
CREATE FUNCTION [dbo].[_fnLevelsTestSelList_Inline] ()
RETURNS table
AS

return
(
select
IdParent,
RowId,
LevelId
FROM [dbo].[_fnLevelsTestInsRandomList]()
-- where
-- LevelId = 1
)

и итоговая процедура:
/*
Для тестов по уровням вложенности.
Сделать выборку для построения дерева.
*/
ALTER procedure [dbo].[_vspLevelsTestSelTreeList]
as

select
a.[IdParent],
a.[RowId],
a.[LevelId] as LevelId_Debug,
b.[MaxLevelId] as MaxLevelId_Debug
from
(
-- выбрать прямые уровни подчиненности (level = 1)
SELECT
[IdParent],
[RowId],
[LevelId]
FROM dbo._fnLevelsTestSelList_Inline() -- _fnLevelsTestSelList_Cr()
where
LevelId = 1
) as a
inner join
(
-- выбрать для каждого узла его max уровень подчиненности,
-- для сортировки основного результата
SELECT
-- [IdParent],
[RowId],
max([LevelId]) as [MaxLevelId]
FROM dbo._fnLevelsTestSelList_Inline() -- _fnLevelsTestSelList_Cr()
group by
[RowId]
) as b
on
a.IdParent = b.RowId
order by
b.[MaxLevelId] -- важно, по max уровню вложенности

она выбирает по верному признаку - определить max уровень вложенности для каждого RowId, и выбирать их с сортировкой по этому признаку, т.е. в начале всегда будут более "высокие" родители, для каждого child'a (RowId) всегда ранее в выборке будет его IdParent.

НО! Выборка для 10'000 записей длится на промышленном MS SQL Server 2000 целых 5 сек. ((

 

эх, проглядел
jek,
"... Однако размер растет экспоненциально ..."
не эспоненциально, а, в самом плохом случае, когда дерево представлено одной цепью объем второй таблицы будет (n*(n-1)), что в принципе, не так уж и страшно.

chv, как я уже говорил, используйте вместо функции дополнительную таблицу.

 

вторая таблица (Parents, Childs, Level) приведёт к тому, что при перемещении узла внутри дерева придётся переформировывать почти всю эту таблицу, для наших данных, хранящих ещё и историю их изменений, это неприемлемо, как и для любых частоменяющихся данных.

Мои последние запросы на самом деле можно упростить, там есть избыточный код. Достаточно написать SQL UDF, которая для каждого Id узла получает его MaxLevelId уровня max вложенности, и сделать inner join с исходной таблицей (Id, IdParent) для сортировки по MaxLevelId, и задача решена.

 

chv,
"... переформировывать почти всю эту таблицу ..."
это очень большое преувеличение.

"... для наших данных, хранящих ещё и историю их изменений, это неприемлемо ..."
как часто происходит перемещение узла внутри дерева?
сколько раз в секунду, минуту или час?

 

Данные с автоматической закачкой из других источников могут давать непрерывный поток данных, как сервер сможет их принять. В любом случае минимум несколько десятков записей в минуту всегда идёт, этого вполне достаточно, чтобы назвать переформирование таблицы постоянной операцией.

 

Дело в том, что если рассматривать вариант хранения второй таблицы (Parents, Childs, Level) для ускорения select'ов, то к её пересозданию ведёт не только перемещение в дереве, но и любое изменение или дополнение исходной таблицы (Parent, Child), а это уже частая операция, хотя... надо оценить, что критичнее, запрос на select в 3 сек, или затык при обновлении.

 

chv,
"... хотя... надо оценить, что критичнее, ..."
полностью согласен.
еще раз укажу на свои слова: http://www.forum-volgograd.ru/showthread.php?postid=964398#post964398
и замечу, что в моей практике в одной и тоже БД использовались оба варианта: и с таблицей и с функцией (на самом деле с хранимой процедурой, функций тогда еще не было). просто в одном случае было выгодно одно, а в другом -другое.

 

В принципе, мнения сходятся.
Для построения дерева мне достаточно вместо "полной" таблицы (IdParent, Id, Level) хранить лишь пару (Id, MaxLevel), т.е. менять в базе результат выборки:
-- выбрать для каждого узла его max уровень подчиненности,
-- для сортировки основного результата
SELECT
-- [IdParent],
[RowId],
max([LevelId]) as [MaxLevelId]
FROM dbo._fnLevelsTestSelList_Inline() -- _fnLevelsTestSelList_Cr()
group by
[RowId]

при изменении исходной таблицы её триггером или в процедурах изменения. Этот запрос отрабатывается на 10000 исходных записей за 3 сек. Зато выборки дерева по ней будут простым join'ом этой таблицы с исходной (Id, IdParent).
Выходит что-то вроде этого. Попробуем воплотить механизм.

 

"Этот запрос отрабатывается на 10000 исходных записей за 3 сек."

Уточните при каком числе запросов в единицу времени? Подозреваю что это был вообще один единственный запрос. Сможете получить те же 3 секнды хотя бы на 300 тыс. обращений в час?