struktura drzewa Opcje

[pero]

witam
mam taka tabele

kategoria
--------
id_kategoria (PK)
id_rodzica (FK)
nazwa

wiecie moze jak za pomoca jednego zapytania sql wyswietlic wysztkie podkategorie ktorych rodzicem jest kategoria o id=1 ?
szukalem na forum i zwykle ludzie pisza zeby drzewa a php obslugiwac. ja wolalbym to zalatwic w sql.
macie moze jakis pomysl jak to rozwiazac ?

pozdrawiam

[mike]

Poczytaj sobie o Nested Set Model. To da Ci odpowiedź.

[pero]

ten przyklad daje odpowiedz w przypadku gdy znam ilosc poziomow, ale co gdy poziomy dodawane sa dymamicznie i nie mam zalozone ze max ilosc poziomow wynosi 4 ?

[cafepl_com]

Osobiście używam takiego kodu (jeszcze ani razu mnie nie zawiódł):

[PHP] pobierz, plaintext 
<?php
function showSubCategories($cat_id, $dashes = ''){
    $dashes .= '----';
    $rsSub = mysql_query("SELECT * FROM tabela WHERE id_rodzica=" . $cat_id) or die(mysql_error());
    if(mysql_num_rows($rsSub) >= 1){
        while($rows_sub = mysql_fetch_array($rsSub)){
            echo '<li>'.$dashes.' '.$rows_sub['nazwa'].'</li>';
            showSubCategories($rows_sub['id_kategoria'], $dashes);
        }
    }
 
}
 
 
echo '<ul>';
$rsMain = mysql_query("SELECT * FROM tabela WHERE id_rodzica=0") or die(mysql_error());
if(mysql_num_rows($rsMain) >= 1){
    while($rows_main = mysql_fetch_array($rsMain)){
    echo '<li>-- '.$rows_main['nazwa'].'</li>';
        showSubCategories($rows_main['id_kategoria']);
    }
}
    echo '</ul>';
?>
[PHP] pobierz, plaintext 

Pozdrawiam.

[ayeo]

Witam!

W bazie trzymaj, id elementu, id rodzica, ścieżkę, i level. Podam przykład:

id parent path level name
1 0 0 0 główny
2 1 1 1 pierwszy poziom
3 2 1.2 2 drugi

Level to w sumie ilość kropek w ścieżce + 1 więc nawet nie musisz tego trzymać. Całą gałąź pobierasz przez LIKE. Na przykład gałąź od elementu id 2: path LIKE 2% Oczywiście musisz używać CONCAT, żeby dodawać kropki przed i po ścieżce bo Ci złapie trochę "nie tych" elementów.

Ścieżka w bazie 1.2.3
CONCAT('.', path, '.') LIKE .1.2.3.% OR path = 1.2.3

Jest to sposób banalny w implemantacji. Wszystkie operacje (dodawanie, przenoszenie całych gałęzi, usuwanie gałęzi...) są proste i przyjemne. Rozwiązanie jest nawet, można powiedzieć, wydajne


Pozdrawiam!

[kbsucha]

ayeo jak to własnie jest z wydajnościa tej metody, bo ogólnie LIKE nie jest uważany za najszczęśliwsze rozwiązanie dla bazy?

pozdr

[ayeo]

LIKE jest ok, gorzej z REGEXpami. Kwestia dobrych indexów wydaje mi się. Trzeba by zrobić testy.

[dr_bonzo]

LIKE "asdasd%" skorzysta z indeksu - bo poczatek stringa jest znany, i przegladamy tyko stringi zaczynajace sie na "asdasd", a ze mamy jes poukladane to szybko sie do nich dostaniemy
LIKE "%adasdasd" nie skorzysta - poczatek stringa nie jest znany, wiec musimy przejrzec cala tabele

[Black-Berry]

Wszystko pięknie ale co jeśli chcemy przenieść kawałek drzewa w inne miejsce? Wtedy trzeba zmienić wartość 'path' dla każdego węzła i wydaje mi się, że nie będzie to wtedy prosta sprawa prawda? Przy zastosowaniu left_node, right_node też nie ma łatwo ale jak się dobrze pokombinuje to można każdą operację (typu add, remove, update, move, copy) wykonać w 1-3 zapytania (a przynajmniej w liczbie nierosnącej przy wzroście ilości węzłów).

Ma ktoś większe (albo chociaż mniejsze) doświadczenie z drzewami? Jakiej metody używacie?

Ten post edytował Black-Berry 10.11.2008, 09:58:02

[ayeo]

@Black-Berry, a co za problem? Jednym zapytaniem robisz UPDATE i tyle...

Przykład:
1.2.3.4.5 - Mama
1.2.3.4.5.6. - Jaś
1.2.3.4.5.7 - Kubuś

10.11 - Inna mama

Przenosimy element o id 5 do elementu o id 11. W ścieżce w bazie nie ma id elementu (czyli path Mama = 1.2.3.4). Robimy UPDATE wszystkich elementów z path 1.2.3.4.5% (szczegóły wyżej, trik z CONCAT), zamieniając w path 1.2.3.4 na 10.11. Jedno zapytanie, nie widzę problemu...

Pozdrawiam!

[Black-Berry]

Fakt, nie pomyślałem o CONCAT. Sposób wydaje się nie mieć wad poza wydajnościowymi. Może ma ktoś dokładne wyliczenia co? Jak to się ma do sposobu z left, right?

[tomek_]

sam ostatnio miałem problem ze struktura drzewiastą w MySQL-u 

wszystko da się załatwić dzięki procedurom składowanym

tu link do topiku http://forum.php.pl/index.php?showtopic=106515&st=0

w linku który dostałem w odpowiedzi jest kilka fajnych przykładów jak sobie z tym poradzić 

Ten post edytował tomek_ 17.11.2008, 14:47:12

[Zyx]

Algorytm przechodzenia drzewa zmodyfikowaną metodą preorder. Każdemu wierszowi przyporządkowujesz dwie unikalne liczby: left i right o następujących własnościach:

1. Dla każdego węzła left < right
2. Dla każdego potomka Y węzła X zachodzą warunki Y.left > X.left, Y.left < X.right, Y.right > X.left, Y.right < X.right (czyli wartości left, right potomków zawierają się w przedziale left-right węzła X).

Wyświetlenie takiego drzewka to kwestia dwóch zapytań, analogicznie bardzo łatwo można odpowiadać na sporo pytań dotyczących danego drzewa (ścieżka do korzenia, ilość potomków itd.), lecz zarządzanie danymi jest już nieco skomplikowane.

Opis algorytmu można znaleźć tutaj: http://artykuly.zyxist.com/czytaj.php/drzewa_w_php_i_mysql

Osobiście dodatkowo dorzucam do tego pole parent_id, które pozwala na pobranie dzieci danego węzła oraz prostsze określenie rodzica.

[Black-Berry]

no tak, insert w przypadku nested tree jest prosty. Ktoś próbował, przenoszenie gałezi, usuwanie i zmianę pozycji węzła? Moze ma ktos kompletną bibliotekę którą mógłby się podzielić. Chcętnie też nawiązałbym współpracę z kimś kto chciałby taką klase stworzyć na spółkę.

[Zyx]

Próbowałem i zrobiłem:
- usuwanie jest proste - odwrotność dodawania. Zamiast robić dziurę na nowy węzeł, po prostu wycinasz nowy węzeł i kasujesz po nim dziurę w numeracji.
- zmiana kolejności dzieci w obrębie tej samej gałęzi, przenoszenie - to jest już bardziej skomplikowane, gdyż zapytań jest tam trochę, ale po rozrysowaniu sobie, jak zamieniać które wartości, da się napisać. Szczegółów w tej chwili nie pamiętam - musiałbym do kodu zajrzeć i prześledzić, jak to się tam robi.

Niestety biblioteki nie mogę Ci udostępnić, ponieważ jest to integralna część stworzonego jakiś czas temu CMS-a. Za to, o ile dobrze pamiętam, Doctrine posiada wbudowane ogólne wsparcie dla tego typu struktur. Jeśli chciałbyś to jednak pisać samemu, dam jeszcze na wszelki wypadek dobrą radę: transakcje są obowiązkowe .