Nie wiem, czy ten temat nadaje się tutaj, czy na Pro. Na wszelki wypadek umieściłem go w "php", żeby nie narazić się na ewentualną krytykę ;)
Nie znalazłem rozwiązania mojego problemu tutaj na forum. W zasadzie rozwiązań mam kilka, ale nie wiem, które z nich jest najlepsze, czytaj: najbardziej wydajne.
Problem polega na zliczaniu ilości elementów w każdym węźle dowolnie zagnieżdżalnego drzewa kategorii.
Struktura wygląda w uproszczeniu tak:
[sql:1:9ec233cd06]# Tabela kategorii.
create table kategorie (
id_kategorii int not null auto_increment primary key,
id_rodzica int,
nazwa text);
# Tabela elementow.
create table elementy (
id_elementu int not null auto_increment primary key,
id_kategorii int,
nazwa text);[/sql:1:9ec233cd06]
Docelowo kategorii będzie niewiele, natomiast elementów będzie bardzo dużo. Kategorie mogą być dowolnie zagnieżdżone, co umożliwia zdefiniowana powyższej struktura.
Następujący wpis w tabeli kategorie:[sql:1:9ec233cd06]insert into kategorie(id_kategorii, id_rodzica, nazwa) values(1, 0, 'kat')[/sql:1:9ec233cd06]oznacza, że kategoria o nazwie "kat" znajduje się na najwyższym poziomie drzewa (id_rodzica=0) i nie ma przodków, natomiast taki wpis: [sql:1:9ec233cd06]insert into kategorie(id_kategorii, id_rodzica, nazwa) values(2, 1, 'podkat')[/sql:1:9ec233cd06]oznacza, że kategoria o nazwie "podkat" znajduje się w podkategorii "kat" (id_rodzica=1).
Następujący wpis w tabeli elementy[sql:1:9ec233cd06]insert into elementy(id_elementu, id_kategorii, nazwa) values(1, 2, 'elem')[/sql:1:9ec233cd06]oznacza, że element o nazwie "elem" znajduje się w kategorii o numerze 2.
Problem zliczania kategorii polega na tym, żeby policzyć wszystkie elementy znajdujące się w danej kategorii i we wszystkich jej podkateriach, we wszystich podkategoriach podkategorii itp.
Mówiąc dalej "potomkowie", mam na myśli wszystkich potomków węzła, a więc bezpośrednich (dzieci) i niebezpośrednich, czyli "A jest potomkiem węzła B", jeśli w drzewie istnieje gałąź (droga) prowadząca z "A" do korzenia drzewa i przechodząca przez "B".
Analogicznie będę rozumiał słowo "przodkowie" = przodkowie bezpośredni (ojcowie) i niebezpośredni.
Sposób I. Rekurencja.
To jest oczywiste - mając kategorię, posuwamy się w dół drzewa, przeglądając jej potomków i sumując liczbę elementów w kategorii i jej potomkach.
Plusy:
+ łatwość implementacji,
+ przejrzystość,
+ niezależność od operacji dodawania/usuwania/edycji elementów.
Minusy:
- spadek wydajności (wzrost liczby zapytań do bazy) przy bardzo dużej liczbie elementów,
- jest to metoda zachłanna: w przypadku wyświetlania listy wszystkich kategorii, za każdym razem konieczne jest przetwarzanie poddrzewa, które wcześniej być może zostało już przetworzone. Można tego uniknąć, stosując tablicę dotychczas przetworzonych poddrzew.
Sposób II. Pamiętanie liczby elementów w każdej kategorii.
Można do tabeli `kategorie' dodać pole `liczba_elementow', która zawiera liczbę elementów w kategorii i jej potomkach. Przy każdym dodaniu/usunięciu elementu zwiększana/zmniejszana jest liczba elementów w kategorii tego elementu oraz we wszystkich przodkach tejże kategorii.
Plusy:
+ bardzo duża wydajność zapytań przy przeglądaniu elementów i drzewa kategorii,
+ łatwość formułowania zapytań do drzewa kategorii.
Minusy:
- elementy mają dodatkowe parametry, takie jak "ukryty", co także jest uwzględniane przy liczeniu elementów. Każda zmiana tego parametru wymaga zmiany liczby elementów w kategoriach.
Sposób III. Grupowanie.
Za każdym razem, kiedy szukamy liczby elementów w kategorii, wywołujemy zapytanie:[sql:1:9ec233cd06]select k.id_kategorii as kat, k.id_rodzica as rodzic, count(e.id_elementu) as liczba from elementy as e, kategorie as k where e.id_kategorii = k.id_kategorii group by kat order by kat desc[/sql:1:9ec233cd06]Otrzymamy listę "trójek": (id kategorii, id rodzica, liczba elementow) uporządkowaną malejąco względem id kategorii. Porządek ten zakłada, że element "wyżej" nie może być rodzicem elementu "niżej".
Następnie (np. w php) przetwarzamy otrzymaną listę "od góry", dodając liczby elementów w kolejnych kategoriach do kategorii "poniżej", będących rodzicami kategorii aktualnie przetwarzanych w iteracji:[php:1:9ec233cd06]// $arr - tablica "trojek".
$elem = array();
foreach ($arr as $a)
{
// Liczba elementow w aktualnej kategorii.
if (isset($elem[$a['kat']))
$elem[$a['kat']] += $a['liczba'];
else
$elem[$a['kat']] = $a['liczba'];
// Liczba elementow u rodzica aktualnej kategorii.
if (isset($elem[$a['rodzic']])
$elem[$a['rodzic']] += $elem[$a['kat']];
else
$elem[$a['rodzic']] = $elem[$a['kat']];
}[/php:1:9ec233cd06]Otrzymamy tablicę asocjacyjną, w której kluczami będą id kategorii, a wartościami - liczba elementów w kategorii.
Plusy:
+ trywialność implementacji,
+ metoda dynamiczna.
Minusy:
- konieczność liczenia elementów we wszystkich kategoriach, nawet jeśli chodzi nam tylko o jedną lub niektóre kategorie,
- możliwy spadek wydajności przy bardzo dużej liczbie zapytań (czy aby na pewno?).
Wydaje mi się, że przy zastosowaniu sposobu I może drastycznie spaść wydajność zapytań, natomist II sposób wymaga stałej kontroli liczby elementów w kategoriach, co utrudnia usuwanie elementów np. bezpośrednio z bazy, jeśli zajdzie taka potrzeba. Sposób III jest najbardziej intuicyjny i trywialny, ale zastanawiam się nad jego wydajnością. Warto też wziąć pod uwagę fakt, że dodawanie/usuwanie/edycja elementów odbywa się zdecydowanie rzadziej niż ich przeglądanie, co działa na korzyść sposobu II.
Będę wdzięczny za wszelkie opinie i komentarze, a zwłaszcza inne pomysły rozwiązania tego problemu :) Zależy mi przede wszystkim na wydajności.