1. Этот сайт использует файлы cookie. Продолжая пользоваться данным сайтом, Вы соглашаетесь на использование нами Ваших файлов cookie. Узнать больше.

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

Тема в разделе "Программирование", создана пользователем Nekto, 21.12.05.

  1. Nekto

    Nekto Почётный

    5.712
    0
    Т.е. необходимо сделать возможность неограниченого количество вложенных подрубрик в самих подрубриках каталога.
    Никто не сталкивался?

    Нужна наводка на структуру базы данных и только.
     
  2. AlTk

    AlTk Читатель

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

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

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

    Bob Активный

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

    AlTk Читатель

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

    Bob Активный

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

    jek Активный участник

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

    g100m Участник

    420
    0
    jek
    Количество выборок всегда несоизмеримо больше количества вставок :)
    Какие статичные данные?
     
  8. jek

    jek Активный участник

    5.733
    0

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

    pegas Участник

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

    AlTk Читатель

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

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

    jek Активный участник

    5.733
    0

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

    AlTk Читатель

    10.699
    0
    в моем случае не придется.
    пример
    первая таблица:
    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
     
  13. jek

    jek Активный участник

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

    pegas Участник

    311
    0
    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
    автоматически отпадет проблема с синхронизацией двух таблиц
     
  15. AlTk

    AlTk Читатель

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

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

    HorstWessel Активный участник

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

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

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


    http
     
  17. Rem

    Rem Активный

    4.704
    0


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

    pegas Участник

    311
    0
  19. jek

    jek Активный участник

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

    Bob Активный

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

    chv Новичок

    28
    0
    Задача не так проста, как кажется, и она не решена. Ключевой вопрос - как обеспечить выборку данных из СУБД одним запросом так, чтобы гарантированно при проходе по выбранному набору 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 сек. :(((
     
  22. AlTk

    AlTk Читатель

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

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

    chv Новичок

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

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

    AlTk Читатель

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

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

    chv Новичок

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

    chv Новичок

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

    AlTk Читатель

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

    chv Новичок

    28
    0
    В принципе, мнения сходятся.
    Для построения дерева мне достаточно вместо "полной" таблицы (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).
    Выходит что-то вроде этого. Попробуем воплотить механизм.
     
  29. Гость

    Гость Гость

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

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