Оптимизация дерева

← →
Альберт (2006-07-23 14:36) [0]

Есть дерево (классификатор, по сути), которое в идеале должно храниться в БД (порядка 1 тыс. листьев, 3 уровня) и жутко быстро реагировать на просьбы юзера (навигация, collapse, expand и прочее) + быстро инициализироваться. Хочу услышать мнения Мастеров по ряду вопросов.

Во-первых по поводу хранения дерева в таблице. Напрашивается сразу два варианта:

1 вариант:
ID / Data / ParentID
0 - в случае, когда корень

Пример:
1 / Кошки / 0
2 / Сиамские / 1
3 / Собаки / 0
4 / Дворняги / 3
5 / Чеширские / 1
6 / Болонки / 3

Тут порядок не важен.

2 вариант:
ID / Data / Level

Пример:
1 / Кошки / 1
2 / Сиамские / 2
3 / Чеширские / 2
4 / Собаки / 1
5 / Дворняги / 2
6 / Болонки / 2

Тут, понятное дело, важен порядок следования.

У каждого варианта есть плюсы и минусы. К примеру второй вариант удобен тем, что можно быстро получить все листья третьего уровня, простейшим запросом к БД. Есть ли еще варианты? Что посоветуете?

-=-=-=-=-=-=-

Во-вторых, касаемо хранения и обработки. Напрашивается опять же два варианта:

1 вариант (динамический):
Хранение в таблице БД, подгрузка для начала только корня, в случае expand"a любого корневого элемента подгрузка для него child"ов. Может бегать довольно быстро, но одной из задач будет поиск по "классификатору" и вывод неполного дерева с учетом критериев поиска, в итоге сведется ко второму варианту...

2 вариант (статический):
Хранение где угодно, загрузка полностью всего дерева. В случае с БД - ужасно, т.к. времени на загрузку уходит порядочно (делал рекурсией, код могу привести, может посоветуете оптимизацию). В случае с файлом грузится все быстро.

-=-=-=-=-=-

Если есть у кого мысли / идеи по этому поводу, выскажитесь пожалуйста. Я, мягко говоря, опух ( Нужна твердая "отцовская" рука, которая бы привела меня в чувства.

В качестве VCL для дерева решил использовать VirtualTreeView.

P.S. На всякий случай еще раз уточню, что требуется от "классификатора":
1. Отображение дерева (1 тыс. листьев, 3 уровня)
2. Отображение дерева с учетом критериев поиска
3. Возможно обратная связь с БД, либо тогда всю необходимую инфу вытаскивать с БД и линковать к листьям через Data property.
4. Быстрое выполнение запросов типа: показать только третий уровень.
и т.д., в общем, более менее стандартный набор.

← →
KilkennyCat © (2006-07-23 15:02) [1]

Я б вообще БД не использовал бы....

← →
Desdechado © (2006-07-23 15:08) [2]

Почему нельзя комбинировать варианты 1 и 2 для структуры?
Например, все коды для первого уровня укладываются в диапазон 1000-9999, второго - 100000-999999, третьего - 1000000-9999999.
Легко выбирается любой уровень. Если первый цифры уровней в иерархии совпадают (кошки - 1000, сиамские - 100000, у дяди Васи - 1000000), то и подчиненность вычитывается не через рекурсию.
Единственный минус - добавление данных только в монопольном режиме. Но, как я понял, это справочник для чтения, поэтому пойдет.

← →
KilkennyCat © (2006-07-23 15:11) [3]

Если все данные хранить просто как дерево, то можно реализовать все вышеперечисленное...
http://www.a-cons.com/SetupOKVED.exe - вот здесь именно так.

← →
Альберт (2006-07-23 15:35) [4]

Desdechado © (23.07.06 15:08) [2]
Можно попробовать. Спасибо за идею.

KilkennyCat © (23.07.06 15:11) [3]
Гляну. Но БД желательна из-за запросов и потому что многие иные таблицы привязаны к этой.

← →
Суслик © (2006-07-24 01:12) [5]

Спасибо автору.
Хорошо поставленный вопрос за исключением:
1. Какая база.
2. Какое критическое время выполнения запроса.

Я не понимаю:
1. Либо не удачный пример с кошками и собаками (справочники достаточно статичны).
2. Либо не вполне развернутый перечень набора в

> и т.д., в общем, более менее стандартный набор.

В любой из реализаций при том, что листов
> (порядка 1 тыс. листьев, 3 уровня)

ЛЮБАЯ реализация при том, что не четких требований к быстроте выполнения след. запросов:

> 1. Отображение дерева (1 тыс. листьев, 3 уровня)
> 2. Отображение дерева с учетом критериев поиска
> 3. Возможно обратная связь с БД, либо тогда всю необходимую
> инфу вытаскивать с БД и линковать к листьям через Data property.
>
> 4. Быстрое выполнение запросов типа: показать только третий
> уровень.

ЗЫ
2Автор. Я вам еще так скажу, есть еще вариант: хранить еще одну таблицу, где есть 2 столбца: родитель; дите. При том пару держать не только для непосредственных мама-дите, но и для всей иерархии: для каждого корневого элемента есть запись в доп. таблице для каждого концевого элемента. Возможно, что такая архитектура даст вам сделать

> и т.д., в общем, более менее стандартный набор.

← →
Суслик © (2006-07-24 01:14) [6]

Фразу

> ЛЮБАЯ реализация при том, что не четких требований к быстроте
Прошу прощения: решил поправиться. След. фразу

> выполнения след. запросов:
>
> > 1. Отображение дерева (1 тыс. листьев, 3 уровня)
> > 2. Отображение дерева с учетом критериев поиска
> > 3. Возможно обратная связь с БД, либо тогда всю необходимую
>
> > инфу вытаскивать с БД и линковать к листьям через Data
> property.
> >
> > 4. Быстрое выполнение запросов типа: показать только третий
>
> > уровень.

Поправить на

....
даст примерно одинаковые результаты.

← →
Суслик © (2006-07-24 01:18) [7]

Блин, никак корректно фразу не могу написать (неплохо бы сделать предпросмотр).
Суть, уверен, понятна.

← →
Германн © (2006-07-24 01:23) [8]

> Блин, никак корректно фразу не могу написать (неплохо бы
> сделать предпросмотр).

Господа гусары молчать! :-)

← →
ЮЮ © (2006-07-24 05:32) [9]

>
и вывод неполного дерева с учетом критериев поиска, в итоге сведется ко второму варианту...
>

Вполне могут быть выбраны и запросом, пусть и не элементарным:
SELECT lev3.*
FROM
Table lev1
JOIN Table lev2 ON lev1.Id = lev2.ParentId
JOIN Table lev3 ON lev2.Id = lev3.ParentId
WHERE
lev1.ParentId = 0

Или, если нужен только последний уровень:

SELECT lev3.*
FROM
Table lev3
LEFT JOIN Table lev4 ON lev3.Id = lev4.ParentId
WHERE
lev4.Id IS NULL

← →
tupoy (2006-07-24 15:12) [10]

для аналогичной задачи использую полную загрузку в VTV - никаких тормозов и рекурсий. Один раз выбирается запросом вся таблица, грузится в синглетон (объект соответствует записи в таблице), объекты привязываются к узлам дерева. Ну а дальше делайте все что хотите - фильтры, поиск итп - Virtual TV очень быстрый компонент.

2 tupoy
давай урлу на VTV .. оценим!

> давай урлу на VTV .. оценим!

А нечего оценивать, давно оценено :) Очень хороший, бесплатный компонент.
А урлу yandex хорошо знает! Компонет VirtualTreeView

← →
Альберт (2006-07-25 19:37) [13]

@all
простите что пропал )

Суслик © (24.07.06 01:12) [5]
база - MS Access (*.mdb), локальная, понятное дело.
при навигации видимых задержек не должно быть как таковых.

ORMADA © (24.07.06 15:18) [11]
http://www.soft-gems.net/VirtualTreeview/

сам смотрю именно в сторону VTV.

Альберт (23.07.06 14:36)
Есть дерево (классификатор, по сути), которое в идеале должно храниться в БД (порядка 1 тыс. листьев, 3 уровня)
каки запросы, какое БеДе нафиг?? Скачал на клиента при старте программы и показывай как хочешь. 1000 - это ж копейки...

Оптимизация дерева Найти похожие ветки