[CMS] Drzewo kategorii - najlepszy sposób, pod względem wydajności i skomplikowania Opcje

[WebCM]

Potrzebuję wydajnego i niezbyt skomplikowanego sposobu na szybkie pobieranie danych o kategoriach - takiego, aby zmiana struktury kategorii nie była skomplikowana.

1. Pobranie wszystkich kategorii z podkategoriami i pogrupowanie ich
2. Pobranie tytułu i ID nadkategorii wyświetlanej kategorii (aby goście wiedzieli, gdzie się znajdują i mogli wrócić do wyższych kategorii). Aktualnie wywołuję osobne zapytania (jeżeli w ogóle jest potrzeba).
3. Pobieranie wszystkich podkategorii danej kategorii. Nie jest bardzo potrzebne, choć użyteczne (więc ostatecznie można pominąć).
4. Pobieranie podkategorii danej kategorii o 1 poziom niżej.
5. Wykonywanie operacji na gałęziach drzewa (choćby zmiana wartości pól, w tym "ilość zawartości")

Rozwiązanie powinno być zgodne z MySQL i SQLite (a w szczególności z MySQL). Tym bazom danych brakuje odpowiednich typów tabel bądź funkcji do takich celów. Niektóre czynności (np. sortowanie i grupowanie) ostatecznie może wykonać PHP. Tabela z kategoriami zawiera już 11 pól (a mogą dojść kolejne), więc wolałbym nie dodawać już nowych. Ostatecznie w grę wchodzi nowa tabela.

Aktualne rozwiązanie
Ważne pola w tabeli: ID | nazwa | wyższa kategoria

+ bardzo szybkie wyszukiwanie kategorii niższego poziomu i wyższego o 1 poziom
+ nieskomplikowana struktura (przy zmianach nie trzeba wykonywać innych czynności)

Rozwiązania problemów:

• Ad 1. Trzeba zastosować skomplikowane pętle, aby pogrupować kategorie (w PHP bądź SQL)
• Ad 2. Można zastosować pętlę w SQL-u bądź zostawić tak, jak jest (zazwyczaj nie powinno się tworzyć zbyt wielu poziomów).
• Ad 3. Podobnie jak wyżej.
• Ad 5. Teraz stosuję pętle w PHP i wykonuję wiele zapytań (dla zmiany ilości zawartości - tylko wtedy, gdy kategoria ma nadkategorie). Jeśli zastosowałbym pętle w SQL-u, trzeba by też dodawać wartości pól do zmiennej.

Przemierzanie drzewa (tree traversal, nested tree)
Ciekawa metoda, jednak prawdopodobnie nie da się pobrać wyższych kategorii przy pomocy 1 prostego zapytania do bazy. Doskonale się jednak sprawdza przy pobieraniu podkategorii.

Powiązania - metoda Depesza
Również ciekawe rozwiązanie - przy małej ilości poziomów rozmiar drugiej tabeli nie powinien urosnąć do kosmicznych rozmiarów. Niestety, więcej problemów jest przy zmianie struktury. Aby zmienić nadkategorię kategorii środkowego poziomu, zmiana powiązań dla child_id=ID to za mało - również należy wykonać tą czynność dla podkategorii (ale można je pobrać za 1 zapytaniem i z PHP złożyć kwerendę modyfikującą).

• Ad 1. Być może efekt można osiągnąć przez posortowanie kategorii wg: parent_id, depth, jednak mogę się mylić. Czy ktoś jest dobrze zaznajomiony z metodą powiązań i mógłby powiedzieć coś na ten temat?
• Ad 2,3,4,5. Raczej nie będzie problemu - lecz czy na pewno?

Indeksy w stylu adresu IP
Jeżeli kategoria ma subkategorię o ID 8, jej indeks to: 008.001 (ostatni człon to numer kolejności) bądź 008.

+ bezproblemowe i szybkie sortowanie i grupowanie kategorii

Pobieranie podkategorii i nadkategorii jest możliwe, lecz wymaga użycia operatora LIKE lub specjalnej funkcji, więc prawdopodobnie nie jest tak szybkie. Podobnie wykonywanie operacji (ad. 5.) opera się na tej samej zasadzie. Zmiana struktury może być kłopotliwa (ale nie musi) - trzeba pozamieniać podkategoriom indeksy.

Które z tych rozwiązań najlepiej nadaje się do podanych wyżej celów i nie jest uciążliwe przy modyfikacji struktury? Wymieńmy się doświadczeniami.

Ten post edytował WebCM 15.07.2007, 11:58:29

[menic]

No to jak z ta dyskusją ?

[WebCM]

Na końcu wybrałem nested sets, gdy przeczytałem więcej na ten temat. Wcześniej zacząłem implementować materialized path (IP), lecz przy sortowaniu występuje problem:
1.5.9 i 1.5.10 - który najpierw?

Teraz męczę się z przenoszeniem kategorii w Nested Trees. Jeśli macie namiary na gotowe algorytmy, piszcie.

Chyba, że są lepsze metody.

Ten post edytował WebCM 4.08.2007, 20:28:08

[menic]

No ja sie zabierałem i nie moglem sie zebrac. Az do dzisiaj. Przysiadlem porzadnie i napisalem Dziala wyswietlanie kategorii oraz ich dodawanie. Algorytm jest to przerobiona wersja depesza no i oczywiscie port na MySQL
Jak już skoncze calkowicie to nie omieszkam sie podzielić

Ten post edytował menic 8.08.2007, 21:40:16

[sf]

Osobiście używam tylko nested tree Ostatnią metodą jaką bym wybrał to coś w stylu bodowania stringu.

[cicik]

Ja też używam nested tree. Łatwo można na tym zrealizować wszystko co może być do szczęścia potrzebne. Znalazłem tylko jeden problem.
Na stronie http://www.phpriot.com/d/articles/php/appl...es-1/index.html jest opis algorytmu nested tree i aby wyświetlić cale drzewo to wykonujemy zapytanie select * from tabela order by nleft. Problem polega na tym, że nie mamy tutaj mozliwości wpływania na kolejność kategorii.
Nie możemy raz wyświetlać elementów posortowanych po nazwie a raz po jakiejś ustalonej przez usera kolumnie. Dla każdej opcji sortowania trzeba by mieć osobne pola nleft i nright.

[WebCM]

Potrzebuję skryptu, który ustawi automatycznie pola left i right na podstawie:

Kod

ID | ID wyższej kategorii

http://pastebin.4programmers.net/2953 - ta funkcja zajmuje się ponownym zapisem ilości pozycji w kategoriach. Czy dałoby się podpiąć tutaj również uaktualnianie tych pól? Funkcja:
- pobiera wszystkie kategorie z bazy
- liczy zawartość (I FOR)
- iteruje po każdej kategorii (II FOR)
--- wyszukuje "rodziców" i dodaje im swoją liczbę pozycji (WHILE)

Jeśli nie da się podpiąć tego, dobra będzie też osobna funkcja (a może nawet lepiej?). Tylko w jaki sposób napisać odpowiedni algorytm? Najlepiej, by nie wykonywał osobnego zapytania dla każdej kategorii jak w przykładzie na SitePoint. LEFT oznacza też kolejność (zapytanie do wyświetlenia listy kategorii zawiera: ORDER BY left), choć przebudowa ewentualnie może opierać się na tytułach (alfabetycznie).