Получение и отображение дерева.

[phprus]

Получение и отображение дерева.

Есть база данных PostgreSQL в которой есть таблица location из 4-х полей id, parent_id, name, type. Как из этого следует дерево задается путем указаний ссылок на родителя.

Необходимо отображать дерево в таком виде:
Корень
- первый уроверь 1
-- второй уровень
- первый уровень 2
-- второй уровень.
-- второй уровень.

Сейчас используется схема где для получения каждого уровня потомков в каждом поддереве применяется отдельный sql-запрос, то есть в данной схеме 5 запросов получается. каждый уровень каждого поддерева выгребается рекурсивным вызовом функции.

Как Вы понимаете экспоненциальный рост количества запросов от количества узлов в дереве это очень не хорошо...

Можно ли написать такой запрос к базе который бы выбирал данные уже в нужном порядке (то есть после после узла с уровнем N шли бы все узлы с уровнем N+1, а потом только следующий узел уровня N), чтобы для каждого узла для вывода нужно было только определить уровень вложенности, а не высчитывать в скрипте когда же нужно выводить тот или иной элемент.

Или подскажите какой тут еще можно применить тут алгоритм.

Предполагаемое количество записей около 1000.

 

[HraKK]

Nested Sets?

-~{}~ 27.06.08 21:43:

SELECT * и рекурсия на пыхе?

 

[phprus]

HraKK

Nested Sets?

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

SELECT * и рекурсия на пыхе?

Я вот думаю а не подавится ли php обработкой древа в пару тысяч узлов... хотя уровень вложенности и небольшой (не более 5-6).
Вот по этому мне и хотелось бы максимум работы переложить на СУБД.

 

[HraKK]

а проверить? Я думаю не подавиться.
+ Можно держать зеркало этой базы в Nested сет для чтения.

 

[phprus]

а проверить?

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

А ты можешь посоветовать какие-нибудь хорошие статей на русском по реализации SQL в Postgres, а то изучать его отличия от синтаксиса MySQL с нуля по оригинальной английской документации мне сложновато.

 

[Sad Spirit]

Автор оригинала: phprus
Или подскажите какой тут еще можно применить тут алгоритм.

Предполагаемое количество записей около 1000.

Вытаскивать в PHP все записи и строить дерево там... 1000 записей --- это тьфу, к тому же результат построения можно упихать в кэш.

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

Хороших статей на русском нету.

 

[phprus]

Всем спасибо за советы. Реализовал преобразование дерева полностью на php. Вроде работает с достаточной скоростью и сервер не грузит.


Sad Spirit

Хороших статей на русском нету.

А книг хороших по PostgreSQL не посоветуешь на английском или на русском? Или таких тоже нет?

 

[Wicked]

phprus
1) если не сложно, можешь описать получившийся алгоритм?
2)

Как Вы понимаете экспоненциальный рост количества запросов от количества узлов в дереве это очень не хорошо...

и откуда тут "экспоненциальный рост", когда кол-во запросов равно кол-ве нод?

 

[phprus]

Wicked

и откуда тут "экспоненциальный рост", когда кол-во запросов равно кол-ве нод?

Если честно, то мне и самому интересно, с чего я это взял. Попробую списать это на тот факт, что я писал это сообщение в первом часу ночи.

если не сложно, можешь описать получившийся алгоритм?

Вначале по результату выборки строится дерево вида:
array('info'=>',,,', 'children' => array(тут массив таких-же массивов))
Для этого применяется функция следующего вида:

function makeTree($data, $parent_id = null) {
  $ret = array();
  foreach ($data as $node) {
    if ($node[parent_id] === $parent_id) {
      $ret[] = array('info' => $node, 'children' => makeTree($data, $node[id]);
    }
  }
  return $array;
}

А потом это дерево обходится рекурсивно и таким образом конвертируется в массив. На этом-же шаге вычисляется глубина.

Я думаю, что это далеко не самый оптимальный алгоритм, так как количество итераций у foreach велико (массив перебирается полностью на каждом рекурсивном вызове), но все-же это должно быть несколько лучше чем 1000 запросов к базе.

 

[Wicked]

(массив перебирается полностью на каждом рекурсивном вызове)

Именно. Это O(n^2), т.е. порядка 1 млн итераций
Есть другой алгоритм, который делает это за O(n), причем без использования рекурсии:

$tree = array(0 => null);
$root =& $tree[0];
foreach($data as $node) {
  if(!isset($tree[$node["parent_id"]])) {
    $tree[$node["parent_id"]] = array();
  }
  $tree[$node["parent_id"]][$node["id"]] =& $tree[$node["id"]];
}
print_r($root);

 

[phprus]

Wicked
Спасибо.
Я до такого алгоритма вряд-ли бы додумался.

 

[Sad Spirit]

Автор оригинала: phprus
А книг хороших по PostgreSQL не посоветуешь на английском или на русском? Или таких тоже нет?

У PostgreSQL вполне адекватная документация, рекомендую начать с неё. А книги, которые есть, в основном не очень новые... С русскими в принципе не рекомендую связываться --- очень давно переводились.

 

[phprus]

Sad Spirit

У PostgreSQL вполне адекватная документация, рекомендую начать с неё.

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

 

[HraKK]

phprus

я не могу долго читать большие тексты с монитора

На правах рекламы http://lbook.com.ua

Если что свяжись со мной)

 

[phprus]

HraKK
На правах оффтопика.
http://lbook.com.ua/ru/faq

15 – поворот экрана на 900 градусов

900 градусов - это сильно!

Спасибо за ссылку.

 

[HraKK]

Я сайтом не занимаюсь =)) Но скажу чтоб поправили, спс!

 

[algo]

phprus, может я не в теме, но как же насчет ltree ?

 

[phprus]

algo
Судя по всему не в теме я. Я не знаю что такое ltree. А может и знаю, но не знаю что это называется именно ltree.

На всякий случай скажу, что к моменту задания этого вопроса опыта работы с Postgres у меня было 3 дня.

 

[algo]

Автор оригинала: phprus
algo
Судя по всему не в теме я. Я не знаю что такое ltree. А может и знаю, но не знаю что это называется именно ltree.

На всякий случай скажу, что к моменту задания этого вопроса опыта работы с Postgres у меня было 3 дня.

ltree это специальный тип данных + индексная структура для материализованного пути в postgresql.
По сути как строка, но удобнее =)

 

[w0Lf]

$tree = array(0 => null);
$root =& $tree[0];
foreach($data as $node) {
if(!isset($tree[$node["parent_id"]])) {
$tree[$node["parent_id"]] = array();
}
$tree[$node["parent_id"]][$node["id"]] =& $tree[$node["id"]];
}
print_r($root);

Подскажите, а как теперь из этого вывести подобный спикок:

<select name="id">
 <option value="3">Glava 1</option>
 <option value="4">&nbsp;Glava 1.1</option>
 <option value="5">&nbsp;Glava 1.2</option>
 <option value="9">&nbsp;&nbsp;Glava 1.2.1</option>
 <option value="17">Glava 2</option>
 <option value="18">&nbsp;Glava 2.1</option>
 <option value="19">&nbsp;&nbsp;Glava 2.1.1</option>
 <option value="20">&nbsp;&nbsp;&nbsp;Glava 2.1.1.1</option>
</select>