Drzewka w PHP [rzseattle] Opcje

[scanner]

Dyskusje na temat artykułu "Drzewka w php"

Ten post edytował nospor 14.12.2005, 20:12:38

[Seth]

Trzy dni wczesniej ten art byl by dla mnie zbawieniem

[scanner]

Trzy dni wcześniej byłem na wyjeżdzie, a art dostałem tuz przed wyjazdem właśnie
BTW: trzy dni temu, to świętować było, a nie pracować

[halfik]

No a dla mnie byłby zbawienny 2 tygonei temu, gdy kombinowałem jak na bazie zrobić tree żeby móc pruszac się zarówno w pionie jak i poziomie (prawie 2h bym zaoszczędził...). Nic, pewnie się jeszcze nie jedemu przyda

[lukaswoj]

Bardzo ciekawe podejście.

Ja jakiś czas temu jak musiałem się uporać z drzewkami, zrobiłem to wykorzystując dwie tablice. Jedna odzwierciedlała strukturę drzewa a druga - jednowymiarowa trzymała referencje do każdego z elementów drzewa.

Każdy element drzewa to był obiekt klasy TreeElement, a do zarządzania całością była klasa Tree (ona miała w sobie te dwie tablice) posiadająca metody realizujące podobne zadania jak wymienione w art'sie.

Nigdy nie sprawdzałem jak bardzo wolne to jest ale z góry zakładam, że chociażby w porównaniu ze sposobem przedstawionym w tym arts'ie - moje rozwiązanie jest żółwiem .

Czy ma ktoś z was jakieś linki do podobnych artykułów (mogą być po angielsku) ? Jeśli tak to będę wdzięczny za zapodanie ich.

pozdrawiam

Dzieki za prace

[kwiateek]

Jasno, zwięźle i konkretnie (-;. Mi także się ten artykuł przyda.

Pozdrawiam.

[enceladus]

Fajna i prosta implementacja, tylko to ograniczenie głębokości Stosowanie stringów do przetrzymywania schematu drzewa może też wpłynąć na wydajność przy większych drzewkach.
Dlatego zawsze będę polecał metodą Depesza - http://www.depesz.pl/various-sqltrees-impl...lementation.php - Jest kompilacją najlepszych metod jakie znam Zainteresowanych odsyłam do artykułu - przykłady są na bazie Postgresa - w tym konkretnym przypadku widać jego ogromną przewagę na MySQL-em (funkcje, triggery). Nie ma jednak problemu z przeportowaniem wszystkiego ma MySQL-a.

[rzseattle]

Ciesze sie ze art bedzie pomocny .

Co do samej implementacji to moze dopisze kiedys czesc druga "Jak rozszezyc funkcjonalnosc" i opisze tam sposob zwiekszenia mozliwosci (ilosc dzieci ograniczona np do 99 lub nawet do 999 ).

@enceladus

Oczywiscie masz racje ale mi chodzilo o prosta i wmiare szybka klase. Nie chcialem stosowac zaawansowanych i nie przenosnych na inne bazy funkcji i triggerow.

[halfik]

Ale dlaczego chesz ograniczać wielkość drzewa? Czy nie lepiej zrobić bez limitu wysokości?

Tree z ograniczeniami, to jednak nie to co każdemu w każdej sytuacji mogłoby sie przydać.

[enceladus]

Nie chcialem stosowac zaawansowanych i nie przenosnych na inne bazy funkcji i triggerow.

Tu bym właśnie dyskutował nad słabościami MySQL, brak funkcji i triggerów o kluczach obcych nie wspomnę - są to niestety poważne braki - jedyna nadzieja w przyszłych wersjach Każda poważna baza danych posiada takie funkcjonalności i wcale nie są zaliczane do kategorii zaawansowane - raczej podstawowe.

[rzseattle]

Ale dlaczego chesz ograniczać wielkość drzewa? Czy nie lepiej zrobić bez limitu wysokości?

Tree z ograniczeniami, to jednak nie to co każdemu w każdej sytuacji mogłoby sie przydać.

Owszem ograniczenia sa, ale tylko w arcie, pisze teraz klase ktora omija wszystkie niedoskonalosci pierwowzoru. Jak juz wspominalem w podsumowaniu - nie chodzilo mi o podanie na tacy gotowego rozwiazania. Wydaje mi sie ze nie taka jest rola artow.

UPDATE:
heh jeszcze raz to przeczytalem i zauwazylem ze wlasciwie nie odpowiedzialem na pytanie.
Otoz ograniczenie wysokosci drzewa istnieje poniewaz pomaga w utrzymaniu odpowiedniej wydajnosci. Jesli potrzebujesz drzewa z 4 poziomami zaglebienia to po co ci level ze stoma cyframi?

Tu bym właśnie dyskutował nad słabościami MySQL, brak funkcji i triggerów o kluczach obcych nie wspomnę - są to niestety poważne braki - jedyna nadzieja w przyszłych wersjach Każda poważna baza danych posiada takie funkcjonalności i wcale nie są zaliczane do kategorii zaawansowane - raczej podstawowe.

Zdaje sobie z tego sprawe jednak MySQL jest obecnie jesli nie najpopularniejsza to jedna z najpopularniejszych baz. I wlasnie na nia chcialem to napisac. Pozatym art pelniac roleedukacyjna tylko wskazuje pewna mozliwosc. Nie mowie ze masz na tej metodzie oprzec super wielkie drzewa uprawnien z setkami podgrup itd. Jesli natomiast potrzebujesz na szybko czegos drzewiastego to nie widzialem zreczniejszej i szybszej implementacji. I naprawde to nie sa puste slowa ale podparte doswiadczeniem. Drzewka wedlug depesza studiowalem i stosowalem jednak stopien komplikacji nie jest czasami adekwatny do zastosowania.

[DhuCerbin]

troche nieciekawym rozwiazaniem jest korzystanie w artykule z klasy, o któej nic nie wiadomo, a mianowici 'db' - newbie moze nie miec pojecia co robia jej metody ... dobrym wyjsciem by było podać co zwracają. A same metody napisać moze użytkownik sobie sam.

[Bora]

Zastanawiało mnie czy to LIKE jest optymalne
i moja propozycja:

[SQL] pobierz, plaintext 
SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - 1 AS relativeDepth
FROM groups WHERE cluster = 1 AND level LIKE '1%' AND INSTR(level,'0')-1 <= (5+1)
ORDER BY level
 
## zmienić na 
 
SELECT * , INSTR(
level , '0' ) -1 AS depth, INSTR(level , '0' ) -1 -1 AS relativeDepth
FROM groups WHERE cluster =1 AND LEFT(level , '1' ) = '1' AND INSTR(
level , '0' ) -1 <= ( 5 +1 )
ORDER BY level
[SQL] pobierz, plaintext 

czyli kod :

[SQL] pobierz, plaintext 
SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - [*parent_depth*] AS relativeDepth
FROM groups WHERE cluster = [*parent_cluster*] AND # level LIKE '[*parent_cutLevel]%' 
LEFT(level, [*$depth*]) = [*parent_cutLevel] AND INSTR(level,'0')-1 <= ([*$depth*]+[*parent_depth*])
ORDER BY level
[SQL] pobierz, plaintext 

co do oznaczeń nie jestem pewien.

[rzseattle]

Bora podejscie i oznaczenia jak najbardziej sluszne.

Dorwe scannera to w arcie poprawimy to zapytanie/a.

[Nalfein][WR]

rzseattle - fajna koncepcja, a co do głównego ograniczenia - 9 dzieci - możesz przecież umieszczać w tym stringu litery, które także można traktować operatorami "<" i ">". I tak 1 < A < Z, bo ord('1') < ord('A') < ord('Z'). Mały problem by był z działaniami arytmetycznymi, bo między ostatnią cyfrą, a pierwszą literą jest trochę innych znaków w tablicy ASCII. Sposobem na to jest traktowanie tego ciągu znaków jak np. liczby szesnastkowej z wykorzystaniem HEX2DEC (ale wtedy mamy do 15 dzieci) albo po prostu użycie całej tablicy ascii, wtedy zapiszemy 255 dzieci.

[rzseattle]

[WR"]a co do głównego ograniczenia - 9 dzieci - możesz przecież umieszczać w tym stringu litery, które także można traktować operatorami "<" i ">". I tak 1 < A < Z, bo ord('1') < ord('A') < ord('Z'). Mały problem by był z działaniami arytmetycznymi, bo między ostatnią cyfrą, a pierwszą literą jest trochę innych znaków w tablicy ASCII. Sposobem na to jest traktowanie tego ciągu znaków jak np. liczby szesnastkowej z wykorzystaniem HEX2DEC (ale wtedy mamy do 15 dzieci) albo po prostu użycie całej tablicy ascii, wtedy zapiszemy 255 dzieci.

Tez dobry pomysl. Prawde mowiac ostatnio nie mam czasu rozbudowac tej koncepcji ale i tak to bede musial zrobic bo bede musial ja wykorzystac w kilku projetach. Jak juz sie za to wezme to rozwaze kilka mozliwosci w tym twoja. Jednak myslalem przedewszystkim o zwiekszeniu ilosci liczb do zapisu levelu tylko ze nie moge wykorzytywac w takich liczbach zer i w tym momecie pojawia sie maly problem. Ale to drobiazg bo przeciez jako znak konca levelu mozna wziasc podwojne zero.

[Nalfein][WR]

Jeśli już masz tak gmatwać to może rozważ użycie nested sets (left i right marker) rozszerzonych o informację o głębokości danego rekordu względem korzenia drzewa(depth). Dzięki temu masz wszystkie zalety nested sets i rozwiązania Depesza w jednym. Rozbudowa podobnie trudna jak w przypadku Twojego pomysłu, ale szybkość odczytu nieporównywalnie większa.

Pobrać wszystkie dzieciaki, wnuki, prawnuki itd. wybranego rekordu:
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft BETWEEN $my[lft] AND $my[rgt][/sql:1:9b52cbd8af]

Pobrać tylko dzieciaki:
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft BETWEEN $my[lft] AND $my[rgt] AND depth = $my[depth]+1[/sql:1:9b52cbd8af]

Pobrać n-tego dzieciaka wiedząc że istnieje (assert($my[rgt]-$my[lft]>1)):
[sql:1:9b52cbd8af]SELECT * FROM tree WHERE lft = $my[lft]+$n[/sql:1:9b52cbd8af]

Pobrać nagłówki 120 postów z najnowszych wątków z forum o strukturze drzewiastej (tnąc w razie potrzeby wątki nie mieszczące się na stronie) :
[sql:1:9b52cbd8af]SELECT * FROM forum ORDER BY lft DESC LIMIT 120[/sql:1:9b52cbd8af]

Ze względu na prostotę działa hiper-super-szybko. Jedynym minusem jest użycie nieraz poprzedzającego zapytania (lub od razu inner joina), gdyż trzeba znać namiary rodzica (lft, rgt, depth) aby móc znaleźć jego dzieci.

[rzseattle]

Pisalem ze ta klasa jest kompatybilna z ADODB (link w stopce forum), jesli natomiast z jakis przyczyn nie chce uzywac powyzszej klasy to prosze uzyc tej
[php:1:2d6e60d161]<?php
class db{

var $debug =1;

function db(){

$conn = mysql_connect('localhost','root','root');

if (!$conn){
trigger_error ('[db] Nie mozna polaczyc z baza danych ', E_USER_ERROR);
exit();
}

mysql_select_db('trees');

}

//zwraca wynikz zapytania
function execute ( $query ){
if($this->debug) { print $query."nn"; }
$wynik = mysql_query( $query ) or ($this->error( $query, mysql_error()));
return $wynik;
}


// zwraca wynik w ktorym kazdy wiersz jest kolejnym indexem zwracanej tablicy
function getArray ( $query ) {
$r = $this->execute( $query );
if ($r != FALSE ){
while( $line = mysql_fetch_assoc( $r ) ){
$wynik[] = $line;
}
if( isset($wynik) && is_array($wynik)){
return $wynik;
}else{
return FALSE;
}
}else{
return FALSE;
}

}

// zwraca tablice w ktorej kazde pole jest indexem tablicy assocjacyjnej (zwraca tylko 1 wiersz)
function getRow ( $query )
{
$r = $this->execute( $query );
if ($r != FALSE ){
$line = mysql_fetch_assoc( $r ) ;
$wynik=$line;
return $wynik;
}else{
return FALSE;
}
}


function error( $query, $error ){
$query = nl2br($query);
$this->errStr[] = '<hr><table><tr><td><b>Query: </b>'.$query .'</td></tr><tr><td><b>Return Error: </b>'.mysql_error().'</td></tr></table><hr>';

$this->errorMsg();

return true;
}

function errorMsg(){
foreach($this->errStr as $error){
print $error;
}
return true;
}

}

?>[/php:1:2d6e60d161]

co prawda jest stara i wrecz troche zakurzona ale wystarczy.

Na marginesie dodam ze w przygotowaniu jest artykul o roziazanu usuwajacym wszelkie ograniczenia z tej implementacji (dzialajaaca klasa juz jest ). Musze tylko znalezc odrobine wolnego czasu.

UPDATE
Moglbym przysiadz ze przed chwila tu byl post od kogos kto nie zazyl zkad sie wzielo $db

[itsme]

rowniez go widzialem prosze Moderatorów Wortal - Redakcja o info na PW kto go skasowal

[DhuCerbin]

rzseattle : jaki masz sposób odczytu wszystkich rodziców w góre ?
Czyli z id win xp odczytać :
systemy operacyjne, windows, nt, win xp
?

ja jako zwolennik generacji zapytań troche topornie to zrobiłem i chciałbym sie dowiedzieć jak to robia inni. Oczywiscie wiem, ze trzeba zastepowac ostatnia liczbe =/= 0 zerem i pobierać, do momentu uzyskania 00000000. Ale jakim sposobem to robisz ?

[Seth]

CZy ktos probowal pobrac sciezke do elementu drzewka ?

Czyli mamy dostac np:

Kod

array (

    [0] => root

    [0] => element_roota

    [0] => element_elementu_roota

)

Gdzie mamy takie drzewko:

Kod

root

|

-- element_roota

     |

     -- element_elementu_roota

Siedze juz od kilku godzin nd kodem i stanalem na tym - chyba czas odpoczac

Jakby ktos mial SQLa do tej sciezki to byl bym wdzieczny za podrzucenie

[rzseattle]

Nie no az takim wyjadaczem w SQLu nie jestem. Robie to zwyklym whilem pobieram rodzicow ( cutLevel pomiejszony o jedna cyfre ) dopoki nie dotre do korzenia. Zarzucilbym kodem ale juz operuje na dalszych stadiach rozoju tej teori (niestety nie mam czasu na arta) i kody by byly niekompatybilne.

[Seth]

No coz zostaje mi wlasnie takie rozwiazanie. Jak dojde jak jednym zapytaniem wydobyc taka sciezke to podrzuce kod.

[DhuCerbin]

ja najpierw na podstawie numerka generuje numerki wszystkich rodziców [ w php ] i wysyłam zapytanie sql gdzie w [where] są podane te id. dla zabezpieczenia daje [limit] ;-)

Seth : post wyzej jest moje pytanie o to samo ;-)

[Seth]

Zmeczenie robi swoje.. nie zauwazylem tego

[eXtreme]

Mógłby ktoś zarzucić kodem jak rozwiązał ta ścieżkę? Głowię się nad tym i nie wiem jak to zrobić

[DhuCerbin]

Majac dane numerek tego jednego, robisz na nim operacje :
ucinasz ostatnią niezerową liczbę i zamieniasz ja na zaero, zapisujesz w tablicy, dopóki nie osiagniesz 10000...
Wtedy wszystkie elementy tablicy podajesz jako parametr dla where w zapytaniu :

[sql:1:7d24544c0e]
SELECT * FROM tree WHERE pid=$arr[0] OR pid=$arr[1] OR ...
[/sql:1:7d24544c0e]

[invx]

i o takie drzewka moge napisac system frum hyba, nie

[scanner]

invx: jeszcze jeden taki post i Twoje nabijanie postów zakończy Administrator.
Jeżeli masz problem, to go sprecyzuj. Od rozmów o dupie Maryny jest hydepark.

[invx]

przeczytalem artykul, i z niego wywnioskowuje, ze mozna drzewka zastosowac do napisania skryptu do forum. tylko nie spotkalem sie z forum na drzewkach, i nie wiem cy dobrze mysle. :?

P.S.
na hydeparku mialem zapytac o kilka rzezcy ale sie wlasnie powstrzymuje, zeby nie byc osadzonym o nabijanie...

[treewood]

No moim zdaniem metoda w tym artykule jest troche ograniczona (glebia). Ja od dosc dawna stosuje metode 5 zaprezentowana na http://www.depesz.pl/various-sqltrees.php.

w niej nie ma tego typu ograniczen i jest moim zdaniem lepsza. bardzo proste przenoszenie podgrup do innej nadgrupy itd itp

[eXtreme]

Ale trzeba mieć Postgresa a nie każdy go ma.

[slaw:)]

Zgadza sie, zeby metoda depesza dzialala pgsql musi byc. a ma ktos moze wersje na mysql-a? bylbym bardzo wdzwieczny . Bo potrzebne mi sa drzewka, ale tak sie zastanawiam, bo jednak to ograniczenie do 9 dzieci to jednak troche malo w katalogu produktow.
Chetnie bym to sam przerobil, ale jeszcze nie ten czas, nie ta pora (chociac moze wcale az takie to trudne nie jest?).

pozdrawiam

[rzseattle]

Niestety nie mam czasu narazie aby dostawic druga czesc arta bo goni mnie wszystko opocz biegunki . Ale widze ze komus moze sie to przydac (i wszyscy wieszaja psy na klasie do rozwiniecia) wiec umieszczam wersje obslugujaca 99 cioro dzieci , a jesli ktos zechce to w piec minut przerobi ja na wersje z mozliwoscia dopisania 999 cioro dzieci do rodzica. Klasa nie wyglada jeszcze tak jakbym chcial ale mysle ze wybaczycie mi drobne niedociagniecia . Jak tylko na uczelni zostawia mnie w spokoju to opisze klase , sprawie by jakos wygladala i dodam pare przydatnych metod.

[PHP] pobierz, plaintext 
<?php
class trees{
 
	var $maxNest = 5;  //liczone od zera()
	var $table = &#092;"groups\";
	var $digitsPerSub = 2;
 
	function trees(){
 
		$this->db =& new db;
 
		$this->levelNum = $this->maxNest*$this->digitsPerSub;
 
		return true;
	}
 
	function newGroup( $name ){
 
		return $this->db->execute(&#092;"INSERT INTO \".$this->table.\" ( cluster, name, level, depth ) SELECT MAX(cluster)+1,'\".$name.\"', RPAD('0',\".$this->levelNum.\",'0'), 0 FROM \".$this->table.\" \");
 
	}
 
	function newChild( $name, $parentId ){
 
		$parent = $this->db->getRow(&#092;"select cluster, LEFT(level, depth*2) as cutLevel, depth FROM \".$this->table.\"
									WHERE RIGHT(level,2) != '99' AND
									id=&#092;".$parentId);
 
		if(!$parent){return false;}
 
		return $this->db->execute(&#092;" insert into \".$this->table.\" (cluster, name, level, depth ) select \".$parent['cluster'].\", '\".$name.\"', RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1,  2 ) + 1, 2, '0')), \". $this->levelNum .\", '0'),\".$parent['depth'].\"+1
									FROM &#092;".$this->table.\" AS g
									LEFT  JOIN &#092;".$this->table.\" AS p ON CONCAT(g.cluster,'|',RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1,  2 ) + 1, 2, '0')), \". $this->levelNum .\", '0')) = CONCAT(p.cluster,'|',p.level)
									where g.cluster = &#092;".$parent['cluster'].\" and
									g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
									(&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\"  and
									p.level is null
									LIMIT 1&#092;");
	}
 
	function delete( $id ){
 
		$r = $this->db->getRow(&#092;"SELECT cluster, LEFT(level, depth*2) as cutLevel,depth
								FROM &#092;".$this->table.\"
								WHERE id=&#092;".$id);
		if(!$r){return false;}
 
		return $this->db->execute(&#092;"DELETE
								   FROM &#092;".$this->table.\"
								   WHERE LEFT( level, &#092;".$r['depth'].\"*2)='\".$r['cutLevel'].\"' AND
								   cluster =&#092;".$r['cluster']);
 
	}
	function getAll( $cluster , $depth = null ){
 
		$depth = (is_null($depth))?$this->maxNest:$depth;
 
		return $this->db->getArray(&#092;"SELECT *, depth
						  FROM  &#092;".$this->table.\"
						  WHERE cluster = &#092;".$cluster.\" AND
						  depth <= &#092;".$depth.\"
						  ORDER BY level&#092;");
	}
 
 
	function getPart( $parent_id, $depth = null ){
 
		$depth = (is_null($depth))?$this->maxNest:$depth;
 
		$r = $this->db->getRow(&#092;"SELECT cluster, LEFT(level, depth*2 ) as cutLevel, depth
						  FROM &#092;".$this->table.\"
						  WHERE id=&#092;".$parent_id
						);
 
		if(!$r){return false;}
 
		return $this->db->getArray(&#092;"
						  SELECT *, depth, depth - &#092;".$r['depth'].\" as relativeDepth
						  FROM  &#092;".$this->table.\"
						  WHERE cluster = &#092;".$r['cluster'].\" AND
						  LEFT (level, &#092;".$r['depth'].\"*2) = '\".$r['cutLevel'].\"' AND
						  depth <= (&#092;".$depth.\"+\".$r['depth'].\")
						  ORDER BY level&#092;");
 
	}
 
}
 
?>
[PHP] pobierz, plaintext 

i dodajcie kolumne depth (int) do poprzedniej tabeli

[treewood]

jakiego znow postrgresa? ja ta metode uzylem w MySQL ... i zamiast niektorych operacji na bazie przenioslem je do php ... proste i skuteczne

[123tomek]

Moze mi ktos podpowiedziec jak zmodyfikowac ten przyklad zeby uzyskac cos takiego:


Windows
- NoNT
-- Win95
-- Win98
-- Win Milenium
- NT
Linux

Chce uzyc tego do zrobienia menu. Najpierw musze pobrac id glownych galezi (Windows, Linux) by wyswietlic je jako menu glowne. Potem chce by po kliknieciu na dana galaz wybrane zostaly kolejne podmenu (windows-> NoNT i NT) i w kolejnym kroku znowu po kliknieciu na NoNT maja sie rozwinac kolejno win95,98 i me. Po kliknieciu na np. na me ma sie otworzyc juz strona z zawartoscia.
Mam zamiar w bazie przechowywac nazwy plikow php (lub cale linki) do ktorych ma sie odwolac galaz ktora jest ostatnia (win 95,98,me) i otwierac okno z zawartoscia. Do tego oczywiscie menu ma miec rozne poziomy zagniezdzenia np. po kliknieciu w NT zamiast rozwijac galaz ma juz pokazywac sie strona.

Ratuje mnie samo przerobienie selecta lecz idealnym byloby dorzucenie kawalka kodu ktory juz realizuje to menu wraz zwybieraniem linkow

Ten post edytował 123tomek 16.11.2004, 14:40:18

[Vengeance]

http://www.forum.kasart98.com/viewtopic.php?t=9414

[aszlej]

Witam!

Od wczoraj nad tym siedze, ale za nic nie moge dojsc dlaczego nie dziala mi dodawanie nowego dziecka :/ Moge zakladac glowne kategorie, ale gdy probuje to zrobic poprzez funkcje newChild nie dzieje sie nic. Probowalem dawac zapytania na echo itd, ale nie ma tam bledu - wszystkie funkcje zwracaja true.

Funkcje wywoluje tak:

$tree->newChild('Amerykanskie', 1); // Bo chce dodac np. subkategorie 'Amerykanskie' do kategorii samochody (ID 1).

Bardzo prosze o pomoc - jest to dla mnie bardzo wazne.

Z gory dzieki!

[rzseattle]

sugestia nr 1

Zmien metode newCHild na

[PHP] pobierz, plaintext 
<?php
 
 function newChild( $name, $parentId ){
 
$parent = $this->db->getRow(&#092;"select cluster, LEFT(level, depth*2) as cutLevel, depth FROM \".$this->table.\"
WHERE RIGHT(level,2) != '99' AND
id=&#092;".$parentId);
 
if(!$parent){return false;}
 
print &#092;"select \".$parent['cluster'].\", '\".$name.\"', RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1, 2 ) + 1, 2, '0')), \". $this->levelNum .\", '0'),\".$parent['depth'].\"+1
FROM &#092;".$this->table.\" AS g
LEFT JOIN &#092;".$this->table.\" AS p ON CONCAT(g.cluster,'|',RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1, 2 ) + 1, 2, '0')), \". $this->levelNum .\", '0')) = CONCAT(p.cluster,'|',p.level)
where g.cluster = &#092;".$parent['cluster'].\" and
g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
(&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\" and
p.level is null
LIMIT 1&#092;";
 
return $this->db->execute(&#092;" insert into \".$this->table.\" (cluster, name, level, depth ) select \".$parent['cluster'].\", '\".$name.\"', RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1, 2 ) + 1, 2, '0')), \". $this->levelNum .\", '0'),\".$parent['depth'].\"+1
FROM &#092;".$this->table.\" AS g
LEFT JOIN &#092;".$this->table.\" AS p ON CONCAT(g.cluster,'|',RPAD( CONCAT( '\".$parent['cutLevel'].\"' ,LPAD( SUBSTRING(g.level, (\".$parent['depth'].\"*2)+1, 2 ) + 1, 2, '0')), \". $this->levelNum .\", '0')) = CONCAT(p.cluster,'|',p.level)
where g.cluster = &#092;".$parent['cluster'].\" and
g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
(&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\" and
p.level is null
LIMIT 1&#092;");
} 
?>
[PHP] pobierz, plaintext 

Zobacz czy wyprintowane zapytanie dziala na bazie danych czy nie wywala bledow. I co wazniejsze czy zwraca jakis rezultat.

Jesli nie to:

sugestia nr 2
Jesli mozesz to daj link do zrzutu bazy.

[aszlej]

Tak jak mowie probówałem już dawać zapytanie na ekran.. Wkleje Ci to co zwraca wywolanie jej poprzez $tree->newChild('Amerykanskie', 1); :

Kod

select 0, 'Amerykanskie', RPAD( CONCAT( '' ,LPAD( SUBSTRING(g.level, (0*2)+1, 2 ) + 1, 2, '0')), 0, '0'),0+1 FROM groups AS g LEFT JOIN groups AS p ON CONCAT(g.cluster,'|',RPAD( CONCAT( '' ,LPAD( SUBSTRING(g.level, (0*2)+1, 2 ) + 1, 2, '0')), 0, '0')) = CONCAT(p.cluster,'|',p.level) where g.cluster = 0 and g.level like CONCAT( '','%') and (0*2) + 2 <= 0 and p.level is null LIMIT 1

Zrzut bazy:

Kod

CREATE TABLE `groups` (
  `id` int(11) NOT NULL auto_increment,
  `cluster` int(11) NOT NULL default '0',
  `name` varchar(100) NOT NULL default '',
  `level` decimal(10,0) NOT NULL default '0',
  `depth` int(11) NOT NULL default '0',
  UNIQUE KEY `id` (`id`)
) TYPE=MyISAM AUTO_INCREMENT=48;

--
-- Dumping data for table `groups`
--

INSERT INTO `groups` VALUES (1, 0, 'Samochody', 0, 0);

Z góry dzięki za pomoc, gdyż ten błąd blokuje mi pisanie pewnego ważnego modułu :].

[rzseattle]

Wyglada na to ze to ja sie walnalem kopiujac nowsza klase. Zapomialem o wlasnosci klasy $digitsPerSub okreslajaca ilosc cyfer przypadajaca na okresleniepoziomu zagniezdzenia. Ciekawe czemu to wczesniej nie wyszlo . Juz poprawiam zamieszczana wyzej klase.

[aszlej]

Wyglada na to ze to ja sie walnalem kopiujac nowsza klase. Zapomialem o wlasnosci klasy  $digitsPerSub okreslajaca ilosc cyfer przypadajaca na okresleniepoziomu zagniezdzenia. Ciekawe czemu to wczesniej nie wyszlo . Juz poprawiam zamieszczana wyzej klase.

Ehh dzieki Ci za ta poprawke ;]. Teraz wszystko juz dziala tak jak powinno. Btw wogole dzieki za ta klase - jest jedna z lepszych moim zdaniem :].

Ten post edytował aszlej 22.01.2005, 22:04:15

[hawk]

Polecam artykuł http://arxiv.org/html/cs.DB/0401014.

Krótkie wprowadzenie: to co opisuje rzseattle to jest sprytnie zoptymalizowana implementacja Materialized Path. Oprócz tego istnieje jeszcze metoda opisywana przez depesza (formalnej nazwy nie znam) i Nested Sets wymyślone przez Joe Celko (to co omawiał tutaj Nalfein). Nested Sets są bardzo szybkie przy odczycie, ale każda zmiany struktury wymaga dodatkowego UPDATE obejmującego średnio połowę węzłów.

Powyższy artykuł został napisany przez gościa, który wymyślił Nested Intervals - technikę podobną do Nested Sets, z tym że left i right są liczbami wymiernymi, a nie całkowitymi, co pozwala na wyeliminowanie niepotrzebnego UPDATE.

A teraz uwaga: artykuł opisuje, w jaki sposób zapisać te dwie potrzebne liczby wymierne za pomocą... jednego integera .

Jeżeli ktoś to zrozumie to chylę czoła .

[AcidBurnt]

nie dziala mi stronka depesza, ma moze ktos te arty gdzies zapisane lub jakis mirror?

[wallace]

nie dziala mi stronka depesza, ma moze ktos te arty gdzies zapisane lub jakis mirror?

no ja tez szukalem i to znalazlem:
http://www.dbf.pl/faq/tresc.html?rozdzial=1

[amicek]

nie dziala mi stronka depesza, ma moze ktos te arty gdzies zapisane lub jakis mirror?

Archiwum stronki depesza jest dostepna tutaj.

[Diwi]

Cóż powiem że artykuł jest świetny a ja w chwili czasu dopisałem jeszcze jedną metode:

Często gdy wchodzimy na jakiejś stronie do kategorii możemy na samej górze treści zauważyć:

Download / Skrypty php / CMS-y

Napisałem metode która tworzy coś takiego na podstawie klasy z artykułu:

[PHP] pobierz, plaintext 
<?php
function getOther ( $actual_id ) {
 
		$r = $this->db->getRow(&#092;"
		SELECT * FROM
		groups
		WHERE id='$actual_id'
		&#092;");
 
		$oczysc_level_z_zer = str_replace('0', '', $r['level']);
 
		$kategorie = substr($oczysc_level_z_zer , 0, -1);
 
		$ilosc = strlen($kategorie);
 
		for ($i = 1; $i <= $ilosc; $i++) {
 
				$zmienna = substr($kategorie , 0, $i);
 
				$zmienna = $zmienna.str_repeat('0', 7 - strlen($zmienna));
 
				$wykonaj[$i] = $this->db->getRow(&#092;"SELECT * FROM `groups` WHERE LEVEL = \".$zmienna);
 
		}
 
		foreach ($wykonaj as $costam) {
 
				echo $costam['name'].' / ';
 
		 }
		 
		echo $r['name'];
 
  }
?>
[PHP] pobierz, plaintext 

U mnie działa więc u was też powinno. Można sobie zmienić sposób wyświetlania i wogóle wszystko .

Przykład zastosowania

[PHP] pobierz, plaintext 
<?php
$t = new trees;
 
$t->getOther(57);
?>
[PHP] pobierz, plaintext 

Taki skrypcik (przy rekordach z artykułu zwraca nam coś takiego)

windows / NT / Win 2003

Wadami tego zastosowania jest:

Bardzo duża ilośc wykonywanych zapytań SQL.
Ograniczenie maks. poziomu zagnieżdżenia do 7 leveli. Można to bardzo łatwo zmienić wystarczy zmienić
$zmienna = $zmienna.str_repeat('0', 7 - strlen($zmienna));
na
$zmienna = $zmienna.str_repeat('0', ILOSC_LEVELI - strlen($zmienna));

Pozdrawiam

Ten post edytował Diwi 23.05.2005, 15:30:10

[kłulik]

Sory, że odświerzam.
Jeśli ktoś ma skrypt drzewek zrobiony w oparciu o metodę depesza ale z wykorzystaniem MySQL niech się odezwie na PW. Proszę

[Nickesh]

Witam...

Ogolnie gratuluje tworcy tego pomyslu z levelem. Mimo wszelkich uwag, podanych na forum, dla niezbyt obszernych projektow, to idealne, szybkie i proste w implementacji rozwiazanie.

Jesli chodzi o zwiekszenie ilosci dzieci, to mysle, ze sporym uproszczeniem jest dodanie jeszcze jednego zalozenia. Mam na mysli pomysl z uzyciem dwoch cyfr do reprezentacji kazdego poziomu glebokosci w polu level. Przy takim zapisie, nalezaloby zwrocic uwage na poczatkowe zero w level'u, np 010201000...
Przy wszelkich operacjach matematycznych, bedzie ucinane ze sciezki.
Mozna dzialac LPADem w kazdym zapytaniu, ale chyba latwiej jest po prostu ustalic, ze levele zaczynaja sie od 10, a nie od 01. Rezygnacja z tych dziesieciu dzieci przy kazdym rodzicu, nie powinna miec az takiego znaczenia. Zwlaszcza, ze - tak jak pisalem wyzej - taki sposob konstrukcji drzewa bedzie znakomicie nadawal sie do mniejszych struktur, np. drzewiaste menu, gdzie nie bedzie sie przekraczalo tych 90 dzieci, natomiast 10 byloby chyba niewystarczajace. W dodatku ograniczenie to w zasadzie moze dotyczyc tylko pierwszego, najwyzszego poziomu.

Ten sposob uratowal mnie przed dalsza meczarnia, po mnowstwie nieudanych prob z ta najbardziej intuicyjna struktura drzewa (ID i parent_ID w kazdym wierszu), od ktorej podobno kazdy z nas zaczynal ;P

dzieki ;]


Edit:

Probowalem napisac zapytanie, ktore wypisze mi sciezke od korzenia do elementu o podanym ID (np. home>gallery>sport...). Udalo mi sie tylko z obrobka zapytania przez php. Czy ktos probowal dzialac w tym kierunku przy pomocy samego SQLa?

Ten post edytował Nickesh 27.11.2005, 15:05:55

[DeyV]

U mnie to zapytanie wygląda mniej więcej tak:

[SQL] pobierz, plaintext 
SELECT
	tree_kategorie.id,
	  tree_kategorie.sname
 
FROM tree_powiazania INNER JOIN tree_kategorie ON ( tree_powiazania.parent_id=public.tree_kategorie.id)
				  WHERE tree_powiazania.child_id = '$iChildId'
				  ORDER BY tree_powiazania.depth DESC
[SQL] pobierz, plaintext 

Niestety - nie jestem pewien, czy będzie u Ciebie działało poprawnie, ponieważ pracuję na nieco zmodyfikowanej wersji depeszowego drzewka.

[AxZx]

bedzie ta klasa ulepszona jeszcze?

bo troche chyba jest wadliwa.