Проблемы с построением "дерева"(+)

[Sheryld]

Решил тут написать каталог, простенький. Взял банальный алгоритм(не помню как он называется):

ID-PARENT_ID

т.е. каждая ветка знает своего родителя.
рекурсивной функцией строю дерево.

решил провести тест. заполнил базу 10000 записями. причем, каждая ветка имеет 1 потомка.

т.е. получается 10к запросов вида:

select * from table where parentid = id

apache падает(а может и не он).

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

что интересно, ASP.NET+IIS справляется, хотя и долго.

собственно в чем могут быть грабли(я имею ввиду настройки php, apache, mysql)?

p.s. про другие алгоритмы знаю, но некогда их реализовывать, да и для этой задачи - пустая трата времени.

p.p.s.

hard&soft:

athlon xp1700+, 512 DDR
winxp sp1 eng.

apache 1.3.x
php 4.3.9(как модуль).
mysql 3.23.58 d-max-nt

кстати 5-ый php, опять же - как модуль, "съел" - 6k записей, после чего вывод на страницу просто остановился.

p.p.p.s. добавил принудителньое закрытие mysql соединения после каждого запроса. Похоже виновата все же mysql. Теперь под php4 также просто останавливается вывод.

может кто подскажит утилиту(поудобнее), чтобы смотреть текущие connections и queries для mysql. к сожалению mysql administrator требует mysql 4.x.

[EvroStandart]

Может быть просто гдето в настройках прописано максимальное время выполнения. У меня както была похожая проблема. Увеличил время и всё заработало.

[Sheryld]

оно падает гораздо раньше, чем выходит время выполнения скрипты

[dacuan]

Возможно, скрипту не хватает оперативки. По умолчанию там стоит 8M.
В любом случае, можно включить отображение ошибок либо поискать их в логе.

[Sheryld]

ошибки у меня отображаются, логи тоже молчат по этому поводу. а что стоит 8 МБ? как параметр называется?

[dacuan]

Тогда скрипт в студию

[Hubbitus]

Sheryld:
а что стоит 8 МБ? как параметр называется?

memory_limit

Sheryld:
p.p.p.s. добавил принудителньое закрытие mysql соединения после каждого запроса. Похоже виновата все же mysql. Теперь под php4 также просто останавливается вывод.

Может в данном случае какраз лучше использовать постоянное соединение?

[Sheryld]

вот скрипт:

class Category
	{
		var $categoryInfo = array(
		"id"=>0,
		"parent_id"=>0,
		"level"=>0,
		"title"=>"",
		"desc"=>"",
		"creation_date"=>"",
		"modify_date"=>"",
		"photo"=>"");
		
		var $categoryInfoCollection = array();
		
		function Category()
		{
			//default constructor			
		}

                          ................

                          function GetCategoryByParentID($categoryParentID)
		{
			$db = new MySql(null,"mport3",null,null);
			$db->MySql_Connect();
			$db->MySql_SelectDb();
		
			$selectQuery = "select * from category where cat_PARENTID = ". 
			$categoryParentID;
			
			$db->MySql_QueryDb($selectQuery);
			
			
			//echo $selectQuery;
			
			if ($db->dbResult != null)
			{
				while($row = mysql_fetch_assoc($db->dbResult))
				{
					$this->categoryInfo['id'] = $row['cat_ID'];					
					$this->categoryInfo['parent_id'] = $row['cat_PARENTID'];
					$this->categoryInfo['level'] = $row['cat_NODELEVEL'];
					$this->categoryInfo['title'] = $row['cat_TITLE'];
					$this->categoryInfo['desc'] = $row['cat_DESC'];
					$this->categoryInfo['creation_date'] = $row['cat_CREATION_DATE'];
					$this->categoryInfo['modify_date'] = $row['cat_MODIFY_DATE'];
					$this->categoryInfo['photo'] = $row['cat_PHOTO_URL'];
					
					$this->categoryInfoCollection[] = $this->categoryInfo;					
				}
				return 0;
			}
			return -1;
		}

                          ................

}

"дерево":

function Tree($categoryParentID)
	{
		$category = new Category();
		if ($category->GetCategoryByParentID($categoryParentID) == 0)
		{			
			if (!empty($category->categoryInfoCollection))
			{				 	
				foreach($category->categoryInfoCollection as $categoryInfoItem)
				{
										echo $categoryInfoItem["title"] . " " . $categoryInfoItem["parent_id"] . "<BR>\r\n";
					
					Tree($categoryInfoItem["id"]);
				}
			}		
		}	
	}

mysql helper class:

class MySql
	{
		var $dbServer = "";
		var $dbName = "";
		var $dbUser = "";
		var $dbPass = "";
			
		var $dbConn;
		var $dbResult;
		
		var $dbErrorNumber = 0;
		var $dbErrorMessage = "";
		
		var $debugFromHanlder = "";
		
		/*function MySql()
		{
			//default constructor
			
		}*/
		
		function MySql($dbServer = null, $dbName = null, $dbUser = null, $dbPass = null)
		{
			//default constructor
			if ($dbServer != null)
			{
				$this->dbServer = $dbServer;
			}
			if ($dbName != null)
			{
				$this->dbName = $dbName;
			}
			if ($dbUser != null)
			{
				$this->dbUser = $dbUser;
			}
			if ($dbPass != null)
			{
				$this->dbPass = $dbPass;					
			}
		}
		function MySql_Connect()
		{
			if (!isset($this->dbConn) || $this->dbConn == null)
			{
				$this->dbConn = @mysql_connect(
					$this->dbServer,
					$this->dbUser,
					$this->dbPass);
					
				$this->MySql_ErrorHanlder("connect");
			}
		}
		function MySql_SelectDb()
		{
			if (isset($this->dbName) && $this->dbName != null)
			{
				@mysql_select_db($this->dbName,$this->dbConn);
				
				$this->MySql_ErrorHanlder("select");
			}
		}
		function MySql_QueryDb($dbQuery)
		{
			if (isset($dbQuery) && $dbQuery != null)
			{
				$this->dbResult = @mysql_query($dbQuery,$this->dbConn);
				//echo $dbQuery;
				$this->MySql_ErrorHanlder("query");
				
				if (@mysql_num_rows($this->dbResult) == 0)				
				{
					$this->dbResult=null;
				}
			}
		}
		function MySql_Close()
		{
			if (isset($this->dbConn) || $this->dbConn != null)
			{
				@mysql_close($this->dbConn);
				
				$this->MySql_ErrorHanlder("close");
				
			}
			
		}
		function MySql_Free()
		{
			@mysql_free($this->dbResult);
			
			$this->MySql_ErrorHanlder("free");
		}
		function MySql_ErrorHanlder($debugFromHanlder)
		{
			$this->dbErrorNumber = mysql_errno();	
			$this->dbErrorMessage = mysql_error();
			
			if ($this->dbErrorNumber != 0)
			{
				echo $this->dbErrorNumber . "    " . $this->dbErrorMessage;
				echo "    " . $debugFromHanlder . "<BR>\r\n";
			}
						
			$this->dbErrorNumber = 0;
			$this->dbErrorMessage = "";
		}	
	}

[Sheryld]

проблема походу точно в mysql, т.к. опытным путем установил, что коннекта не происходит, видимо их слишком много, но что интересно:

mysql_err* пустые

[dacuan]

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

[zaartix]

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

[Sheryld]

мой класс проходит свободно 500 уровней вложенности. потом начинаются проблемы.

про nested sets я знаю. но не хочу его применять, т.к. в этом проекте он не нужен, а там много времени уйдет на реализацию...

а что можно оптимизировать?

мой интерес чисто теоритический, т.к. в реальных приложениях я ограничиваю вложенность до 100 категорий(на данном алгоритме).

p.s. за файлик спасибо...

[[stv]]

zaartix
Спасибо за класс =) Как раз искал что-то подобное.

[dacuan]

2 Sheryld
Я сильно с алгоритмом не разбирался, но вот, что сразу броилось в глаза (оно большого прироста не даст, но так приятнее работать )
Код:

$this->categoryInfo['id'] = $row['cat_ID'];
$this->categoryInfo['parent_id'] = $row['cat_PARENTID'];
$this->categoryInfo['level'] = $row['cat_NODELEVEL'];
$this->categoryInfo['title'] = $row['cat_TITLE'];
$this->categoryInfo['desc'] = $row['cat_DESC'];
$this->categoryInfo['creation_date'] = $row['cat_CREATION_DATE'];
$this->categoryInfo['modify_date'] = $row['cat_MODIFY_DATE'];
$this->categoryInfo['photo'] = $row['cat_PHOTO_URL'];

$this->categoryInfoCollection[] = $this->categoryInfo;

Можно заменить на

$this->categoryInfoCollection[] = $row;

Второе, лучше все-таки отказаться от длинных имен переменных. PHP с именами переменных более 8-ми символов медленно обрабатываются.

И, наконец, главное. Учитывая, что допустимы 100 уровней вложенности, я бы все-таки дважды подумал, прежде чем использовать рекурсию для дерева. IMHO Лишняя нагрузка серверу ни к чему.

[Sheryld]

ну а как реализовать дерево на php без рекурсивного алгоритма, но с моей структурой?

[dacuan]

Чтобы не заморачиваться, можно, например, ввести еще одну таблицу следующей структуры:

treeid INTEGER AUTOINCREMENT
path   TEXT
id      INTEGER

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

[Sheryld]

такой алгоритм тоже знаю, но в принципе против него, т.к. нарушаются условия нормализации.

к тому же его следует применять, имхо, только если есть в наличии ms sql server 2K, например. чтобы повесить основные операции по поддержке дерева на триггеры. т.е. получить структуру саму себя поддерживающую.

в принципе уже каркас написал. по первым тестам(искуственным) работает весьма шустро, если скрестить с кешем - то самое оно. ежели на реальном тесте производительность сильно ухудшится, то наверное возьму за основу nested sets.

у меня там каталог полностью "кастомный", т.е. помимо менеджмента категорий там еще предполагается, что каждая единица в категории имеет неограниченное, настраиваемое число параметров определенных заранее типов(joins, joins, joins).

[dacuan]

Сообщение от Sheryld

такой алгоритм тоже знаю, но в принципе против него, т.к. нарушаются условия нормализации.

Иногда, приходится поступиться принципами нормализации, например для уменьшения нагрузки на сервер.

Сообщение от Sheryld

к тому же его следует применять, имхо, только если есть в наличии ms sql server 2K, например. чтобы повесить основные операции по поддержке дерева на триггеры. т.е. получить структуру саму себя поддерживающую.

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

Сообщение от Sheryld

в принципе уже каркас написал. по первым тестам(искуственным) работает весьма шустро, если скрестить с кешем - то самое оно.

Зачем опираться не кеш, когда можно разгрузить работу с БД?

Сообщение от Sheryld

ежели на реальном тесте производительность сильно ухудшится, то наверное возьму за основу nested sets.

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

Сообщение от Sheryld

у меня там каталог полностью "кастомный", т.е. помимо менеджмента категорий там еще предполагается, что каждая единица в категории имеет неограниченное, настраиваемое число параметров определенных заранее типов(joins, joins, joins).

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

[Sheryld]

nested sets конечно рулит:

~0.001

рекурсия:

~0.1

[Sheryld]

а как скажем сделать такую вещь(при таком классе nested sets): сортировка каждой ветки дерева но с сохранением порядка.

пример:

должно быть:

аа
бб
вв
   а_в
   б_в

если, я добавлю order by title asc, то будет так:

аа
    а_в
бб
    б_в
вв

есть идеи как получить валидный лист сразу из базы? или придеться перед выводом еще раз все сортировать?

p.s. при рекурсивном алгоритме можно получить такой список сразу...