Witam,

Piszę ten temat bo ogarnęła mnie już całkowita niemoc. Próbuję zaimplementować jakiś sensowny algorytm drzewek do mojego CMFa. Nie chcę korzystać z Nested Sets (left, right), bo to kompletnie nie nadaje się do większych drzew.

Znalazłem coś takiego:
http://fungus.teststation.com/%7Ejon/treeh...reeHandling.htm

Metoda bardzo fajna, ale utknąłem na jednej bardzo istotnej rzeczy - wyświetlaniu drzewa. Teoretycznie, zgodnie z tym co piszą w artykule, by pobrać drzewo (lub daną część drzewa) wystarczy użyć zapytania:

Select Id from Path where AncestorId = 2

Przypuśćmy, że drzewo wygląda tak:


(gdzie cyfry w nawiasach to numery ID elementów -- 'banan' został dodany później niż 'warzywa'). W tym wypadku, używając powyższego zapytania dostanę:



Czy jest jakiś sensowny sposób, by pobrać odpowiednio posortowane drzewo korzystając z powyższego przykładu?

A może znacie jakieś inne efektywne sposoby przechowywania drzew w bazie danych? Zależy mi przede wszystkim na efektywności i elastyczności. Nested Sets odpadają

co zas odpadaja? poprostu trzeba dodac n-level i wyswietla sie bardzo latwo...

http://www.phpriot.com/d/articles/php/appl...sign/index.html

wydaje mi sie ta klasa idealna, chyba, ze ktos znalazl cos lepszego ;]

Ja kozystam z "przerobionych" drzewek ip, jak kiedys rozmawailem z Its_me to mowil nawet on ze to najlepsze drzewka.

Nie testowalem nigdy innych, dlatego nie wiem jak tam inne, ale wybieranie i cala reszta szlo mi calkiem sprawnie (czyt. bez problemow).

Teraz stoje wlasnie przed problemem drzewek, i nie wiem do konca jakie najlepiej wybrac... jak ktos ma jakies ciekawe, przestestowane drzewka (z porowaniem wydajnosci) to chetnie sie w nie zaglebie.

Wydawało mi się, że wyraźnie powiedziałem, że nie chcę Nested Sets. Korzystałem z tego do tej pory (tak z n-level ), ale widzę, że dla dużych drzew ta metoda jest nie do przyjęcia. Wyobraź sobie ile zajmie np dodawanie nowego posta na forum, gdzie jest 90 000 wątków. Poza tym, jeśli coś pójdzie nie tak przy dodawaniu, to całe drzewo jest rozwalone.

Nie chcę Nested Sets. Kropka.
Użyję ich w ostatecznej ostateczności.


Coś więcej?

Najlepsze znane (przynajmniej mi) drzewko to drzewko depesza, ma ono jednak sens tylko na PgSQL lub innej bazie tego poziomu.

Oczywiście mówię o ostatnim z omawianych przez niego przykladów - to, które sam opracował.

Ja do tego dodaję jeszce zawsze parent_id w kategoriach - jednak dzieki temu jest łatwiej.

DeyV, tez uzywam drzewka depeszy ;] z tym ze na mysql je oprogramowalem na potrzeby swojego cms'a. Pol roku temu jak tworzylem cms'a wydawalo mi sie odpowiednie, teraz po prostu wybralbym postgresql i jego drzewo, wtedy wiekszosc problemow znika.

Przyjrzałem się dokładniej rozwiązaniu depesza. Z tego, co widzę to jest ono bardzo podobne do tego, co podałem w pierwszym poście, z tym, że dodatkowo wprowadził kolumnę depth.

Sposób dość fajny, ale też nie rozwiązuje mojego problemu - do sortowania drzewa musi być użyta dodatkowa funkcja.

Jeszcze przejrzę jak to jest w ezPublish. Wydaje mi się, że tam jest chyba dodatkowa kolumna 'path' typu varchar, w której przechowywana jest ścieżka drzewa, np.: /rosliny/owoce/banan.

Oj coś mi się zdaje, że chyba wrócę do Nested Sets, mimo, że nie jest mi to na rękę :/

Jeśli o mnie chodzi, to z mysqla zrezygnowałbym już dawno. Mam na swoim serwerze postgresa i nie byłoby problemów z uruchomieniem skryptu. Problem tkwi w tym, że system ma posłużyć także dla ewentualnych klientów, którzy nie zawsze będą mieli możliwość instalacji PgSQL na serwerze. MySQL niestety musi zostać. Dołujący jest też fakt, że praktycznie ze świecą można szukać firmy hostingowej, która udostępnia mySQL 4.1 :/

ja potwierdzam, ze drzewka IP sa dosyc dobre. Nie ma wiekszych problemow z implementacja i utrzymaniem

drzewka IP? co to oznacza? Immediate Parent?

to drzewka, ktorych galezie rpzedzielone sa dzielnikiem w tym wypadku kropka:

warzywa/jadalne/kapusta/kiszona to np
18.57.36.2

Nigdy nie wiedziałem w czym tkwi problem z drzewkami . U mnie każdy wpis ma własne pole 'id' oraz pole 'parent_id' dzięki czemu bardzo łatwo można wyświetlić wszystkie dzieci danego rodzica, a potem dzieci tamtych dzieci, a potem ...

Pomysl jaki implementuje M$, sprawdzony ale jak widac na tym forum nie jest dla baz polecany, poniewaz trudnosc w wyciaganiu danych. Kolejne typ drzewka juz wymieniony w tym watku to odwolanie do parenta, elastyczny sposob, przydaje sie jesli chesz szybko wyciagnac "dzieci", wszystko ladnie zindeksowane itd, trudnosc polega na tym ze problem jest ze sciezka, bo wszytko musimy robic rekurencyjne, no chyba ze laczymy 2 podane sposoby.

To się chyba zwie Materialized Path. Rzeczywiście chyba muszę się nim poważniej zająć :]

@Levabul: jasne, że nie ma w tym nic złego dopóki nie używasz rekurencji do wyświeltania drzewa

ja u siebie jedna funkcja zrzucam drzewka do pliku txti potem juz elegancko i szybko wszystko pobieram:)

W jakim celu?

Ja mam to tak:
http://windforce.strefaphp.net/code/tree/?...pTree.class.php

Testowalem tylko troszke, poniewaz potem pad dysku mi usuna wszytko (czesc kodu zostala).

To byla 1wsza podstawowa wersja, tabeli wam dac nie moge poniewaz jej nie mam (ale chyba wszytko jest w miare jasne.

Uzywalem tego i dziala bardz dobrze (testowalem tylko chwile, poniewaz jak to pisalem to poprostu mialo to byc zeby sie na tym reszta oparla).

Nie testowalem wydajnosci, jedyne co wiem to to ze to dziala

Wszelkie uwagi mile widziane.

jezeli bym operowal na bazie danych, musialbym wykonywac duzo zapytan sql ( srednio 4-5). tutaj nie wykonuje zadnego :]

Sprawdźmy, czy dobrze rozumuję:



Tak więc wartość 'path' dla elementów powyższego drzewa wygląda:

• rośliny: 1
• owoce: 1.2
• warzywa: 1.3
• banan: 1.2.4

Tak to powinno być?

Co do pobierania drzewa, to chyba będzie to coś takiego:
SELECT * FROM tree WHERE path LIKE '1%' ORDER BY path.

To jest calego drzewka w gore:)

a w dol to tak jak ja napisalem chyba najlepiej (mam metode)

Ja się właśnie zastanawiałem którą z metod użyć i chyba zrobie IP W samą porę ten temat.

Jak to w górę?? Skoro 1% to pobiera po kolei w dół:
1.2
1.2.4
1.3

no i o to hwao chodzi:)

A gdyby pobrał path i potem explodem podzielił przez sparator "." do tablicy $x. Później wszystko do drógiej tablicy foreachem.
Wyglądało by to tak $tab[$x[0]][$x[1]][$x[2]] itd. ...

Wartość danego wpisu byłaby w $tab[1][5]['value']...

I tak wszystkie wiersze przelecieć i mamy wszystko w tablicy, a potem z wyświetleniem, to nie ma problemu?

Co o tym myślicie?

a ile to bedzie zapytan do bazy danych policz
Jak jedno, to ok

jedno zapytanie, które zwraca wszystkie wiersze

ja przelatuje te wiersze i wszystko wrzucam do jednej tablicy

wyświetlić tablicę to nie problem

Ale jak z szybkością i wydajnością... Duże dane w jednej tablicy?
No, ale przecież jakby ktoś chciał tylko fragment drzewka to sobie użyje like 1.5.5%

ze sciezka zapisywana jako string jest taki problem, ze trzeba napisac mechanizm, ktory bedzie to poprawial gdy usuniemy lub przesuniemy dana kategorie...

co do exportu drzewa do pliku txt.. nie widze sensu, nie wiem jak to ma cokolwiek przyspieszyc... przeciez zapytanie mozna cachowac, albo modul, cala strone, kto komu co pasuje

Co do przenoszenia to mgłobybyć UPDATE z odpowiednim wyrażeniem regularnym: np. mamy 5.2.6.1. I jeżeli chcemy przesunąć ostatnią grupę x.6.1 do np. 5.3.x to wystarczyłoby zmienić tylko 2 na 3...
Ale jeżeli już istnieje 5.3? Wtedy mógłby wystąpić konflikt. Więc najpierw trzebabyłoby znaleźć ostatnią podgałęź 5.3 i wszystkie podgałęzi 5.2 zmienić na kolejne, ale to byłoby niepraktyczne i należałoby zmienić we wszystkich istniejących tabelach (5.2.6 na 5.2.6+x, a potem przenieść do 5.3).

by the way, jezeli chcesz uzystac parenta w drzewkach IP wystarczy obiac wszystko od ostatniej kropki prawda ze proste?

kirkor: nie moze istniec dwa identyczne pathe, poniewaz cyferki to unikalne ID dla kazdej galezi

hmmm... a czy ja powiedziałem, że będą dwa identyczne pathe...

zainteresowałem się ostatnio trochę drzewkami i troszkę poszperałem. Może komuś przyda się:

http://forum.webcity.pl/index.php?act=ST&f=15&t=2461&st=0 Temat na WebCity o drzewkach.
http://www.intelligententerprise.com/00102...equestid=291501
http://www.zyxist.com/artykuly.php/drzewa_w_php_i_mysql

Osobiście uważam temat drzewka za trudny i zdradliwy, sam siedziałem około 10 dni nad stworzeniem własnego systemiku. Jeżeli ktoś jest zainteresowany, chętnie podzielę się doświadczeniami a nawet skrypcikiem.

Moje dzewko posiada:
- nie ogranoczoną ilość poziomów
- możliwość sortowania wewnątrz gałęzi
- mozliwość pełnego edytowania nazw w dowolnym miejscu
- możliwość usówania z uwzględnieniem zmian w sortowaniu

Nie ma natomiast:
- przenoszenia gałęzi
- usówania całych gałęzi

Pozdrawiam.
Zainteresowanych proszę o wiadomość na PRIVA

A nie lepiej byłoby podzielić się tym ze wszystkimi? Po to właśnie jest ta dyskusja.

ps: pisze się usuwania

Moja wersja drzewka robi wszystko co trzeba, przesuwa całe gałęzie, kasuje podgałęzie itd....
korzystam z trzech pól

Id, Id_parent, Order

ale wyświetlanie jest rekurencyjnami zapytaniami , co nie rozwiązuje probelmu tego temtatu.

Sam jestem ciekaw czy jest jakies sensowne rozwiazanie, jak jest to chetnie je zaimplementuje.

teles pełno, wystarczy poszukać

to ja proponuje:

[SQL] pobierz, plaintext 
SELECT * 
FROM tree WHERE LEFT(path, 2) = '1.' ORDER BY path.
[SQL] pobierz, plaintext 

powinno być szybciej niż LIKE

Uzywasz funkcji bazy danych?
Bo w php to juz nie bedzie rekurencja (przynajmniej taka sztuczna)

Zamiast Nested Sets polecam Nested Intervals. Odpada problem z wstawianiem. Linka kiedyś podawałem, potem zgubiłem, a całość jest trudna do zrozumienia i być może Oracle-only.

A w ogóle to można zostać przy ID parenta i zrobić CONNECT BY .

hawk, link jest w komentarzach do artykułu o drzewkach z wortalu
btw zyjesz ;D

Nested sets (zbiory zagnieżdżone) to ciekawy mechanizm nastawiony na mozliwie szybki odczyt drzewa. Dodawanie i modyfikowanie niestety wiaze sie z koniecznoscia aktualizacji indeksow przewaznie wiekszosci rekordow w tabeli. Nie objecie takich operacji transakcja grozi utrata spujnosci struktury.

Osobiscie eksperymentujac z ta metoda oprocz indeksow lewy i prawy zachowalem rowniez parent_id w celu ewentualnej rekurencyjnej odbudowy srtuktury. Dodalem tez pole level co ulatwilo mi wyswietlanie ograniczonej liczby zaglebien wybranej galezi. Dodalem tez pole position (mozna by je nazwac order) gdyz jego wartosc wskazuje na miejsce danego liscia lub galezi w ramach swojego poziomu. Dzieki temu wybiegowi zmiana pozycji w ramach poziomu wymaga jedynie aktualizacji wartosci position elementow tej samej galezi i na tym samym poziomie, a nie przebudowy calych indeksow lewy prawy. Poza tym w przypadku wystapienia niespojnosci struktury drzewa, ponowna przebudowa oparta o id, nie powoduje zmiany kolejnosci elementow w ramach poziomu

Na moim drzewie mozna:
- pobierac pojedynczy element, cale galezie,
- pobierac okreslona liczbe poziomow z drzewa lub wybranej galezi,
- pobierac przodkow wybranego elementu,
- pobrac przodkow o wybrana liczbe leweli w gore,
- dodawac nowe elementy,
- usuwac liscie i cale galezie,
- usuwac rodzica zachowujac jego potomkow,
- przesuwac liscie w ramach danego poziomu lub calego drzewa,
- przesuwac cale galezie w gore, dol, w prawo oraz w lewo
- odbudowac strukture drzewa w razie "powiklan"

Pisze artykul na ten temat (jakos nie mam czasu aby go dokonczyc) Jak mi uruchomia PHP5 na serwerze to wrzuce demo do przetestowania i dorzuce wspomniany artykul.

Mysle ze zrobilem fajny mechanizm jednak zdaje sobie sprawe z jego niedoskonalosci wynikajacych glownie ze wspomnianych juz wyzej trudnosci przy dodawaniu elementu lub modyfikacji struktury. Przy budowie np. forum o ograniczonej liczbie zaglebien, czestej aktualizacji tresci wybralbym raczej inne rozwiazanie - Drzewa Depesza, albo IP (tak na marginesie zastanawiam sie w polu jakiego typu w bazie trzymane sa id oraz sciezka danego elementu - w varchar czy raczej text?)
Co do zrzucania struktury drzewa do pliku to ja ograniczylbym sie jedynie (zresta podejrzewam, ze oto wlasnie chodzi) do zrzucenia id i parent_id i na tej podstawie konstruowal zapytanie do bazy danych.

Nie rozumiem trochę zastosowań drzewa. Jak w jednej tabeli można przechowywać zarówno newsy, jak i artykuły i bóg wie co jeszcze ? Przecież każdy z tych przykładów potrzebuje innych danych. Można by wprawdzie w drzewie dodać pole table mówiąze w jakiej tabeli znajduje się dany news, artykuł itp., ale mija się to z ideą drzewa :/

Newsy od artykułów, postów i komentarzy nie różnią się w brew pozorom, aż tak wieloma elementami. Każdy ma tytuł, treść, date dodania, autora itd. Osobiscie nie zdecydowalbym sie na trzymanie artow, newsow i postow w jednej tabeli, ale na przyklad tematy forum i posty jak najbardziej. Nie widze przeciwskazan do tego by zbudowac system newsow z podzialem na kategorie i komentarze i wszystko to trzymac w jednej tabeli.

Ja tam widze wiele zastosowan dla struktur drzewiastych np. artykuły - jak masz prosciutkie teksty to wrzucasz je jako pojedynczy artykuly, ale jakbys chcial opublikowac wieksza prace to podzial na rozdzialy, podrozdzialy, punkty przywoluje automatycznie na mysl strukture drzewiasta. Czym ze jest menu (mowa oczywiscie o bardziej rozbudowanym menu) jak nie struktura drzewiasta?

A dlaczego nie. Tabela z drzewem przechowuje jedynie najwazniejsze informacje wspolne dla wszystkich elementow drzewa, a pozostale informacje przechowywane sa juz w innych tabelach. Najczesciej bedziesz sie do nich odwolywal wybierajac konkretny element bo do przedstawienia drzewa zaleznosci calkowicie wystarcza informacje wspolne takie jak tytul.

moglbys ktos podrzucic jakas fajna klase do obslugi struktur drzewiastych zapisywanych w bazie mysql?

Ja publikowałem na forum jakiś szkic na forum.

Czy ktos probowal moze przesuwac wezly drzewka metoda depezowa dla MySQL-a < 4.1 Wrzucanie danych oraz wyswietlanie widze jest b. proste jednak jakikolwiek UPDATE zakrawa na hardcore

@NuLL: tak, ja - pokazywałem nawet działanie na forum lub ircu dawno temu (ponad 6 miesiecy). Niezoptymalizowane, nieprzemyślane napisane w ciągu 3 godzin oskryptowanie, twzorzyło, przenosiło, usuwało i kopiowało węzły i całe gałęzie - niestety podczas przeprowadzki do wrocławia kody gdzies się zapodziały.

Ogólnie nie było az tak źle, tylko zapytań troche duzo sie robiło... :/

Gorzej jesli chcesz policzyc ile znajduje sie elementów w tabeli np. newsy przypisanych do danej kategorii... i chcesz to wyswietlic kiedy przegladasz kategorie nadrzedne, czasami nawet przesuniete o kilka poziomów do góry?!