Загрузка данных из БД ввиде дерева.

riff

Новичок
Загрузка данных из БД ввиде дерева.

Оцените, пожалуйста, код (Загрузка данных из БД ввиде дерева.). Не очень строго, т.к. учусь.
PHP:
<?php
/**
 * PHP 4.4.4
 *
 * БД
 * -----
 * ID - Идентификатор ветки
 * PID - Родительский ID (если pid=0 значит это самая первая ветка)
 * FIELD1, FIELD2,... - Поля таблицы
 * -----
 *
 * @return array
 */
function &make_tree()
{
	$tree = array();

	$query = mysql_query('select * from `my_table` order by `field2`');
	if (! $query) return $tree;

	$nodes = array();
	$keys = array();
	while (($node = mysql_fetch_assoc($query)))
	{
		//if ($node['childs'] === '1') //если есть поле определяющее наличие дочерних веток
		//	$node['nodes'] = array();  //то добавляем к записи узел (массив дочерних веток) на данном этапе
		$nodes[$node['id']] =& $node; //заполняем список веток записями из БД
		$keys[] = $node['id']; //заполняем список ключей(ID)
		unset($node);
	}
	mysql_free_result($query);

	foreach ($keys as $key)
	{
		/**
		 * если нашли главную ветку(или одну из главных), то добавляем
		 * её в дерево
		 */
		if ($nodes[$key]['pid'] === '0')
			$tree[] =& $nodes[$key];

		/**
		 * else находим родительскую ветку и добавляем текущую
		 * ветку к дочерним элементам родит.ветки.
		 */
		else
		{
			if (isset($nodes[ $nodes[$key]['pid'] ])) //на всякий случай, вдруг в базе есть потерянные ветки
			{
				if (! isset($nodes[ $nodes[$key]['pid'] ]['nodes'])) //если нет поля определяющего наличие дочерних веток
					$nodes[ $nodes[$key]['pid'] ]['nodes'] = array(); //то добавляем к записи узел (массив дочерних веток) на данном этапе

				$nodes[ $nodes[$key]['pid'] ]['nodes'][] =& $nodes[$key];
			}
		}
	}
	return $tree;
}

$tree =& make_tree();
print_r($tree);
?>
 

Alexandre

PHPПенсионер
Оцените, пожалуйста, код
оценить алгоритм или стиль кода?

с точки зрения архитектуры кода, использую
- классы доступа к БД.
- использую классы в принципе,
в общем ООП инфицированный.

вообще смысл этой функции, ну загрузили дерево из БД,
а дальше - опять обход дерева, но уже в массиве ? :confused:
 

riff

Новичок
Конечно алгоритм, хотя если будут пара слов по поводу стиля, можно и их сказать.
 

HEm

Сетевой бобер
Alexandre
вопрос был не про твои предпочтения ;)
 

Фанат

oncle terrible
Команда форума
по поводу алгоритма только одно замечание.
дерево при такой структуре таблицы можно построить только рекурсией.
здесь она не используется.

оно у тебя вообще работает? при какой вложенности?
 

riff

Новичок
Фанат
Да, конечно, всё проверил и перепроверил.

>>при какой вложенности?
Ннесколько веток в которых несколько подветок, в тех тоже несколько подветок.
 

HEm

Сетевой бобер
проверил на своем каталоге товаров, не сработало
$tree выходит пустое, а вот $nodes почти то что нужно, только там дерево со ВСЕМИ ветками, для 7770 товаров имхо, скрипту вполне может наступить кирдык по памяти

-~{}~ 03.04.07 12:39:

ах, ну да, у меня нет ветки с pid=0, поторопился с выводами, все работает
 

riff

Новичок
Автор оригинала: HEm
проверил на своем каталоге товаров, не сработало $tree выходит пустое
это потому, что, наверно, у тебя нет ветки(ок) у которой PID = 0, именно она(и) попадает(ют) в tree.
только там дерево со ВСЕМИ ветками, для 7770 товаров имхо, скрипту вполне может наступить кирдык по памяти
По памяти, если все товары влезли в массив, не наступит, т.к. добавление дочерних элементов происходит не путём копирования, а через указатели.

-----
а как у тебя со скоростью (в смысле не заполнения массива из базы данных, а после строки mysql_free_result) ?
 

Фанат

oncle terrible
Команда форума
HEm
вы говорите о разном.
он говорит о структуре каталога, а ты - о его содержимом.
 

HEm

Сетевой бобер
В общем, тут вместо рекурсии используются указатели, и оно работает, оригинально.
 

riff

Новичок
Автор оригинала: Alexandre ?
а дальше - опять обход дерева, но уже в массиве ?
Ну, всё таки подход-то к решению задачи несколько иной, нежели, к примеру, рекурсия.
 

Alexandre

PHPПенсионер
я не про рекурсию,

если ты имеешь 7 700 товаров, а в некоторых бахах их и до 100 000 бывает, то тебе нет необходимости их все затаскивать в массив, для того, чтоб отобразить ветку из 25 позиций.

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

Здесь сделано нечно похоже.
Использование указателя вместо рекурсии - это плюс.
 

Фанат

oncle terrible
Команда форума
Alexandre
чтобы получить структуру дерева, не обязательно в неё всключать все листья.
 

HEm

Сетевой бобер
Давайте уже резюмируйте и перенесем топик в теорию?
 

riff

Новичок
Автор оригинала: Alexandre
тебе нет необходимости их все затаскивать в массив, для того, чтоб отобразить ветку из 25 позиций.
Я в своём примере расчитывал только на то, что ты(<абстрактно) вытащил селектом (в данном случае всё) ни больше ни меньше.
---
Пока писал ответ, меня уже опередили
 

serglt

Анус, ой, Ахтунг
Не плохой алгоритм формирования дерева без рекурсии :)
Решил попробовать вывести дерево без рекурсии, и вот что у меня получилось:
PHP:
//--- Данные ---
	$treeData = array (
		array (
			'title'   => 'Auto&Moto',
			'chields' => array (
				array (
					'title' => 'auto',
					'chields' => array (
						array ('title' => 'Vaz'),
						array ('title' => 'Gaz'),
						array ('title' => 'Zil'),
					)
				),
				array (
					'title' => 'moto',
					'chields' => array (
						array ('title' => 'Izh'),
						array ('title' => 'Dnepr'),
						array ('title' => 'Ural'),
					)
				),
			)
		)
	);

//--- Вывод ---
	$nbspCnt = 0;
	$curPos = 0;
	$tree = &$treeData;
	$count  = count ($tree);
	$stateArray = array ();
	do {
		while ($curPos < $count) {
			echo str_repeat ('&nbsp;&nbsp;&nbsp;', $nbspCnt) . $tree [$curPos] ['title'] . "<br>";
			if (isset ($tree [$curPos] ['chields'])) {
				array_push ($stateArray, array ('tree' => &$tree, 'count' => $count, 'curPos' => $curPos + 1));
				$tree = &$tree [$curPos] ['chields'];
				$count = count ($tree);
				$curPos = 0;
				$nbspCnt ++;
			} else {
				$curPos ++;
			}
		}
		if (($a = array_pop ($stateArray)) !== null) {
			$curPos = $a ['curPos'];
			$count  = $a ['count'];
			$tree   = $a ['tree'];
			$nbspCnt --;
		}
	} while ($a != null);
 

Vallar_ultra

Любитель выпить :)
serglt
И где ты такие данные хранить собираешся( в таком виде имеется ввиду ) ?
 

riff

Новичок
avenger_msoft
Да, видимо что-то похожее...
Код:
по поводу действительно ли функция, в моём первом сообщении, написана мной - 
даю честное слово, что она полностью придумана мной, и кроме как с помощью 
рекурсии я не знал как построить дерево.
Поводом же к поиску другого способа было желание избавиться от десятков "лишних" циклов.
Промежуточными результатами были доп.массивы с ключами-идентификаторами,
доп.функции и т.п., которые([SIZE=1]промежуточные результаты[/SIZE]) и трансформировались
в исходный результат.
 

serglt

Анус, ой, Ахтунг
Vallar_ultra
Если ты не заметил - это уже дерево, может оно быть и другогой структуры - это не принципиально, я просто вывел без рекурсии в браузер/консоль.
 
Сверху