Witam

Mam zamiar napisać swój sklep jestem na etapie projektowania i problemem dla mnie jest drzewo kategorii. Jak wy rozwiązujecie ten problem drzewa z nieograniczoną ilością gałęzi i ich długości np. sklep.pl/coś/czegoś/ma/coś/ ?

Dobrze jest zbudować sobie strukturę na bazie danych opartej na 3 tabelach.
Kategoria, dział, referencje

w tabeli kategoria podajemy id i nazwe
dział id i nazwe
referencje powiązania kategoria-dział
lub kategoria - kategoria

W przypadku sklepu najlepszą według mnie metodą na ugryzienie drzewek jest Materialized Path. Z tą lekką modyfikacją: oprócz ścieżki składającej się z id kategorii warto dołożyć ścieżkę z całymi nazwami kategorii. W tym wypadku to małe odstępstwo od założeń normalizacji bardzo przyśpieszy zapytania typu: wyświetl 20 ostatnich produktów wraz z pełną ścieżka kategorii w której się znajdują (wystarczy jedno zapytanie ze złączeniem z tabelą kategorii z zachowaniem warunku produkty.kategoria_id = kategorie.id)

Minusem jest ograniczony stopień zagnieżdżenia kategorii, ale przyznam że nie widziałem sklepu który potrzebowałbym więcej niż 5 stopni zagnieżdżenia, a tu spokojnie możesz uzyskać kilkadziesiąt.

Ja bym zastosowal rekurencje prosta tabela kategori w sql id|nazwa|id_nadrzednej. Jak dodajesz podakategorie to w id_nadrzednej dodajesz ip bezposredniej nadkategorie potem tylko while i rekurencja

[PHP] pobierz, plaintext 
<?php
public function kategoria($id)
{
$zap = "SELECT * FROM kategorie WHERE id_nadrzednej=$id;";
$od = mysql_querry($zap);
while ($w = mysql_fetch_row($od))
		   {
		   print("<a href='index.php?kat=".$w[0]."'>".$w[1]."</a>");
		   kategori($w[2]);
		   }
}
?>
[PHP] pobierz, plaintext 

albo jakos tak bynajmniej tym sposobem wyswietlisz wszystkie kategorie odpowiedznio posortowane. Oczywiscie id zaczynasz od 1 a wszystki kategoriom glownym nadajesz id_nadrzednej 0.

@legorek: takich rzeczy się nie robi tudzież nie powinno się robić, usuwanie takiego schematu jak proponujesz nazywa się chyba normalizacją, w każdym razie z tego co mi wiadomo taka struktura jest niepożądana
zapewne przyspieszy trochę zapytanie "20 ostatnich", ale na pewno spowolni: "wybierz produkty z kategorii"

dalej patrząc wydaję mi się, że: większe sklepy nie korzystają z "ostatnich" bo kto to śledzi i kogo obchodzi co sklep wrzucił do asortymentu w którym jest już 50k produktów, raczej ich interesuję czy znajdą to co potrzebują czyli skakanie po kategoriach... (lub wyszukiwarka ale ta ma niewielki związek z kategoriami )

to takie moje luźne uwagi na ten temat

EDIT: @Grangu: rekurencja SQL... to zło tak w skrócie mówiąc

@wlamywacz: w archiwum Pro na forum jest topic z drzewkami sql... może się przydać
metody: metoda depesza, Materialized Path, Nested Sets, (chyba Nested Intervals), jeszcze jest np. metoda rekurencyjna aczkolwiek raczej niepolecana...

zimi, przeczytaj dokładnie to co napisałem: czasem warto świadomie zrezygnować z normalizacji na rzecz np szybkości wykonania zapytań.

Jeśli np. chcesz wyszukać produkty (powiedzmy 50) i wyświetlić ich pełne ścieżki kategorii, to w najlepszym (!) wypadku będziesz musiał wykonać 50 zapytań (a jeśli produkty mają wysoki stopień zagłębienia to nawet kilkaset zapytań).

Wyświetlenie produktów z danej kategorii sprowadza się też to jednego zapytania.

@legorek: przeczytałem dokładnie co napisałeś
wykonywanie zapytań w pętli bo zapewne o to Ci chodzi nie jest zbyt rozsądne
w zupełności wystarczą 3 zapytania i trochę php do wygenerowania struktury z której łatwo uzyskasz to czego potrzebujesz dla każdego liścia i z pewnością będzie wydajniejsze niż wykonywanie zapytania w pętli


połączyć wszystkie wyniki przecinkami

rozdzielenie ścieżek i połączenie przecinkami, ew. wywalenie powtarzających się identyfikatorów

wyniki zapisujemy w tablicy indeksowanej identyfikatorami kategorii i dorzucamy pole direct_parent

w ten sposób możemy rekurencją w php wyjąć bez żadnych problemów całą ścieżkę kategorii danego produktu
w bazie wszystko prawdopodobnie poleci po indeksie

moim zdaniem będzie bardzo ładnie śmigać

co do Twojego rozwiązania wyobraźmy sobie poziom zagłębienia 5 i w każdej kategorii 5 podkategorii: 5 + 5^2 + 5^3+ 5^4 + 5^5 = 3905 kategorii
załóżmy że każda kategoria ma ... znaków i tu pojawia się problem bo z tym może być różnie, np.:
Komputery
- Płyty główne
- Procesory
- Układy Pamięci
- Urządzenia peryferyjne

ale może być również:
Zwierzaki
- Koty
- Psy
- Węże
- Emo :P

Dla stronki którą ostatnio pisałem na nazwę kategorii przypada średnio (w sumie mega dużo :P) ~ 27,06 znaku, załóżmy że na kategorie przypada 10 znaków już razem z separatorem dla równego rachunku

bez indeksu musimy przejrzeć 4000 pól o długości do 50 znaków średnio zapewne między 40-50 znakami
dla standardowego rozwiązania średnio będzie już pewnie między 20-25 znakami
2 razy krótszy ciąg to prawdopodobnie 2 razy mniej czasu...

założenie indeksu 10 znakowego (indeksy zasadniczo powinny być krótkie) rozwieje zdecydowanie więcej wątpliwości dla drugiej metody
nie dość że prawdopodobnie wyłoni 5 razy mniej wyników (pierwsza rozpozna pierwszy poziom zagłębienia, druga wyłoni na pewno 2 poziomy), to do dalszego porównania zostanie dla pierwszej 30-40 znaków, dla drugiej 10-15 znaków

śmiem twierdzić że w ogólnym zarysie, gdzie wykonywane będą różnego typu zapytania, Twoja metoda będzie wolniejsza (szczególnie gdy wziąć pod uwagę przykład mojej strony gdzie na kategorie przypadało prawie 30 znaków...)

np. wybierz wszystkie dzieci danej kategorii... to będzie IMO masakra

PS. być może rzucam jakieś bezsensowne farmazony chętnie przeczytam jak ktoś mi wytknie jakąś głupotę, się czegoś nauczę , zasadniczo nie jestem specem wszystko co napisałem jest na podstawie mojego "zdrowego" rozsądku

Zrobiłem szybki test mojego rozwiązania:

3905 rekordów, 5 stopni, średnia długość nazwy kategorii: 32 znaki.

Wyświetlenie całego drzewa posortowanego alfabetycznie: 0.0335s (bez sortowania 0.024s)
Wyświetlenia Kategorii pierwszego poziomu i 4 poziomów dzieci posortowane alfabetycznie: 0.0027s
Wyświetlenie kategorii trzeciego poziomu i 2 poziomów dzieci posortowane alfabetycznie: 0.001s

To są średnie, każdy test wykonany kilka razy z zablokowanym cachowaniem.

Maszyna: Archaiczny P4 z 512 MB RAMu pracująca jako publiczny serwer webowy pod pełnym obciążeniem. MySQL 4 cośtam.

Jak dla mnie szybkość jest w porządku, a implementacja wyświetlania kategorii jest bajecznie prosta.

cóż, generalnie cała sprawa to chyba trochę dzielenie włosa na czworo,
musimy ustalić o czym rozmawiamy
jeśli o tym czy dane rozwiązanie będzie mulić... no to rzeczywiście biorąc pod uwagę Twoje testy prawdopodobnie nie, bo wydaję mi się, że rezultaty są przyzwoite
jeśli bierzemy pod uwagę optymalność rozwiązania to na miejscu byłoby przetestować również (nazwijmy je...) "moje" rozwiązanie i wyniki ze sobą porównać...

swoją modyfikacje argumentujesz tym że przyspiesza ona działanie, więc to że podasz wyniki które są dobre (swoją drogą wydają mi się aż za dobre, ale ja się nie bawiłem to nie wiem...) nie znaczy że rzeczywiście w ogólnym rozrachunku jest lepsze

bo na te wyniki można patrzeć dwojako nie mając porównania:
a ) rzeczywiście przyspieszyło i "widać" rezultaty (ładne czasy...)
b ) zmuliło... ale jeszcze nie tak żeby było niedopuszczalne...

rozumiem że test zrobiłeś w odpowiedzi na:

ja tutaj miałem na myśli że to będzie masakra w porównaniu z...

Tutaj chyba popełnie grzech zgłębiając temat, ale tak go delikatnie tknę...
jakby nie patrzeć obecne komputery, jak również te "archaiczne" są szybkie...
z tabelki którą znalazłem na angielskiej wikipedii:

z czego wynika że Pentium 4 Extreme Edition przy taktowaniu 3.2 GHz wykonywał niemal 10 mld operacji maszynowych w ciągu sekundy
tak więc mając 0,001s i nawet słabszego procka można trochę zdziałać...

więc Twoje wyniki mi dają mi teraz raczej informację: "mamy szybkie komputery" niż "cechą mojego rozwiązania jest jego wydajność"

ogólnie w swoich postach może troche przesadziłem... ale Twoje rozwiązanie i tak mnie nie przekonuję jak i nie podoba mi się

edit: @Grangu: to właśnie miałem na myśli pisząc "dzielenie włosu na czworo", choć

Skłania do trochę innego toku rozumowania... aczkolwiek się z Tobą zgadzam

3900 kategorii w sklepie internetowym?? To chyba troche wiecej niz sednio one maja. Takie rozwazania co jest bardziel optymalne sa moim zdaniem offtopiciem, przeciez kategorii raczej tyle nie bedzie, wiec nie wazne ktore wybierze rozwiazanie bo bedzie ono szybkie szybsze albo najszybsze.