Строим дерево (флейм)

Ну елки-палки... Тема интересная, но опять сваливается на флуд. Давайте уж как-то формализуем условия задачи.

Типа так:

1) nested sets использовать нельзя;

2) рекурсия — плохо;

3) хранимых процедур, триггеров и т. п. нет. Чистый sql.

4) кешировать можно (?)

Вот, для затравки, бредовое дерево у себя нашел:

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

Что касается всего остального, то при текущей постановке задачи (1000 записей, 5 уровней) неплохим вариантом является хранение в таблице пути к узлу

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

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

3. Эффективный поиск пока в разработке, сейчас обычный полнотекстовый поиск по базе с указанием id категорий.

4. Рекурсия - не плохо, это математика и это хорошо. Только с умом.

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

6. Путь к узлу не решит все задачи.

В общем все эти задачи у меня решаются один запросом, который я написал выше. На практике работает в целом отлично.

Вообще да, тема очень интересная, но сваливается к тому что раз уж кешируем то как хранить и выбирать не очень важно :)

А вот почему nested sets использовать нельзя ? в том смысле что если "поверх" как предлагает Коля Дубр (т.е. не нарушая исходные условия задачи с хранением parent_id) то выборки там очень удобные и быстрые получаются, а рассчитывать (синхронизовывать иерархии) его нужно только при изменении структуры дерева (что обычно происходит нечасто)

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

Насчёт хранимых процедур и триггеров, то делать их на таблицах без поддержки транзакций может вылезти боком :)

кэширование не заменяет оптимальный алгоритм построения деревьев, это просто некая следующая ступень оптимизации.

Зато там очень неудобный INSERT и перенос веток. Поэтому я использую не одно большое дерево, а "лес" - в этом хитрость.

Если операции изменения БД централизовать в каком-то одном специальном классе - этот код достаточно написать один раз, оттестировать как следует, и больше не задумываться о нем.

Ладно, я пойду бухать корпоратив и придумывать каверзные контраргументы, завтра Вас еще потерзаю :) Спасибо за интересную дискуссию.

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

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

кстати, чего исключили возможность использовать nested sets?

ИМХО, с его помощью или с помощью подобных алгоритмов, можно решить почти любую задачу по хранению дерева в БД майскьюэль лучше, чем с помощью других...

MOP1 добавил 04.10.2008 в 21:27

где-то проскальзывала ссылка

вот что там я увидел:

<?php

function tree_list_tree(&$a_list,$k_item=0)

{

  if(empty($a_list[$k_item])) return array();

  $a_tree=array();

  for($i=0;$i<count($a_list[$k_item]);$i++)

  {

    $f=$a_list[$k_item][$i];

    $f['a_tree']=tree_list_tree($a_list,$a_list[$k_item][$i]['k_item']);

    $a_tree[]=$f;

  }

  return $a_tree;

}



function tree_list_load_all()

{

  // Возвращает ложь в случае ошибки



  //1. Загружаем данные. Загружаем в таком виде, в каком они записаны в таблице.



  //Загружаем сразу все дерево одним запросом

  $r=mysql_query("

    select

      t_catalog_tree.k_item,   #идентификатор элемента

      t_catalog_tree.k_parent, #идентификатор родительского элемента

                               #   элементы верхнего уровня содержат здесь 0

      t_catalog.s_name         #название

    from

      t_catalog,               #данные

      t_catalog_tree           #дерево

    where

      t_catalog.k_item=t_catalog_tree.k_item

    order by

      t_catalog.s_name");

  //Обратите внимание, что в запросе строки отсортированы по s_name.

  //Это сделано для того, что бы и сами элементы массива $a_tree и

  //  списки дочерних элементов этого массива были отсортированы по этому полю.



  if(!$r) return false;



  $a_list=array();

  //Ключ массива - идентификатор родительского элемента

  // значение - список дочерних элементов



  for($i=0;$i<mysql_num_rows($r);$i++)

  {

    $f=mysql_fetch_assoc($r);

    if(empty($a_list[$f['k_parent']]))

      $a_list[$f['k_parent']]=array();

    $a_list[$f['k_parent']][]=$f;

  }



  return tree_list_tree($a_list);

}



?> 

эм... вообщето дерево такой структуры строится без рекурсии ;)

Зачем тратить процессорное время сервера на постройку дерева? Пускай у клиента браузер его и строит :)

Помнится давно как-то писал такую фиговину... Если найду, то выложу.

Не совсем то оказывается писал, но тоже дерево :)

<html>

<head>



</head>

<body><div id="tree"></div>

<script language="JavaScript" type="text/javascript">

is1=new Array();

is2=new Array();

var maxi;

function create_tree()

{

glava=new Array();

part=new Array();

punkt=new Array();

pp=new Array();

chars=new Array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z');

document.write('<ul>');

//Создание глав

i=0;

for(gi=0;gi<Math.random()*10+3;gi++)

{

i++;

is1=0;

is2=0;

glava[gi]='Глава '+(gi+1);

document.write('<li><a href="javascript:showhide('+i+');"><div id="s'+i+'">'+glava[gi]+'</div></a><div id="'+i+'">');

if(Math.random()>=0)

	{

	document.write('<ul>');

	//Создание частей

	parenti=i;

	for(pi=0;pi<Math.random()*10+3;pi++)

		{

		i++;

		is1=parenti;

		is2=0;

		part[pi,1]='Часть '+(gi+1)+'.'+(pi+1);

		part[pi,2]=gi;

		document.write('<li><a href="javascript:showhide('+i+');"><div id="s'+i+'">'+part[pi,1]+'</div></a><div id="'+i+'">');

		if(Math.random()<=0.5)

			{

			document.write('<ul>');

			//Создание пунктов

			pparenti=i;

			for(pui=0;pui<Math.random()*10+3;pui++)

				{

				i++;

				is1=parenti;

				is2=pparenti;

				punkt[pui,1]='Пункт '+(gi+1)+'.'+(pi+1)+'.'+(pui+1);

				punkt[pui,2]=pi;

				document.write('<li><a href="javascript:showhide('+i+');"><div id="s'+i+'">'+punkt[pui,1]+'</div></a><div id="'+i+'">');

				

				if(Math.round(Math.random())<=1)

					{

					document.write('<ul>');

					//Создание контента

					ppparenti=i;

					for(ppui=0;ppui<Math.random()*10+3;ppui++)

						{

						i++;

						is1=parenti;

						is2=pparenti;

						pp[ppui,1]='- '+(gi+1)+'.'+(pi+1)+'.'+(pui+1)+'.'+chars[ppui];

						pp[ppui,2]=pi;

						document.write('<li><div id="s'+i+'">'+pp[ppui,1]+'</div></li><div id="'+i+'"></div>');

						}

					document.write('</ul>');

					}

				

				document.write('</div></li>');

				}

			document.write('</ul>');

			}

		else

			{

			document.write('<ul>');

			//Создание контента

			ppparenti=i;

			for(ppui=0;ppui<Math.random()*10+3;ppui++)

				{

				i++;

				is1=parenti;

				is2=0;

				pp[ppui,1]='- '+(gi+1)+'.'+(pi+1)+'.'+chars[ppui];

				pp[ppui,2]=pi;

				document.write('<li>'+pp[ppui,1]+'</li><div id="'+i+'"></div>');

				}

			document.write('</ul>');

			}

		document.write('</div></li>');

		}

	document.write('</ul>');

	}

document.write('</div></li>');

}

document.write('</ul>');

maxi=i;

for(i=1;i<maxi;i++)

	{

	document.getElementById(i).style.display='none';

	}

}

create_tree();

function showhide(id)

{

//Скрытие всех пунктов, кроме шёлкнутого

for(i=1;i<maxi;i++)

	{

	if(i==id)

		{

		if(document.getElementById(i).style.display=='block'){document.getElementById(i).style.display='none';}

		else{document.getElementById(i).style.display='block';}

		}

	else document.getElementById(i).style.display='none';

	}

//Отображение предков щёлкнутого

if(is1[id]!=0)document.getElementById(is1[id]).style.display='block';

if(is2[id]!=0)document.getElementById(is2[id]).style.display='block';

}



//Показ-сокрытие всего дерева

function sh(action)

{

if(action==0)ac='block';else ac='none';

for(i=1;i<maxi;i++)document.getElementById(i).style.display=ac;

}

//Поиск по подпунктам

function searchpod()

{

document.getElementById('spbutton').value='Работа...';

document.getElementById('spbutton').enabled=false;

n=0;

s1=document.getElementById('searchstring').value;

s2='<b><u>'+s1+'</u></b>';

for(i=1;i<maxi;i++)

	if(document.getElementById('s'+i)!=undefined)

	{

	xx=document.getElementById('s'+i).innerHTML;

	var req=/s1/gi;

	var res=xx.replace(s1,s2);

	if(res!=document.getElementById('s'+i).innerHTML)

		{

		flag1=false;

		for(j=1;j<maxi;j++)if(is1[j]==i)flag1=true;

		flag2=false;

		for(j=1;j<maxi;j++)if(is2[j]==i)flag2=true;

		if(!flag1&&!flag2)

			{

			document.getElementById('s'+i).innerHTML=res;

			n++;

			if(is1!=0)document.getElementById(is1).style.display='block';

			if(is2!=0)document.getElementById(is2).style.display='block';

			document.getElementById(i).style.display='block';

			}

		}

		

	}

document.getElementById('spbutton').enabled=true;

document.getElementById('spbutton').value='Поиск по подпунктам';

if(n>0)document.getElementById('srchres').innerHTML='Найдено: '+n;

else document.getElementById('srchres').innerHTML='Нет совпадений';

}

//Глобальный поиск

function search()

{

document.getElementById('spbutton').value='Работа...';

document.getElementById('spbutton').enabled=false;

n=0;

s1=document.getElementById('searchstring').value;

s2='<b><u>'+s1+'</u></b>';

for(i=1;i<maxi;i++)

	if(document.getElementById('s'+i)!=undefined)

	{

	xx=document.getElementById('s'+i).innerHTML;

	var req=/s1/gi;

	var res=xx.replace(s1,s2);

	if(res!=document.getElementById('s'+i).innerHTML)

		{

		document.getElementById('s'+i).innerHTML=res;

		n++;

		if(is1!=0)document.getElementById(is1).style.display='block';

		if(is2!=0)document.getElementById(is2).style.display='block';

		document.getElementById(i).style.display='block';

		}

		

	}

document.getElementById('spbutton').enabled=true;

document.getElementById('spbutton').value='Поиск по подпунктам';

if(n>0)document.getElementById('srchres').innerHTML='Найдено: '+n;

else document.getElementById('srchres').innerHTML='Нет совпадений';

}

</script>

<input type="button" value="Показать все" onclick="javascript:sh(0);" /><input type="button" value="Скрыть все" onclick="javascript:sh(1);" /><br />

<input type="text" id="searchstring" value="" /><input type="button" id="spbutton" value="Поиск по подпунктам" onclick="searchpod();" /><input type="button" id="spbutton" value="Глобальный поиск" onclick="search();" /><div id="srchres"></div>

</body>

</html>