Aplikacje internetowe

Bełdziowe spojrzenie na aplikacje internetowe

Drzewka

Jako, że null i cojack wywołali mnie do tablicy postanowiłem opisać prostą, ale za to bardzo skuteczną metodę tworzenia drzew z wykorzystaniem mySQL. W przeciwieństwie do użycia rekurencji poniższy sposób ogranicza się do wykorzystania jednego zapytania SQL.

Przyjmijmy, że chcemy stworzyć drzewko opisujące powiązania między pojazdami prezentujące się następująco

Pojazdy
   Motory
      Ścigacze
      Crossy
   Samochody
      Osobowe
         Ładne
         Szybkie
      Ciężarowe
         Czarne
         Czerwone

Dla prostszego zobrazowania powyższych relacji posłużymy się następującym diagramem.

Przedstawienie hierarchi w postaci zbioru

Zrozumienie powyższego diagramu jest kluczem do zrozumienia opisanego sposobu tworzenia drzewek. Jak widać przedstawiliśmy na nim nasze drzewo w postaci zbioru. Każda strona zbioru została oznaczona kolejnymi liczbami, które są jego granicami. Znając je możemy łatwo wyznaczyć podzbiory czyli podkategorie elementu wybierając rekordy, które zawierają się w jego granicach. Prześledźmy to na przykładzie.

Wiedząc, że granice zbioru Osobowe to odpowiednio 9 i 14 możemy pobrać elementy, których lewa granica zawiera się w przedziale (9,14).

SELECT name 
FROM vehicles 
WHERE `left` BETWEEN 10 AND 13
ORDER BY `left`;

Powyższe zapytanie zwróci nam dwa rekordy:

+---------+
| name    |
+---------+
| Ładne   |
| Szybkie |
+---------+

Chcąc pobrać całe drzewo z uwzględnieniem hierarchii należy pobrać wszystkie dane posortowane wg kolumny left, a następnie podczas wyświetlania dodawać wcięcia bazując na wartości kolumny level określającej poziom zagłębienia. Aby wyświetlić nasze drzewko korzystając tylko z jednego zapytania SQL możemy posłużyć się następującym kodem:

SELECT CONCAT( REPEAT( ' ', level * 5 ), name ) as name
FROM vehicles
ORDER by `left`;

wynikiem, którego będzie

+-------------------------+
| name                    |
+-------------------------+
| Pojazdy                 |
|      Motory             |
|           Ścigacze      |
|           Crossy        |
|      Samochody          |
|           Osobowe       |
|                Ładne    |
|                Szybkie  |
|           Ciężarowe     |
|                Czarne   |
|                Czerwone |
+-------------------------+

Dodanie nowego rekordu do tabeli wiąże się z koniecznością wykonania dwóch operacji:

  • 1.Pobranie wartości prawej granicy (wartość kolumny right) rodzica.
  • 1.Aktualizacja granic elementów o granicach równych lub większych nowo wstawionemu rekordowi.

Chcąc dodać nowy samochód osobowy (prawa granica = 14) należy wykonać następujące zapytania:

UPDATE `vehicles` SET `left` = `left` + 2 WHERE `left` >= 14;
UPDATE `vehicles` SET `right` = `right` + 2 WHERE `right` >= 14;

INSERT INTO vehicles VALUES( 'Kolorowy', 14, 15, 3 );

Dzięki aktualizacji granic mamy pewność, że pobranie elementów zawierających się w wybranej kategorii zawsze zwróci aktualne dane.

Przydatne linki


Tagi: , , , ,
Kategoria: Inne, Bazy danych


15 komentarzy

  1. Szymon Perski napisał(a):

    Witaj,

    Ciekawy artykuł. Bardzo dobrze ze są ludzie którzy dziela sie taką wiedzą :)

    Mam jednak pewien problem wykorzystywalem juz takie rozwiazanie kilka razy, w szczegolnosci do tworzenia struktury kategorii. Za kazdym razem kiedy tworzylem tabele ktora zawierala wlasciwe dane np. ogloszenia, produkty itp. nie wiedzialem jak stworzyc strukture tej tabeli, tak aby bez problemu z kazdego poziomu przegladania kategorii wyswietlac wszystkie rekordy ktore znajdowaly sie w danym miejscu drzewa i przy okazji podliczyc ile znajduje sie w danym miejscu rekordow lacznie z tymi ktore moga byc ewentualnie przypisane nizej.

    Np.

     Aparaty ( 10 )
       Cyfrowe ( 5)
          Canon ( 2 )
          Sony ( 3 )
       Lustrzanki ( 5 )
          Nikon ( 3 )
          Canon ( 2 )
    

    Zatem pytanie jest nastepujace jakie pola powinna zawierac w takim przypadku tabela z produktami, oraz jak to ugryzc w MySQL :)

  2. Michał Ławicki napisał(a):

    a widzisz :) miałem podpiąc zrzut bazy i zapomniałem :) notka zaktualizowana :)

    jeśli chodzi o ilość elementów w kategorii to uzyskasz ją poprzez leftright – 1

  3. Tutaj pełniejsze rozwinięcie tematu: http://www.sitepoint.com/article/hierarchical-data-database/ które nie korzysta z kolumny level, która stwarza dodatkowe problemy podczas aktualizacji poziomu zagłębienia danego elementu, szczególnie gdy zawiera on jakieś podkategorie.

  4. Szymon Perski napisał(a):

    Ok, dzieki :)

  5. Jakie problemy? Podczas dodawania elementu pobieramy wartość prawej granicy tak więc wystarczy pobrać dodatkowo level i zwiększyć go i 1 :) i już nie ma problemów :)

  6. Szymon Perski napisał(a):

    Beldzio odpowiedziales mi jak policzyć elementy które znajduja sie w drzewku…

    Ale powiedzmy jak mamy moja strukture np.

    Aparaty ( 10 ) -> 10 rekordow w tabeli produkty
    Cyfrowe ( 5) -> 5 rekordow w tabeli produkty
    Canon ( 2 ) -> 2 rekordy w tabeli produkty
    Sony ( 3 ) -> itd
    Lustrzanki ( 5 )
    Nikon ( 3 )
    Canon ( 2 )

    Zatem pytanie, jest takie, jesli mamy dwie tabele odopowiedzialne za strukture drzewka i trzecia tabele ktora przechowuje wpisy docelowe pogrupowane wg drzewka to jaką powinna miec strukture?

    Podejrzewam ze samo id danej kategorii nie bedzie wystarczy a moze nawet nie bedzie potrzebne?

    Ty natomiast odpowiedziałeś mi, jak policzyć ilość elementow drzewka a o to mi nie chodzilo?

    Jeśli mógłbyś nakreślić temat tego o co pytam to byłbym rad, ewentualnie moze jest jakies inne rozwiązanie mojego problemu?

    Z góry dzięki i pozdrawiam,

    SP.

  7. mało napisałeś o danych jakie zawierają tabele, ale jeśli założymy ze każda z kategorii posiada artykuły to najprościej będzie zrobić 2 tabele

    1. zawierająca kategorię czyli drzewko wg struktury, którą zamieściłem w pliku
    2. zawierającą artykuły z dodatkowym polem zawierającym identyfikator kategorii – zakładając że jeden artykuł należy tylko do jednej kategorii

    jeśli nadal źle celuję to opisz troszkę dokładniej problem :)

    B.

  8. Cześć,

    Świetny tekst, naprawdę.

    A jaki masz prosty algorytm na zamiane kolejność samochodów z motorami ?

  9. akurat nad tym się jakoś mocno nie zastanawiałem :-) ale można to zrobić tak:

    1. lewa granica kategorii motory = prawa granica samochodow + 1 – czyli 22
    2. różnica między starą, a nową lewą granicą motorów to 22 – 2 = 20
    3. do granic podkategorii motorów dodajemy wyżej obliczoną różnice
    4. aktualizujemy granicę rodzica

    tak na szybko ;-)

  10. Nie jestem pewien, ale w przypadku dodawania nowego rekordu najpierw należy zrobić UPDATE/Przesunięcie kolumn, a dopiero potem zrobić INSERT.

    Jeśli zrobimy tak jak teraz jest pokazane, najpierw dodamy left14 po czym zaraz updatem zmieniamy mu na 16 … przez co powstaje tak jakby „dziura” … ale mogę się mylić :)

  11. oczywiście masz rację :) już poprawiam :)

  12. A ja mam pytanko odnośnie innej kwestii ;)
    Powiedzmy, że chcę wykorzystać taką strukturę kategorii dla sklepu internetowego, gdzie muszę mieć możliwość ustalenia aktywności danego zbioru i/lub podzbiorów czyli odłączam np. samochody a osobowe i ciężarowe nie są widoczne. Co wtedy? Osobna tabela w bazie dla aktywnych?

  13. wystarczy dodatkowa kolumna informująca o widoczności

  14. Pomimo że stworzyłeś tak wspaniały zbiór graficznie, mało był dla mnie zrozumiały i tak po twoim kursie musiałem doszukać informacji.
    Kurs świetny ale dla bardziej obytych w temacie. http://www.eioba.pl/a130/drzewa_w_php_i_mysql
    Fajnie jak byś umieścił taki obrazek jak jest na tamtej stronie z elementami.

    Od razu mi rozjaśniło sytuacje.

  15. jakby nie patrzeć to w notce jest taki sam graf jak na eiobie tyle, że w innej postaci :) imho bardziej zrozumiałej :)

Dodaj komentarz