» Построить дерево из DB

Вот довно мучаюсь и не могу толком придумать быстрого алгоритма для построения дерева из базы данных, т.е. есть база такая:
ID PARENT NAME
1 0 Родитель1
2 1 Потомок1
3 1 Потомок2
4 2 Потомок1 у потомка11

надо получить дерево
+Родитель1
+Потомок1
Потомок1 у потомка1
Потомок2

И чтоб енто строилось быстро... у меня строится дерево из 400 элементов порядка 20 секунд - это Оччччччень долго...

Строй только первый подуровень, а к тем элементам, у которых есть потомки добавляй фиктивный (шоб "+" был). Затем когда юзер кликает на "+" - удаляешь фиктивный и выбираешь следующий уровень... И так для каждого.

Была такая идея, да и фиктивного добавлять не надо - можно сказать, что у него есть дети и "+" сам нарисуется... только есть необходимость, что называется произвонить поиск во всех детях элемента (к каждому елементу прикручена дохрена всего) и когда они все есть, то по ним легко пройтись и проверить на наличие нужной инфы... вот...

Я че то не понял - ты поиск в базе делаешь ли как?! Или ты в дереве искать хочешь - брось это занятие...

Если поиск - то по БД, делаешь двунаправленный список (предок хранит код потомка, потомок - код предка) . Находишь - по ссылкам выходишь нв корень и разворачиваешь все что нужно...

Да, под БДТрее есть отдельные, уже готовые компоненты....

HighTower
Как именно строишь?
Через рекурсию ?

Искать по дереву? Бред!

Dust

Цитата:

Я че то не понял - ты поиск в базе делаешь ли как

Поиск-то в базе, только гораздо понятней относительно того (юзеру) где происходит поиск, если ты видишь всё падстуру какого-то элемента. Мне так кажется. Сейчас делаю так: просто прохожусь по всем детям и их детям какого-то узла и вытаскиваю их ID, собираю SQL строчку вида "ID=q1 and ID=q2 and ...." (q1, q2 - числа) и делаю соотв. выборку, потом пробегаюсь по полученно таблице и что-то делаю...


Цитата:

Если поиск - то по БД, делаешь двунаправленный список (предок хранит код потомка, потомок - код предка) . Находишь - по ссылкам выходишь нв корень и разворачиваешь все что нужно...

Что-то не уловил сути... каждый элемент может сожержать любое количество детей и как прикажете запоминать их коды?


Цитата:

Да, под БДТрее есть отдельные, уже готовые компоненты....

Хочу сам написать

Wowik

Цитата:

Как именно строишь?
Через рекурсию ?

Угу. Ф-я, которя строит всех детей какого-то элемнта и потом вызввается для всех постоенных детей... и т.д... Могу кинуться кодом.

Вот базар развели, а толком никто ничего не посоветовал.

HighTower
Вобщем есть отличная статья "Деревья в SQL", которая является переводом не менне известной английской статьи.

Русская версия лежит тут: http://sdm.viptop.ru/articles/sqltrees.html

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

UncoNNecteD бред - это твой пост в этой теме.
По дереву можно отлично искать, только нужно знать как правильно его хранить в БД.

Кроме изложенных двух способов хранения деревьев в этой статье есть еще и "работают" они эффективней. Если что - обращайся(тесь). У меня тема дипломной работы очень тесно связана с хранением иерархических объектов в БД.

Vodmal загнув пальцы ты так ничего и не понял.
У человека ЕСТЬ база. Он не хочет делать древесную структуру. Он строит дерево для отображения (компонент tdbtree) и пытается строить его быстрее.
Но это невозможно если база большая. Поэтому ему рекомендуется достраивать дерево при открытии ветвей.

Цитата:

Вот довно мучаюсь и не могу толком придумать быстрого алгоритма для построения дерева из базы данных

Искать по компоненту tdbtree безмазовая затея, то есть бред, если ты не согласен - обоснуй.
А про поиск по дереву в древообразной базе я знаю достаточно. И то что это достаточно геморное занятие тоже знаю.
Поверь мне я изучал достаточно много способов организации структуры и поиска по базе.
З.Ы. Статья неплохая, но не в тему имхо.

UncoNNecteD

Цитата:

Vodmal загнув пальцы ты так ничего и не понял.

Я не загибал пальцы - извини если так показалось.

А эффективно реализовать алгоритм вывода дерева из "стандартнопостроенной" таблицы не получится. Вернее, пока там будет немного записей, то можно предварительно загрузить все содержимое этой таблицы, по ней построить в памяти дерево.
Может и будет летать...., но если таблица разрастется и там будет 10000 элементов, а если больше?
И зачем тогда хранить это в БД? Что бы потом в памяти "на лету" преобразовывать??? Проще сразу перейти от такого представления к "правильному".


Цитата:

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

Я и не думал об обратном. У меня нет причин думать о ком-либо "плохо", пока он не докажет обратное.

Вот еще одна статья на русском : Древовидные структуры в SQL
http://www.sql.ru/articles/mssql/01091502TreesInSQL.shtml

Тут описан еще один способ хранения деревьев в БД, который работает намного эффективнее если в таблице часто происходит добавление и удаление элементов.

Цитата:

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

об этом и речь!


Цитата:

можно предварительно загрузить все содержимое этой таблицы, по ней построить в памяти дерево

он так и делает, но это долго!!!
Верный это подход или нет, не нам решать так как вся задача нам не ясна.
Я предлагаю вариант построения дерева (в памяти) не полностью, а по мере надобности.
А поиск имхо надо по базе производить, преобразовать базу мысль неплохая.

Народ, спасибо за статьи!
Я тут порылся в инете и нашёл следующие статейки, что вы о них думаете?
Древовидные (иерархические) структуры данных в реляционных базах данных (Часть I)
Древовидные (иерархические) структуры данных в реляционных базах данных (Часть II)

Ладно, положим дерево будет достраиваться по мере надобности, но тогда другой вопрос - как поиск-то организовать?
Положем есть каталог, один из корней которого "Музыка", там есть подразделы "Тексты", "Аккорды", "Табы".... и т.д... В каждом из них есть свои подразделы, скажем названия исполнителей и групп, а в них уже название композиций... . И положем юзер, стоя на ноде "Музыка" решает произвесли глобальный поиск по содержимогу всех подразделов... (типа найти слово "гы-гы" в текстах... или ещё где). Надо каким-то макаром произвести выборку, а когда будет известен результат поиска и юзер захочет перейти на данного детя, а оно даже ещё и не постоено, то как постоить соотвествующий кусок дерева и установить выделение на нужного ребёнка? Вот если всё дерево загружено, то легко, а так я не зданю даже....

Может кто-нибудь механизм консультаций в структуре дерева В+ ?
Я учу по буржуйскому учебнику, но из предоставленного материала ничего не понял.
Таким образом описан механизм консультаций.

"Представьте, что необходимо найти все регистры, чьим ключём поиска будет V. Сначала проверяется корень для нахождения наименьшего значения ключа поиска, большего чем V. Пусть значением данного ключа будет К(i). Следуем указке Р(i) до следующего узла. Если значение не найдено, то k>=K(m-1), где m- число указок узла. В этом случае следуем указке Pm до другого узла. В ранее достигнутом узле снова ищется значение ключа поиска, которое больше чем V, для того чтобы следовать соответствующей указкею В заключении достигаем лист узла."
Буду признателен тому, кто по-русски объяснит мне.

procedure TMainForm.LoadTreeView;
var
TextItem : string;
i ,
pIndex : integer;
aNode : TTreeNode;
begin
with fSource,TreeView Do Begin
// Filtered := true;
Items.Clear;
First;
while not EOF do begin
pIndex := FieldByName('Parent').AsInteger;
TextItem := FieldByName('About').AsString;
if TextItem <> '' then TextItem := '-'+TextItem;
TextItem := FieldByName(FieldStore).AsString + TextItem;
if pIndex = -1 then
aNode := Items.AddObject(TopItem, TextItem , pointer(FieldByName('Index').AsInteger))
else begin
for i := 0 to Items.Count do
if integer(Items[i].Data) = pIndex then Break;
aNode := Items.AddChildObject( Items[i],TextItem , pointer(FieldByName('Index').AsInteger))
end;
Next;
end;
end;
end;


Шото вроде этого - думаю разобратся можно!
Если непоймешь - тогда прошу в ПМ.

Добавлено
Можно и рекурсией!
Но как по мне это будет уже лишним!

HighTower

Цитата:

юзер захочет перейти на данного детя

А что с этим детем он делать будет? Если просматривать/изменять/удалять то позиционирование по дереву тебе не нужно. А если и нужно тогда можешь подняться вверх по дереву от конкретного child-a, запомнить путь по которому прошел, и вернись обратно с построением полного дерева. Минимум что тебе прийдется загрузить это один уровень, максимум -- поддерево. По мере заполнения интерфейса, тебе прийдется считывать все меньше информации.

vserd
Mamay
Вах, не думал что эту тему ещё поднимут
вообщем то я уже давно всё реализовал и пашет, так что спасибо.