Hi All!

вот какая задача:
есть 2 таблицы, в первой таблицы содержиться описание(просто элементы с определенной инфой), во второй таблице - указание, как из описания построить дерево (какие узлы после каких), кроме всего прочего помимо указания как строить дерево из описания, на конкретный момент времени из описания можно построить только определенное (но не окончательное) количестов узлов, т.е.  по ходу времени узлы будут достраиваться как только появиться описание в первое таблице, так вот сейчас сделаны две процедуры: 1-я - обход рут-узлов, 2-я (рекурсивная) - обход child-узлов, фактически в рекурсии открывается новый курсор по данным, делается обход по элементам ну и т.д. (каждый элемент может стать узлом), ес-но что данных в первой таблице очень много, и что рекурсивное открытие курсоров очень требовательно как к ресурсам так и ко времени, в связи с этим хочу просто выкачать плоские данные из двух таблиц, и делать обход по данным в пямати, кто что скажет?

ну если я правильно допонял вопрос то первым в голову пришло следующее:

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

а вообще можно поробовать написать вид :
element_code|parent_code|element_name  - order by по паренту - и за один проход можно попробовать сделать.

зы а покаж таблички ?

То есть одна табличка - вершины графа,
вторая - переходы?

Тогда как обычно - вытянул рут и пошёл в рекурсии.
Таблички, конечно, лучше сразу подтянуть. Хотя, если у тебя миллиарды записей... )

все именно так:
table1
  id number not null pk
  ... other fields

table2
  id number not null pk
  pid number nullable 
  tab1_id number not null fk

chief39, не миллиарды, в первой таблице содержиться актуальная информация только за прошедьшую ночь с 0 часов + текущий день, по ней все и строиться
вся проблема в том, что в рекурсивной функции каждый раз открывается курсор, это долго, страничка генериться от 60 до 100 сек, я хочу в идеале иметь 2 набора данных из двух таблиц, и по ним ходить, может уже есть готовое средство для этого, сам я пока склоняюсь к xml + xpath (получить xml и делать по нему обход), но на сколько это будет быстрее, я не знаю

не открывай ... можно бегать и  по резултсету - 
result.previous();
resul.next();... и пр. - для этого нужно 



Но мне кажется тебе нужно сделать HashMap в который загнать key = id, value = name из первой таблички
А далее  resultSet = "select * from table2 order by parent_id"

Загнать в map интереснее, так как несмотря на толькочитабельность выход за границы fetchsize (с помощью next() или previons()) практически эквивалентен очередному запросу. А еще рекомендую ознакомится с такой вот организацией дерева - во многих случаях она позволит избавиться от рекурсии вообще.

Загнать в Мап безусловно интереснее, но тут есть ряд маленьких нюансов:

• что если данные со временем разрастутся настолько, что перестанут влезать в память?
• кэширование данных в памяти содержит риск возможной рассинхронизации с содержимым базы;
• если со временем встанет вопрос о разнесении нагрузки на несколько серверами, автора системы, завязанной на внутрипамятную обработку данных, будет подстерегать большой сюрприз.
• Хранение дерева в памяти делает затруднительным формирование прямых SQL запросов, связанных с позицией в иерархии.

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

Что касается варианта представления деревьев, описанного в статье. Мне, если честно, не понравилось. Вообще, все решения подобного рода можно охарактеризовать одним словом: преагрегация. Что, строго говоря, противоречит принципу четвертой нормальной формы: все, что может быть выведено из данных, должно именно выводиться, а не сохраняться в том или ином виде. Но на практике сознательная денормализация - это полезный и зачастую чрезвычайно эффективный способ повысить производительность системы. Надо только отдавать себе отчет в том, что при этом надо внимательно следить за непротиворечивостью данных и быть готовым пожертвовать скоростью операций обновления.

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

Идея очень простая: нужно всего-навсего хранить полный путь к каждому узлу. Например, имеется такая структура каталога:



Традиционно для хранения таких структур используют самоссылающиеся (self-referencing) таблицы:





А теперь делаем финт ушами: добавляем поле для пути и зполняем его значениями:





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

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

1. По поводу map: я думал об это, но map ведь по сути таблица с двумя столбцами, только мне нужно столбцов побольше
2. 2Stampede, в целом идея толковая, но есть нюансы: сейчас слишком большое дерево,и состовлять пути будет проблематично, кроме всего, дерево непостоянно, ветки могут менятся
3. По поводу статьи: мне кажется, что для меня это будет введение дополнительной таблицы (либо добавление дополнительных столбцов), я хочу получить максимальную простоту и скорость

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



Это тоже не проблема. Вызываем из триггера процедуру, и всех делов. На псевдокоде будет выглядет примерно так:



Можно аналогичным образом оформить в теле Java программы, если неохота заморачиваться с триггерами.


Это сообщение отредактировал(а) Stampede - 17.8.2006, 05:24

В общем-то, вы описали тот же способ, разница только в представлении и месте хранения путей. А какие еще есть способы хранения деревьев, позволяющие избежать рекурсии при построении?

Эту задачу решить можно, и без всякой рекурсии.

Давайте сведём эту задачу к задаче ЗА - перебор всех дочерних элементов данного корневого элемента без всякой рекурсии. Если задачу ЗА мы решим, то думаю наша задача будет решена тоже.

Теперь давайте определим ещё две задачи:

З1 - поиск первого элемента во множестве нашего корневого элемента
З2 - поиск следующего элемента для данного элемента

Если мы эти задачи решим, задача ЗА будет решаться так:
1) решаем задачу З1 и запоминаем найденный элемент как текущий;
2) если текущий элемент = нулл, то переход к п. 6;
3) исполняем полезную работу с текущим элементом;
4) для текущего элемента решаем задачу З2 и запоминаем новый элемент как текущий;
5) переход к п. 2;
6) утверждение: задача ЗА решена.

Для того чтобы можно было решить задачи З1 и З2, необходимо упорядочить всех братьев, а проще упорядочить вообще все элементы, и тогда все братья будут упорядочены тоже. Т.к. в table2 есть уникальный целочисленный идентификатор (это первичный ключ), то он вполне может подойти как средство упорядочивания.

Замечание: я предполягаю что table2.pid и table2.tab1_id ссылаются на table1.id

Рассмотрим ещё две задачи:

Z1 - поиск минимального сына у текущего элемента (current_id - ид текущего элемента)
Решение: 

где: limit 1 - это значит, что запрос возвращает не больше одной строчки (из MySQL)
Если получиться что res_id == null, то у текущего элемента нет детей

Z2 - поиск следующего брата (current_id - текущий брат - у него должен быть родитель)
Решение: 

Если res_id == null, то это значит что текущий брат самый старший.

Деалее будем писать: res_id = Z1( current_id ) - решение задачи Z1 для current_id с результатом в res_id
аналогично и с Z2.

Решение задачи З1:

Задача решена

Ну и последняя задача З2 - самая сложная:
Обозначим: parent_id = P(current_id) - получение родителя, если parent_id == null, то current_id - корневой

Задача решена

При решении задачи ЗА последним элементом мы обработаем корневой

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

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

Замечание: данное решение предусматривает, что у каждого элемента может быть максимум один родитель. Для этого следует создать соответствующий индекс в table2


Это сообщение отредактировал(а) pompei - 18.10.2007, 15:42

Мне нравится такой способ