Fie ca vrei să-ți construiești propriul forum, publica mesajele dintr-o lista de discuții pe site-ul tau sau să scrii propiul CMS. Va veni un moment cînd vei dori sa stocezi datele ierarhic într-o bază de date. Și daca nu folosești o bază de date XML, tabelele nu sunt ierarhice; acestea sunt doar o un fișier plat. Există 2 metode importante: modelul listei adiacente și algoritmul parcurgerii arborelui cu preordine modificată.
În acest articol vom explora aceste 2 metode. Ca exemplu vom folosi arborele unui magazin alimentar fictiv. Acest magazin își sorteaza produsele dupa categorie, culoare și tip
Acest articol conține o serie de exmple de cod, care arată cum se salvează și se restabilesc datele. Deoarece folosesc eu însumi acest limbaj și mulți alți oameni îl folosesc sau îl cunosc, am ales să scriu exemple în PHP. Putem cu ușurință sa-l traducem in limbajul care îl doriți.
Metoda recursivă
Prima și cea mai elegantă metodă pe care o vom încerca se numește metoda recursivității. Este o metodă elegantă pentru ca avem nevoie de o simplă funcție care să se repete în arborele dumneavoastră. În magazinul nostru de alimente tabelul arată astfel:
După cum vedeți salvați “părintele” fiecărui nod. Putem vedea că “Pear” este copil al lui “Green” care este un copil al “Fruit” s.a.m.d Nodul rădăcină “Food” nu are o valoare parentală. Pentru simplificare, am folosit valoarea “title” pentru a identifica fiecare nod. Bineînțeles, într-o bază de date reală ar trebui să folosiți id-ul numeric al fiecărui nod.
Dați-mi arborele
Acum că am introdus arborele nostru în baza de date, e timpul sa scriem funcția de afișare. Această funcție va trebui să înceapă de la nodul rădăcină – nodul fără nici un părinte – și ar trebui să afișeze apoi toți copiii din acel nod. Pentru fiecare dintre acești copii, funcția va trebui să restabilească și să arate toate nodurile copii ale acelui copil. Pentru acești copii, funcția ar trebui să arate din nou toți copiii și așa mai departe.
După cum s-ar putea să fi observat, există un model regulat în descrierea funcției. Putem scrie pur si simplu o singură funcție, care preia copiii unui anumit nod părinte. Această funcție ar trebui să pornească o altă instantă a ei însăși pentru fiecare dintre acești copii, pentru a-i arăta pe toți copii acestora. Acesta este mecanismul recursiv care-i dă metodei numele de metoda recursivității.
Code block
<?php
// $parent este parintele copiilor pe care vrem sa-i vedem
// $level creste cand inaintam in arbore, pentru a arata arborele frumos
function display_children($parent, $level)
{
// restabileste toti copiii $parent
$result = mysql_query('SELECT title FROM tree '.'WHERE parent="'.$parent.'";');
// arata fiecare copil
while ($row = mysql_fetch_array($result))
{
// indenteaza si arata titlul acestui copil
echo str_repeat(' ',$level).$row['title']."n";
// copiii acestui copil
display_children($row['title'], $level+1);
}
}
?>
Pentru a afișa întregul arbore, vom rula funcția cu un șir gol cur ar fi $parent și $level = 0; display_children(‘ ‘,0).
Pentru arborele magazinului nostru funcția returnează:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
Rețineți că, dacă vreți să vedeți un sub-arbore, puteți indica funcția să pornească cu-n alt nod. De exemplu, pentru a arăta sub-arborele Fruit, ar trebui să puneți în aplicare display_children(‘Fruit’,0);
Calea către un nod
Aproape cu aceeași funcție, este posibil pentru a căuta calea spre un nod dacă știi doar numele sau id-ul acelui nod. De exemplu calea spre “Cherry” este “Foot” > “Fruit” > “Red“. Pentru a obține această cale, funcția noastră va trebui sa înceapă de la nivelul cel mai profund: “Cherry”. Dupa care, ea se uită in sus la părintele acestui nod și-l adaugă la această cale. În exemplul nostru, acest lucru ar fi “Red” este părinte pentru “Cherry“, putem calcula calea spre “Cherry“, folosind calea spre “Red“. Și acest lucru ne este dat de funcția care am folosit-o: căutînd în mod recursiv părinții, vom obține calea către orice nod din arbore.
Code block <?php
// $node este numele nodului a carui cale o dorim
function get_path($node)
{
// cauta parintele acestui nod
$result = mysql_query('SELECT parent FROM tree '.'WHERE title="'.$node.'";');
$row = mysql_fetch_array($result);
// salveaza calea in aceasta ordine
$path = array();
// continua numai daca acest Snod nu este nodul radacina
if ($row['parent']!='')
{
// ultima parte a caii spre $nod, este numele
// parintelui lui $node
$path[] = $row['parent'];
// ar trebui sa adaugam calea spre parintele acestui nod la cale
$path = array_merge(get_path($row['parent']), $path);
}
// returneaza calea
return $path;
}
?>
Această funcție returnează calea spre un nod dat. Returnează calea în array, pentru a arăta aclea putem folosi print_r(get_path(‘Cherry’));
Dacă facem acest lucru pentru “Cherry”, vom vedea:
Array
(
[0] => Food
[1] => Fruit
[2] => Red
)
Dezavantaje
După cum ați văzut, aceasta este o metodă excelentă. Este ușor de înțeles, și codul de care avem nevoie este simplu. Atunci care sunt dezavantajele modelului acestei structuri de date? În majoritatea limbajelor de programare, este lentă și ineficientă. Aceasta se datorează recursivității. Avem nevoie de o interogare în baza de date pentru fiecare nod din arbore.
Fiecare interogare ia ceva timp, acest lucru face foarte lentă funcția atunci cînd se aplică la arbori foarte mari.
Al doilea motiv pentru care această metodă nu este atît de rapidă, este limbajul de programare pe care probabil îl veți folosi. Spre deosebire de limbajele cum ar fi Lips, cele m ai multe limbaje nu sunt proiectate pentru recursivitate. Pentru fiecare nod, funcția pornește o altă instanță a ei însăși. Deci, pentru un arbore cu patru nivele, veți pune în aplicare patru instanțe ale funcției in același timp. Și cum fiecare funcție ocupă o felie de memorie și are nevoie de ceva timp pentru a porni, recursivitatea este foarte lentă atunci cînd este aplicată pentru arbori mari.
Parcurgerea în preordine modificată a arborelui
Acum, haideți să aruncăm o privire asupra altei metode de stocare a arborilor. Recursivitatea poate fi lentă, așă că n-ar trebui să folosim o funcție recursivă. Am dori de asemenea să micșorăm numărul interogărilor în baza de date. Preferabil ar fi dacă am avea o singură interogare pentru fiecare activitate.
Vom începe prin așezarea aborelui nostru în poziție orinzontală. Pornim de la nodul rădăcină (“Food“) și scriem 1 în stînga lui. Urmăm arborele spre “Fruit” și scriem 2 lîngă el. În acest fel, mergem de-a lungul marginilor arborelui în timp ce scriem cîte un număr în stînga și în dreapta fiecărui nod. Ultimul număr este scris în dreapta nodului “Food“. În această imagine, putem vedea întregul arbore numerotat și cîteva săgeți care arată ordinea numerotării.
Vom numi aceste numere la stînga și la dreapta. (de exemplu valoarea stînga pentru “Food” este 1, valoarea dreapta este 18 ). După cum puteți vedea, aceste cifre indică relația dintre fiecare nod. Deoarece “Red” are numerele 3 și 6, este un descendent a 1-18 “Food“. În același fel, putem spune că toate nodurile cu valorile de stînga mai mari decît 2 și valorile din dreapta mai mici decît 11 sunt descendenți ai nodului 2-11 “Fruit“. Structura arborelui este acum stocată în valorile din stînga și din dreapta. Această metodă de a merge imprejurul arborelui și de a număra nodurile se numește algoritmul “Parcurgerea în preordine modificată a arborelui“.
Înainte de a continua, să vedem cum arată aceste valori în tabelul nostru:
Rețineți că termenii left și right au o semnificație specială în SQL. Prim urmare, vom utiliza “lft” și “rgt” pentru a identifica coloanele. Observați de asemenea că nu prea avem nevoie de coloana părinte. Avem acum valorile “lft” și “rgt” pentru a stoca structura arborelui.
Extragerea datelor din arbore
Dacă doriți să afișați arborele cu ajutorul unui tabel cu valorile stînga și dreapta, va trebui mai întii mai întii să identificați nodurile pe care vreți să le restabiliți. De exemplu, dacă vreți subarbore “Fruit“, vei avea pentru a selecta numai nodurile cu o valoare de stînga între 2 și 11. În SQL, aceasta ar însemna:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
Această interogare returnează:
Ei bine, iată un arbore întreg într-o singură interogare. Pentru a arăta acest arbore așa cum am procedat cu funcția noastră recursivă, va trebui să adăugam o clauză ordonara după (order by) pentru această interogare. Dacă adăugați și ștergeți rînduri din tabelul dvs, probabil că el nu va fi în ordinea corectă. De aceea, ar trebui să ordonăm rîndurile după valoarea lor din stînga.
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11 ORDER BY lft ASC;
Singura problemă care ne-a mai rămas este identarea.
Pentru a arăta structura arborelui, copiii ar trebui indentați ceva mai mult decît părintele lor. Putem face aceasta, păstrînd o stivă a volorilor din dreapta. De fiecare dată când începeţi cu copiii unui nod, adăugaţi valoarea din dreapta a acelui nod la stivă. Ştiţi că toţi copiii acelui nod au o valoare-dreapta mai mică decât valoarea din dreapta a părintelui, aşa că, dacă o să comparaţi valoarea din dreapta a nodului curent cu ultimul nod din dreapta aflat în stivă, o să puteţi vedea dacă încă mai arătaţi copiii acelui părinte. Când aţi terminat de arătat un nod, îndepărtaţi valoarea sa din partea dreaptă din stivă. Dacă veţi număra elementele din stivă, veţi obţine nivelul nodului curent.
Code block <?php
function display_tree($root)
{
//restabileste toti descendentii nodului $root
$result = mysql_query('SELECT lft, rgt FROM tree '.'WHERE title="'.$root.'";');
$row = mysql_fetch_array($result);
// incepe cu o stiva goala $right
$right = array();
// restabileste toti descendentii nodului $root
$result = mysql_query('SELECT title, lft, rgt FROM tree '.
'WHERE lft BETWEEN '.$row['lft'].' AND '.
$row['rgt'].' ORDER BY lft ASC;');
// arata fiecare rand
while ($row = mysql_fetch_array($result))
{
// verifica stiva numai daca exista una
if (count($right)>0)
{
// verifica daca ar trebui sa indepartam un nod din stiva
while ($right[count($right)-1]<$row['rgt'])
{
array_pop($right);
}
}
// arata titlul nodului indentat
echo str_repeat(' ',count($right)).$row['title']."n";
// adauga acest nod la stiva
$right[] = $row['rgt'];
}
}
Dacă veţi folosi acest cod, veţi obţine exact acelaşi arbore pe care l-aţi obţinut cu funcţia recursivă discutată mai sus. Noua noastră funcţie va fi probabil mai rapidă, nu este recursivă şi foloseşte doar două interogări
Calea către un nod
Cu acest nou algoritm, va trebui de asemenea să găsim un nou mod de a obţine calea către un anumit nod. Pentru a obţine această cale, vom avea nevoie de o listă a tuturor strămoşilor acelui nod.
Cu structura noului nostru tabel, nu este foarte greu. Când vă uitaţi, de exemplu, la nodul 4-5 ”Cherry“, o să vedeţi că valorile din stânga ale tuturor strămoşilor sunt mai mici decât 4, în timp ce toate valorile din dreapta sunt mai mari decât 5. Pentru a obţine toţi strămoşii, putem folosi această interogare:
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
Observaţi că, întocmai ca în investigaţia noastră precedentă, trebuie să folosim clauza ORDONEAZA DUPA pentru a sorta nodurile. Această interogare va returna:
+——-+
| title |
+——-+
| Food |
| Fruit |
| Red |
+——-+
Acum nu ne rămâne decât să intrăm pe fiecare rând pentru a găsi calea spre “Cherry“.
Cîţi descendenţi
Dacă îmi daţi valorile din stânga şi din dreapta ale unui nod, vă pot spune căţi descendenţi are, folosind puţină matematică.
Deoarece fiecare descendent incrementează valoarea din dreapta a nodului cu 2, numărul descendenţilor poate fi calculat cu:
$descendants = (right – left – 1) / 2
Cu această formulă simplă, vă pot spune că nodul 2-11 “Fruit” are 4 noduri descendenţi şi că nodul 8-9 “Banana” este doar un copil, nu un părinte.
Automatizarea parcurgerii arborelui
Acum că aţi văzut câteva dintre lucrurile uşoare pe care le puteţi face cu acest tabel, e timpul să învăţăm cum putem automatiza crearea acestui tabel. Cu toate că este un exerciţiu plăcut atunci când e făcut prima dată şi cu un arbore mic, avem cu adevărat nevoie de un scenariu care să facă toată această numărătoare şi înconjur al arborelui pentru noi.
Să scriem un scenariu care transformă o listă adiacentă într-un tabel traversal al arborelui cu preordine modificată.
Code block <?php
function rebuild_tree($parent, $left)
{
// valoarea din dreapta a acestui nod este valoarea din stanga + 1
$right = $left+1;
// obtine toti copiii acestui nod
$result = mysql_query('SELECT title FROM tree '.'WHERE parent="'.$parent.'";');
while ($row = mysql_fetch_array($result))
{
// executarea recursiva a acestei functii pt fiecare copil al acestui nod
// $right este valoarea dreapta curenta, care este incrementata de functia rebuild_tree()
$right = rebuild_tree($row['title'], $right);
}
// am obtinut valoarea din stanga, si acum ca am procesat
// copiii acestui nod stim si valoarea din dreapta
mysql_query('UPDATE tree SET lft='.$left.', rgt='.$right.' WHERE title="'.$parent.'";');
// returneaza valoarea din dreapta a acestui nod + 1
return $right+1;
}
?>
ceasta este o funcţie recursivă. Ar trebui s-o porniţi cu
rebuild_tree(‘FOOD’,1);
atunci funcţia restabileşte toţi copiii nodului “Food”.
Dacă nu există copii, ea stabileşte valorile din stânga şi din dreapta ale acestui nod. Valoarea din stânga este dată, 1, iar valoarea din dreapta este valoarea din stânga plus 1. Dacă există copii, această funcţie se repetă şi ultima valoare din dreapta este restabilită. Această valoare este folosită atunci ca valoare din dreapta a nodului “Food”.
Recursivitatea face ca această funcţie să fie, prin complexitatea ei, destul de greu de înţeles. Totuşi, ea ajunge la acelaşi rezultat la care am ajuns noi manual la începutul acestui capitol. Ea merge în jurul arborelui, adăugând câte un nod pentru fiecare nod pe care îl vede. După ce aţi pus în aplicare această funcţie, veţi vedea că valorile din stânga şi din dreapta rămân aceleaşi (o verificare rapidă, valoarea din dreapta a nodului rădăcină ar trebui să fie egală cu de două ori numărul nodurilor).
Adăugarea unui nod
Cum adăugăm un nod la arbore? Există două abordări: puteţi păstra coloana părinte în tabelul dvs şi doar să porniţi din nou funcţia rebuild_tree() – o funcţie simplă dar nu aşa de elegantă; sau puteţi reactualiza valorile din stânga şi din dreapta ale tuturor nodurilor în partea dreaptă a fiecărui nod nou.
Prima opţiune este simplă. Folosiţi metoda listei adiacente pentru reactualizare şi algoritmul parcurgerii arborelui cu preordine modificată pentru restabilire. Dacă vreţi să adăugaţi un nou nod, adăugaţi-l la tabel şi setaţi coloana părinte. Apoi, nu vă rămâne decât să reporniţi funcţia rebuild_tree(). Această opţiune este uşoară, dar nu foarte eficientă cu arbori mari.
Cea de-a doua modalitate de a adăuga şi şterge noduri constă în reactualizarea valorilor din stânga şi din dreapta ale tuturor nodurilor în partea dreaptă a noului nod. Să ne uităm la un exemplu. Vrem să adăugăm un nou tip de fruct, o “Strawberry“, ca ultim nod şi copil al “Red“. Mai întâi, va trebui să facem puţin loc. Valoarea – dreapta de la “Red” ar trebui schimbată din 6 în 8, iar nodul 7-10 “Yellow” ar trebui schimbat în 9-12 etc. Reactualizarea nodului “Red” înseamnă că va trebui să adăugăm 2 la toate valorile din stanga şi din dreapta mai mari decât 5.
Vom folosi interogarea:
UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;
Acum putem adăuga un nou nod “Strawberry” pentru a umple noul spaţiu. Acest nod are valoarea – stânga 6 şi valoarea – dreapta 7.
INSERT INTO tree SET lft=6, rgt=7, title=’Strawberry’;
Dacă pornim funcţia noastră display_tree();, vom vedea că noul nostru nod “Strawberry” a fost introdus cu succes în arbore:
Food Fruit Red Cherry Strawberry Yellow Banana Meat Beef Pork
Dezavantaje
În primul rând, algoritmul parcurgerii arborelui cu preordine modificată pare greu de înţeles. Este cu siguranţă mai greu decât metoda listei adiacente. Totuşi, odată ce v-aţi obişnuit cu proprietăţile valorilor din stânga şi din dreapta, este evident că puteţi face cu această tehnică aproape tot ce făceaţi cu metoda listei adiacente şi că algoritmul traversal al arborelui cu preordine modificată este mult mai rapid. Reactualizarea arborelui impune mai multe investigaţii, ceea ce durează mai mult, dar restabilirea nodurilor se realizează cu o singură interogare.
Concluzie
Acum v-aţi familiarizat cu ambele metode de stocare a arborilor într-o bază de date. Deşi prefer oarecum parcurgerea arborelui cu preordine modificată, în cazul dvs. metoda listei adiacente ar putea fi mai bună. Vă las să judecaţi singuri.
Lecturi suplimentare
Mai multe despre Arbori în SQL de specialistul în baze de date Joe Celko:
http://searchdatabase.techtarget.com/tip/1,289483,sid13_gci537290,00.html
Alte două metode pentru a opera cu datele ierarhice:
http://www.evolt.org/article/Four_ways_to_work_with_hierarchical_data/17/4047/index.html
Xindice, baza de date XLM nativă:
http://xml.apache.org/xindice/
O explicaţie a recursivităţii:
http://www.strath.ac.uk/IT/Docs/Ccourse/subsection3_9_5.html