Drukowana wersja tematu

Kliknij tu, aby zobaczyć temat w orginalnym formacie

Forum PHP.pl _ Artykuły _ Drzewka w PHP [rzseattle]

Napisany przez: scanner 14.04.2004, 10:19:48

Dyskusje na temat artykułu "http://www.php.pl/artykuly/aplikacje_internetowe/architektura/drzewka_w_php"

Napisany przez: Seth 14.04.2004, 11:34:49

Trzy dni wczesniej ten art byl by dla mnie zbawieniem winksmiley.jpg

Napisany przez: scanner 14.04.2004, 11:36:42

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

Napisany przez: halfik 14.04.2004, 13:43:55

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 smile.gif

Napisany przez: lukaswoj 14.04.2004, 14:28:23

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 smile.gif.

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

Napisany przez: kwiateek 14.04.2004, 16:00:15

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

Pozdrawiam.

Napisany przez: enceladus 14.04.2004, 21:10:53

Fajna i prosta implementacja, tylko to ograniczenie głębokości sad.gif 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-implementation.php - Jest kompilacją najlepszych metod jakie znam smile.gif 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.

Napisany przez: rzseattle 14.04.2004, 22:22:52

Ciesze sie ze art bedzie pomocny biggrin.gif.

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 winksmiley.jpg ).

@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.

Napisany przez: halfik 15.04.2004, 07:19:04

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ć.

Napisany przez: enceladus 15.04.2004, 10:34:56

Cytat
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 smile.gif Każda poważna baza danych posiada takie funkcjonalności i wcale nie są zaliczane do kategorii zaawansowane - raczej podstawowe.

Napisany przez: rzseattle 15.04.2004, 19:27:27

Cytat
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?

Cytat
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.

Napisany przez: DhuCerbin 15.04.2004, 20:37:31

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.

Napisany przez: Bora 15.04.2004, 22:39:40

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

  1. SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - 1 AS relativeDepth
  2. FROM groups WHERE cluster = 1 AND level LIKE '1%' AND INSTR(level,'0')-1 <= (5+1)
  3. ORDER BY level
  4.  
  5. ## zmienić na
  6.  
  7. SELECT * , INSTR(
  8. level , '0' ) -1 AS depth, INSTR(level , '0' ) -1 -1 AS relativeDepth
  9. FROM groups WHERE cluster =1 AND LEFT(level , '1' ) = '1' AND INSTR(
  10. level , '0' ) -1 <= ( 5 +1 )
  11. ORDER BY level

czyli kod :
  1. SELECT *, INSTR(level,'0')-1 AS depth, INSTR(level,'0')-1 - [*parent_depth*] AS relativeDepth
  2. FROM groups WHERE cluster = [*parent_cluster*] AND # level LIKE '[*parent_cutLevel]%'
  3. LEFT(level, [*$depth*]) = [*parent_cutLevel] AND INSTR(level,'0')-1 <= ([*$depth*]+[*parent_depth*])
  4. ORDER BY level

co do oznaczeń nie jestem pewien.

Napisany przez: rzseattle 15.04.2004, 22:50:37

Bora podejscie i oznaczenia jak najbardziej sluszne.

Dorwe scannera to w arcie poprawimy to zapytanie/a.

Napisany przez: Nalfein][WR 17.04.2004, 13:35:17

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.

Napisany przez: rzseattle 17.04.2004, 14:42:28

Cytat
[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.

Napisany przez: Nalfein][WR 18.04.2004, 13:29:00

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.

Napisany przez: rzseattle 26.04.2004, 21:30:32

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 winksmiley.jpg
[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 winksmiley.jpg ). Musze tylko znalezc odrobine wolnego czasu.

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

Napisany przez: It's_me 27.04.2004, 06:06:44

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

Napisany przez: DhuCerbin 27.04.2004, 21:47:10

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 ?

Napisany przez: Seth 3.05.2004, 16:19:37

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 smile.gif

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

Napisany przez: rzseattle 3.05.2004, 19:37:06

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.

Napisany przez: Seth 3.05.2004, 19:41:07

smile.gif

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

Napisany przez: DhuCerbin 3.05.2004, 19:54:29

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 ;-)

Napisany przez: Seth 3.05.2004, 19:57:24

Zmeczenie robi swoje.. nie zauwazylem tego smile.gif

Napisany przez: eXtreme 11.05.2004, 17:51:30

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

Napisany przez: DhuCerbin 11.05.2004, 19:34:01

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]

Napisany przez: invx 12.05.2004, 18:25:50

i o takie drzewka moge napisac system frum hyba, nie questionmark.gif

Napisany przez: scanner 12.05.2004, 19:33:24

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.

Napisany przez: invx 12.05.2004, 20:07:04

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...

Napisany przez: treewood 15.05.2004, 10:41:39

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

Napisany przez: eXtreme 16.05.2004, 16:13:25

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

Napisany przez: slaw:) 27.05.2004, 20:32:39

Zgadza sie, zeby metoda depesza dzialala pgsql musi byc. a ma ktos moze wersje na mysql-a? bylbym bardzo wdzwieczny smile.gif. 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

Napisany przez: rzseattle 27.05.2004, 21:03:56

Niestety nie mam czasu narazie aby dostawic druga czesc arta bo goni mnie wszystko opocz biegunki smile.gif. 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 winksmiley.jpg . Jak tylko na uczelni zostawia mnie w spokoju to opisze klase , sprawie by jakos wygladala i dodam pare przydatnych metod.

  1. <?php
  2. class trees{
  3.  
  4. var $maxNest = 5; //liczone od zera()
  5. var $table = &#092;"groups\";
  6. var $digitsPerSub = 2;
  7.  
  8. function trees(){
  9.  
  10. $this->db =& new db;
  11.  
  12. $this->levelNum = $this->maxNest*$this->digitsPerSub;
  13.  
  14. return true;
  15. }
  16.  
  17. function newGroup( $name ){
  18.  
  19. 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.\" \");
  20.  
  21. }
  22.  
  23. function newChild( $name, $parentId ){
  24.  
  25. $parent = $this->db->getRow(&#092;"select cluster, LEFT(level, depth*2) as cutLevel, depth FROM \".$this->table.\"
  26. WHERE RIGHT(level,2) != '99' AND
  27. id=&#092;".$parentId);
  28.  
  29. if(!$parent){return false;}
  30.  
  31. 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
  32. FROM &#092;".$this->table.\" AS g
  33. LEFT http://www.php.net/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)
  34. where g.cluster = &#092;".$parent['cluster'].\" and
  35. g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
  36. (&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\" and
  37. p.level is null
  38. LIMIT 1&#092;");
  39. }
  40.  
  41. function delete( $id ){
  42.  
  43. $r = $this->db->getRow(&#092;"SELECT cluster, LEFT(level, depth*2) as cutLevel,depth
  44. FROM &#092;".$this->table.\"
  45. WHERE id=&#092;".$id);
  46. if(!$r){return false;}
  47.  
  48. return $this->db->execute(&#092;"DELETE
  49.  FROM &#092;".$this->table.\"
  50.  WHERE LEFT( level, &#092;".$r['depth'].\"*2)='\".$r['cutLevel'].\"' AND
  51.  cluster =&#092;".$r['cluster']);
  52.  
  53. }
  54. function getAll( $cluster , $depth = null ){
  55.  
  56. $depth = (http://www.php.net/is_null($depth))?$this->maxNest:$depth;
  57.  
  58. return $this->db->getArray(&#092;"SELECT *, depth
  59. FROM &#092;".$this->table.\"
  60. WHERE cluster = &#092;".$cluster.\" AND
  61. depth <= &#092;".$depth.\"
  62. ORDER BY level&#092;");
  63. }
  64.  
  65.  
  66. function getPart( $parent_id, $depth = null ){
  67.  
  68. $depth = (http://www.php.net/is_null($depth))?$this->maxNest:$depth;
  69.  
  70. $r = $this->db->getRow(&#092;"SELECT cluster, LEFT(level, depth*2 ) as cutLevel, depth
  71. FROM &#092;".$this->table.\"
  72. WHERE id=&#092;".$parent_id
  73. );
  74.  
  75. if(!$r){return false;}
  76.  
  77. return $this->db->getArray(&#092;"
  78. SELECT *, depth, depth - &#092;".$r['depth'].\" as relativeDepth
  79. FROM &#092;".$this->table.\"
  80. WHERE cluster = &#092;".$r['cluster'].\" AND
  81. LEFT (level, &#092;".$r['depth'].\"*2) = '\".$r['cutLevel'].\"' AND
  82. depth <= (&#092;".$depth.\"+\".$r['depth'].\")
  83. ORDER BY level&#092;");
  84.  
  85. }
  86.  
  87. }
  88.  
  89. ?>


i dodajcie kolumne depth (int) do poprzedniej tabeli winksmiley.jpg

Napisany przez: treewood 28.05.2004, 10:06:58

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

Napisany przez: 123tomek 16.11.2004, 14:39:37

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

Napisany przez: Vengeance 16.11.2004, 15:00:16

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

Napisany przez: aszlej 17.01.2005, 21:26:34

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!

Napisany przez: rzseattle 22.01.2005, 14:33:06

sugestia nr 1

Zmien metode newCHild na

  1. <?php
  2.  
  3.  function newChild( $name, $parentId ){
  4.  
  5. $parent = $this->db->getRow(&#092;"select cluster, LEFT(level, depth*2) as cutLevel, depth FROM \".$this->table.\"
  6. WHERE RIGHT(level,2) != '99' AND
  7. id=&#092;".$parentId);
  8.  
  9. if(!$parent){return false;}
  10.  
  11. http://www.php.net/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
  12. FROM &#092;".$this->table.\" AS g
  13. LEFT http://www.php.net/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)
  14. where g.cluster = &#092;".$parent['cluster'].\" and
  15. g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
  16. (&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\" and
  17. p.level is null
  18. LIMIT 1&#092;";
  19.  
  20. 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
  21. FROM &#092;".$this->table.\" AS g
  22. LEFT http://www.php.net/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)
  23. where g.cluster = &#092;".$parent['cluster'].\" and
  24. g.level like CONCAT( '\".$parent['cutLevel'].\"','%') and
  25. (&#092;".$parent['depth'].\"*2) + 2 <= \".$this->levelNum.\" and
  26. p.level is null
  27. LIMIT 1&#092;");
  28. } 
  29. ?>


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.

Napisany przez: aszlej 22.01.2005, 15:19:07

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 :].

Napisany przez: rzseattle 22.01.2005, 17:14:15

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.

Napisany przez: aszlej 22.01.2005, 22:00:40

Cytat(rzseattle @ 2005-01-22 16:14:15)
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 :].

Napisany przez: hawk 2.02.2005, 14:55:27

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 blink.gif.

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

Napisany przez: AcidBurnt 1.03.2005, 16:04:41

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

Napisany przez: wallace 15.04.2005, 23:49:42

Cytat(AcidBurnt @ 2005-03-01 17:04:41)
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#o1_9

Napisany przez: amicek 27.04.2005, 07:54:56

Cytat(AcidBurnt @ 2005-03-01 15:04:41)
nie dziala mi stronka depesza, ma moze ktos te arty gdzies zapisane lub jakis mirror?

Archiwum stronki depesza jest dostepna http://web.archive.org/web/20041013092834/depesz.pl/various-sqltrees-implementation.php.

Napisany przez: Diwi 23.05.2005, 15:13:48

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:

  1. <?php
  2. function getOther ( $actual_id ) {
  3.  
  4. $r = $this->db->getRow(&#092;"
  5. SELECT * FROM
  6. groups
  7. WHERE id='$actual_id'
  8. &#092;");
  9.  
  10. $oczysc_level_z_zer = http://www.php.net/str_replace('0', '', $r['level']);
  11.  
  12. $kategorie = http://www.php.net/substr($oczysc_level_z_zer , 0, -1);
  13.  
  14. $ilosc = http://www.php.net/strlen($kategorie);
  15.  
  16. for ($i = 1; $i <= $ilosc; $i++) {
  17.  
  18. $zmienna = http://www.php.net/substr($kategorie , 0, $i);
  19.  
  20. $zmienna = $zmienna.http://www.php.net/str_repeat('0', 7 - http://www.php.net/strlen($zmienna));
  21.  
  22. $wykonaj[$i] = $this->db->getRow(&#092;"SELECT * FROM `groups` WHERE LEVEL = \".$zmienna);
  23.  
  24. }
  25.  
  26. foreach ($wykonaj as $costam) {
  27.  
  28. http://www.php.net/echo $costam['name'].' / ';
  29.  
  30.  }
  31.  
  32. http://www.php.net/echo $r['name'];
  33.  
  34. }
  35. ?>


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

Przykład zastosowania
  1. <?php
  2. $t = new trees;
  3.  
  4. $t->getOther(57);
  5. ?>


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

Napisany przez: kłulik 26.05.2005, 23:07:18

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ę

Napisany przez: Nickesh 26.11.2005, 15:57:54

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?

Napisany przez: DeyV 27.11.2005, 20:47:29

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

  1. SELECT
  2. tree_kategorie.id,
  3. tree_kategorie.sname
  4.  
  5. FROM tree_powiazania INNER JOIN tree_kategorie ON ( tree_powiazania.parent_id=public.tree_kategorie.id)
  6. WHERE tree_powiazania.child_id = '$iChildId'
  7. ORDER BY tree_powiazania.depth DESC


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

Napisany przez: AxZx 23.01.2006, 15:58:07

bedzie ta klasa ulepszona jeszcze?

bo troche chyba jest wadliwa.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)