Loading:


Tworzenie struktury drzewa w PHP i MySQL

Wprowadzenie

 

Hierarchiczne, lub inaczej drzewiaste struktury znakomicie nadajÄ… siÄ™ do porzÄ…dkowania wielopoziomowych danych. Każdy element znajdujÄ…cy siÄ™ wewnÄ…trz nich posiada tzw. "rodzica" bÄ™dÄ…cego elementem nadrzÄ™dnym. JednoczeÅ›nie on sam może posiadać dowolnÄ… ilość podelementów. Podobnie dziaÅ‚a system plików w systemach operacyjnych. Jest jeden centralny wÄ™zeÅ‚ zwany korzeniem, a wewnÄ…trz niego znajdujÄ… siÄ™ pliki i katalogi. Te drugie mogÄ… zawierać kolejne pliki i katalogi i tak w nieskoÅ„czoność (w teorii).

Niestety jÄ™zyk SQL wykorzystywany do komunikacji ze wszystkimi najpopularniejszymi systemami baz danych (Oracle, MySQL, PostgreSQL itd.) nie zawiera dosÅ‚ownie żadnych mechanizmów pozwalajÄ…cych na szybkÄ… i efektywnÄ… implementacjÄ™ drzew. Normalny programista zrobiÅ‚by tak, jak podpowiada logika, tj. utworzyÅ‚ w tabeli pole "parent_id" przechowujÄ…ce identyfikator elementu nadrzÄ™dnego. Zgoda, tyle że czas potrzebny na wyÅ›wietlenie takiego drzewa jest niezwykle dÅ‚ugi. JÄ™zyk SQL nie zezwala na utworzenie zapytaÅ„ rekurencyjnych, zatem dla każdego odgałęzienia i każdego poziomu musimy wywoÅ‚ać osobne zapytanie. Im wiÄ™ksze drzewo, tym wiÄ™cej siÄ™ ich wysyÅ‚a i tym wolniej wszystko dziaÅ‚a. A tego przecież nie chcemy, prawda?

SurfujÄ…c po sieci trafiÅ‚em jednak na bardzo dobre ominiÄ™cie tego problemu. Zaimplementowane tym sposobem drzewo można wyÅ›wietlić w caÅ‚oÅ›ci jednym tylko zapytaniem bez wzglÄ™du na jego rozmiar oraz ilość rozgałęzieÅ„. W dodatku korzysta ono z podstawowych elementów jÄ™zyka SQL, co gwarantuje jego idealne dziaÅ‚anie na wszystkich bazach danych potrafiÄ…cych solidnie go obsÅ‚użyć.

Na czym polega sztuczka? Otóż wystarczy nasze drzewo... rozpÅ‚aszczyć i utworzyć miÄ™dzy wÄ™zÅ‚ami drogÄ™ w taki sposób, jak pokazaÅ‚em na rysunku. Jeżeli znasz siÄ™ na algorytmice, prawdopodobnie już zauważyÅ‚eÅ›, że opisywany tutaj sposób jest niczym innym, jak implementacjÄ… metody przechodzenia przez drzewa metodÄ… preorder, tyle że zaimplementowanÄ… w MySQL'u.


Po co te liczby? To jest klucz do sukcesu. Do każdego wÄ™zÅ‚a dodajemy dwa pola: left oraz right. Na rysunku ich wartoÅ›ci obrazujÄ… wÅ‚aÅ›nie liczby znajdujÄ…ce siÄ™ po lewej (left) oraz prawej (right) stronie danego elementu. Jak je dobrać? Jeżeli dany element nie zawiera żadnych podelementów, wtedy right jest wiÄ™ksze o 1 od left. W przeciwnym wypadku różnica miÄ™dzy nimi musi być taka, aby pomieÅ›ciÅ‚y siÄ™ miÄ™dzy nimi analogiczne wartoÅ›ci we wszystkich podwÄ™zÅ‚ach. Zobaczmy, jak to jest na rysunku: wÄ™zeÅ‚ "Fabryka" nie zawiera podelementów, dlatego opisaliÅ›my go liczbami 3,4. Zawarty on jest w węźle "PrzemysÅ‚owe" opisanym jako 2,5. PomiÄ™dzy 2 i 5 mieÅ›ci siÄ™ 3,4 i stÄ…d wiemy, że "Fabryka" leży w "PrzemysÅ‚owem". Zauważmy też kolejnÄ… rzecz: jeÅ›li dwa wÄ™zÅ‚y leżą na tym samym poziomie w tej samej gałęzi, wtedy po wartoÅ›ciach left i right możemy okreÅ›lić kolejność ich poÅ‚ożenia. Na rysunku obrazuje to gałąź "Publiczne" z "BibliotekÄ…" i "KoÅ›cioÅ‚em".

Zatem left i right wyznaczajÄ… swym zakresem pewien "pojemnik" dla wszystkich wÄ™zÅ‚ów potomnych, ich wÄ™zÅ‚ów potomnych itd. Takie podejÅ›cie do problemu sprawia, że możemy zaimplementować nasze drzewo tak, jak chcemy. Nie korzystamy z żadnych niestandardowych rozszerzeÅ„ jÄ™zyka SQL, a caÅ‚e drzewo da siÄ™ wyÅ›wietlić jednym zapytaniem.

Przejdźmy do kodowania. Na początek struktura naszej tabeli oraz dane testowe:


CREATE TABLE `drzewko` (
`id` int(8) NOT NULL AUTO_INCREMENT,
`nazwa` varchar(32) collate utf8_polish_ci NOT NULL DEFAULT '',
`left` int(8) NOT NULL DEFAULT '0',
`right` int(8) NOT NULL DEFAULT '0',
PRIMARY KEY (`id`),
KEY `parent` (`left`),
KEY `right` (`right`)
);

INSERT INTO `drzewko` VALUES (1, 'Budynki', 1, 22);
INSERT INTO `drzewko` VALUES (2, 'Przemyslowe', 2, 5);
INSERT INTO `drzewko` VALUES (3, 'Publiczne', 6, 11);
INSERT INTO `drzewko` VALUES (4, 'Mieszkalne', 12, 21);
INSERT INTO `drzewko` VALUES (5, 'Fabryka', 3, 4);
INSERT INTO `drzewko` VALUES (6, 'Biblioteka', 7, 8);
INSERT INTO `drzewko` VALUES (7, 'Kosciol', 9, 10);
INSERT INTO `drzewko` VALUES (8, 'Domy', 13, 18);
INSERT INTO `drzewko` VALUES (9, 'Blok mieszkalny', 19, 20);
INSERT INTO `drzewko` VALUES (10, 'Dom jednorodzinny', 14, 15);
INSERT INTO `drzewko` VALUES (11, 'Dom wielorodzinny', 16, 17);


Aby wyświetlić drzewko, potrzebne są nam tylko dwa zapytania:


# Pobierz parametry left i right dla elementu, od
ktorego zaczac wyswietlanie
SELECT `left`, `right` FROM drzewko WHERE id='1'


# Wyswietl drzewo, za @left i @right wstawiajac
dane z poprzedniego zapytania
SELECT `nazwa`, `left`, `right` FROM drzewko
WHERE `left` BETWEEN @LEFT AND @RIGHT ORDER BY `left`


Tak oto otrzymujemy listÄ™ podelementów uÅ‚ożonÄ… już od razu w odpowiedniej kolejnoÅ›ci. Jednak aby przypominaÅ‚a ona choć trochÄ™ drzewo, potrzebny jest nam jeszcze odpowiedni skrypt, który zrobi użytek z drugiego parametru, right. Przy wyÅ›wietlaniu każdego elementu bÄ™dziemy go odkÅ‚adać na stos, który na samym poczÄ…tku pÄ™tli jest "przycinany" do czasu, gdy zawarte w nim wielkoÅ›ci bÄ™dÄ… mniejsze od wartoÅ›ci right aktualnie obrabianego wÄ™zÅ‚a. W ten sposób wielkość stosu zawsze bÄ™dzie wskazywaÅ‚a na poziom jego zagłębienia. Poniżej przedstawiam funkcjÄ™ rysujÄ…cÄ… takie drzewko opisanym tu sposobem:


<?php
function displayTree($root)
{
// pobierz parametry glownego wezla
$r = mysql_query('SELECT `left`, `right` FROM
drzewko WHERE id=\''.$root.'\'');
if($row = mysql_fetch_assoc($r))
{
$right = array();
// wyswietl wezly
$r = mysql_query('SELECT `nazwa`, `left`,
`right` FROM drzewko WHERE `left`
BETWEEN \''.$row['left'].'\' AND
\''.$row['right'].'\' ORDER BY `left`');
while($row = mysql_fetch_assoc($r))
{
// czysc stos
if(count($right) > 0)
{
while($right[count($right)-1] < $row['right'])
{
array_pop($right);
}
}
// wyswietl element
echo str_repeat('| ',count($right))."\n";
if(count($right) - 1 > 0)
{
echo str_repeat('| ',
count($right) - 1).'+- '.
$row['nazwa']."\n";
}
else
{
echo '+- '.$row['nazwa']."\n";
}
// zloz jego parametr 'right' na stos
$right[] = $row['right'];
}
// wszystko jest OK
return 1;
}
// tere fere, nie ma takiego wezla
return 0;
} // end displayTree();
?>


Dodawanie elementów wymaga wykonania trochÄ™ wiÄ™kszej pracy, niż w normalnie, ponieważ potrzebne sÄ… aż cztery zapytania. Gdy bowiem dodamy nowy wÄ™zeÅ‚, trzeba przesunąć w górÄ™ wartoÅ›ci "left" i "right" wszystkich pozostÅ‚ych leżących w dalszej części naszej drogi. Oto zaczÄ…tek funkcji sÅ‚użącej do tego celu:


<?php
function createNode($id, $title)
{
// zablokuj innym dostep do tabeli, aby sie nic nie pokopalo
mysql_query('LOCK TABLES `drzewko` WRITE');
$r = mysql_query('SELECT `left`, `right`
FROM drzewko WHERE id=\''.$id.'\'');
if($row = mysql_fetch_assoc($r))
{
$left = $row['left'];
$right = $row['right'];
}
else
{
// nie znaleziono elementu
// nadrzednego, zacznij nowe drzewo
$left = 0;
$right = 1;
}

// przesun wartosci parametrow nastepnych wezlow o 2
mysql_query('UPDATE drzewko SET `right`=`right`+2
WHERE `right` > '.($right-1));
mysql_query('UPDATE drzewko SET `left`=`left`+2
WHERE `left` > '.($right-1));

// dodaj nowy element
mysql_query('INSERT INTO drzewko (`nazwa`, `left`,
`right`) VALUES(\''.$title.'\', \''.$right.'\',
\''.($right+1).'\')');
// zdejmujemy blokade, tabela ponownie nadaje
// sie do uzytku
mysql_query('UNLOCK TABLES');
} // end createNode();
?>


Piszę "zaczątek", ponieważ obecnie, jeśli pomylimy ID rodzica, funkcja pomyśli, że zaczynamy robić nowe drzewo i wszystko pochrzani :). Dodatkowo przypominam, aby nie zapomnieć tutaj o założeniu blokady na tabelę na czas dodawania tak, jak ja to zrobiłem. Inaczej przy dużym ruchu oglądający może ujrzeć głupoty, ale to nie wszystko. W najgorszym przypadku dwie osoby mogą dodać jakiś węzeł w tym samym czasie, co ewidentnie rozwali nam bazę.

W analogiczny sposób realizuje siÄ™ usuwanie; trzeba tylko odwrócić czynnoÅ›ci.

Opisana tu struktura ma jeszcze dwie ciekawe wÅ‚aÅ›ciwoÅ›ci. Na poczÄ…tek odpowiemy na pytanie, ile elementów zawiera dany wÄ™zeÅ‚. Możemy to wyliczyć bez uciekania siÄ™ do funkcji COUNT:
(right-left-1)/2

NastÄ™pnie zajmijmy siÄ™ stworzeniem paska nawigacyjnego. WykorzystujÄ… go czÄ™sto i gÄ™sto rozmaite serwisy WWW, aby oglÄ…dajÄ…cy mógÅ‚ zorientować siÄ™, jak głęboko w nich ugrzÄ…sÅ‚: Zyxlaski.pl » Importowane » MahoÅ„ » Prod. szwedzka » Superkijek 2000 Pro. Tu również wystarczÄ… nam dwa zapytania:


# Pobierz parametry left i right elementu, w ktorym jestes
SELECT `left`, `right` FROM drzewko WHERE id='1'

# Wyswietl sciezke do niego
SELECT `nazwa` FROM drzewko WHERE `left` <= @LEFT AND
`right` >= @RIGHT ORDER BY `left`


Jeśli chcemy, aby na pasku NIE pojawiła się także nazwa właśnie oglądanego elementu, zamieniamy znaki <= i >= na < i >.

Na koniec taka uwaga. OsobiÅ›cie stwierdziÅ‚em, że mimo wszystko najlepiej jest połączyć ten sposób z metodÄ… tradycyjnÄ…, tj. zostawić także pole "parent_id". DziÄ™ki temu bÄ™dziemy mogli też wyÅ›wietlać poziomy pÅ‚asko, bez zgłębiania siÄ™ w ich podwÄ™zÅ‚y itd. Na jego podstawie jesteÅ›my też w stanie odtworzyć budowÄ™ drzewa, gdyby ktoÅ› przez przypadek namieszaÅ‚ nam z parametrami left i right.

W powyższym kodzie brakuje wielu istotnych metod, m.in. zamieniania dwóch równorzÄ™dnych wÄ™zÅ‚ów miejscami. Pozostawiam to czytelnikowi jako ćwiczenie. Opracowanie wszystkich funkcji zarzÄ…dzania drzewem zajęłoby tak dużo miejsca, że przekracza możliwoÅ›ci tego tekstu, a napisanie ich samodzielnie nie stanowi zbyt dużego problemu, jeÅ›li pojmie siÄ™ zasadÄ™, na jakiej wszystko funkcjonuje.

Na tym koÅ„czÄ™ ten artykulik. Gwoli Å›cisÅ‚oÅ›ci dodam, że pomysÅ‚ na zrobienie czegoÅ› takiego w taki sposób daÅ‚ mi tekst Storing Hierarchical Data in a Database.

 

ŹródÅ‚o: http://artykuly.zyxist.com/



Napisz Artyku³

Listing

niema




Dodano przez: divix
Ranga: Administrator serwisu Punktów: 38473
Komentarze użytkowników
    • Tre¶æ komentarza
      Kod do komentarza (opcjonalnie)
      PHP JavaScript MySQL Smarty SQL HTML CSS ActionScript
      Autor
      Token
      token

       

       








funkcje.net
Wszelkie prawa zastrzeżone©. | Funkcje.net 2008-2021 v.1.5 | design: diviXdesign & rainbowcolors