Эта тема на forum.dklab.ru


Tsvetkov: Иерархические списки (построение и вывод)
Предлагаю рассмотреть тут варианты построения и работы с иерархическими списками.

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

Итак, вот мое решение данной задачи в классическом виде (массивы):

// Образец массива исходных данных (классическая структура)
$array = array(
array('id' => 1,'parent_id' => null,'name' => 'Параграф 1'),
array('id' => 2,'parent_id' => null,'name' => 'Параграф 2'),
array('id' => 3,'parent_id' => 1, 'name' => 'Пункт 1.1'),
array('id' => 4,'parent_id' => 1, 'name' => 'Пункт 1.2'),
array('id' => 5,'parent_id' => 3, 'name' => 'Подпункт 1.1.1'),
array('id' => 6,'parent_id' => 2, 'name' => 'Пункт 2.1'),
);

///////////////////////////////////////////////////////////////////
////// Построения
///////////////////////////////////////////////////////////////////
// Функция построения схемы иерархии
function get_schema(&$array) {
foreach ($array as $key=>$entry) {
$result[$entry['parent_id']][$entry['id']] = $key;
}
return $result;
}
// Рекурсивная функция в иерархического массива
function array_to_tree(&$array, &$tree_array, $root = null) {
$entries = &$tree_array[$root];
if (empty($entries)) return;
foreach($entries as $id=>$key) {
$result[$id] = $array[$key];
$result[$id]['childs'] = &array_to_tree($array, $tree_array, $id);
}
return $result;
}
///////////////////////////////////////////////////////////////////
////// Вывод
///////////////////////////////////////////////////////////////////
// Рекурсивная функция вывода иерархического списка
function print_tree(&$entries) {
if (!empty($entries)) {
echo '<ul>';
foreach($entries as $id => $entry) {
echo '<li>';
echo $entry['name'];
print_tree($entry['childs']);
echo '</li>';
}
echo '</ul>';
}
}
///////////////////////////////////////////////////////////////////

$tree_array = &array_to_tree(&$array, get_schema(&$array));
print_tree($tree_array);


Результат вывода:

<ul>
<li>Параграф 1
<ul>
<li>Пункт 1.1
<ul>
<li>Подпункт 1.1.1<li>
</ul>
</li>
<li>Пункт 1.2</li>
</li></ul>
<li>Параграф 2
<ul>
<li>Пункт 2.1</li>
</li>
</ul>


Незнаю какие будут вопросы - думается, по коду все понятно... Но если все же таковые будут - постараюсь ответить на все :-)
Нужен ли пример аналогичного решения через классы?
Буду очень рад Вашей критике! Я не претендую на номинацию лучшего решения, будут рад увидеть другие варианты. ;)
Юрий Насретдинов:
Если Вам требуется высокая производительность чтения, могу порекомендовать Nested Sets. Впрочем, для всего остального они не очень-то удобны.
Tsvetkov:
Я сам по службе работаю с PostrgeSQL 8.3... а там уже достаточно реализовано средств, чтобы не использовать данные алгоритмы :-)
Данная тема больше пригодится для новичков... ну и для обсуждения в целом, так как я не много нашел полезной информации по данной задаче.
Юрий Насретдинов:
ну и для обсуждения в целом, так как я не много нашел полезной информации по данной задаче.
Хм... Да вроде бы в интернете на эту тему написано очень много :). Впрочем, идеального решения этой проблемы, насколько я знаю, не существует :).

Тут даже приводили на форуме примеры с кучей JOIN'ов, чтобы не делать такое же количество запросов...
Tsvetkov:
Мне кажется обработка массива (в случае ссылок - их незначительное окл-во) в оперативной памяти должно выполняться шустрее, нежели выборка JOIN'ами... Хотя, я как-то до сих пор не собрался протестировать... %)
Юрий Насретдинов:
Ну, обычно-то интересует вопрос, когда дерево хранится в БД... При хранении в простом пхп-файле довольно быстро встанет вопрос масштабируемости... Вот тут БД и придет на помощь :).
Tsvetkov:
В этом я согласен. Особенно, когда дерево растет "как на дрожжах" :)
Но в этом случае уже предусмотрены другие средства, в том числе и на уровне контроллеров БД.

Кстати, схему можно сразу и из базы читать... хм...
В общем, надо тестить :)

Эта тема на forum.dklab.ru