Descriere:Stocarea unor date ierarhice intr-o baza de date
Download:Nu necesita
Autor:Anonim
Sursa (Link-ul oficial): Propria parere:Util.
Tutorialul:
Fie că vreţi să vă construiţi propriul forum, să vă publicaţi mesajele dintr-un ‘mailing list' pe propriul site de pe internet sau să vă scrieţi propriile CMS, va veni un moment când veţi dori să stocaţi datele ierarhice într-o bază de date. Şi, dacă nu folosiţi o bază de date cu suport XML, tabelele nu sunt ierarhice; ele nu sunt decât un fişier plat. Va trebui să găsiţi un mod de a traduce ierarhia într-un fişier plat.
Stocarea arborilor este o problemă obişnuită, cu multiple soluţii. Există 2 abordări importante: modelul listei adiacente şi algoritmul parcurgerii arborelui cu preordine modificată.
În acest articol vom explora aceste 2 metode de salvare a datelor ierarhice. Ca exemplu voi folosi arborele dintr-un magazin alimentar fictiv de pe internet. Acest magazin îşi sortează alimentele după categorie, culoare şi tip. Arborele arată astfel:
sitepoint tree
Acest articol conţine un număr de exemple de coduri 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 exemplele în PHP. Probabil că-l puteţi traduce uşor în limbajul pe care vi-l doriţi.
Metoda recursivă
Prima şi cea mai elegantă abordare pe care o vom încerca se numeşte metoda recursivităţii . Este o abordare elegantă pentru că veţi avea nevoie de o simplă funcţie care să se repete în arborele dvs. În magazinul nostru de alimente tabelul arată astfel:
tabel 01
După cum vedeţi salvaţi "părintele" fiecărui nod. Putem vedea că "Pear" este un copil al lui "Green" care este un copil al "Fruit" ş.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 să scriem o funcţie de afişare. Această funcţie va trebui să înceapă la nodul rădăcină - nodul fără nici un părinte – şi ar trebui după aceea să arate toţi copiii acelui nod. Pentru fiecare dintre aceşti copii, funcţia ar 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 ş.a.m.d.
Aşa după cum probabil că aţi observat, există un tipar regulat în descrierea acestei funcţii. Putem pur şi simplu să scriem o funcţie care restabileşte copiii unui anumit nod părinte. Acea funcţie ar trebui atunci să pornească o altă instanţă a ei însăşi pentru fiecare dintre aceşti copii, pentru a-i arăta pe toţi copiii acestora. Acesta este mecanismul recursiv care-i dă metodei numele de " metoda recursivităţii".
Cod:
Cod: Selectaţi tot
<?php
// $parent este parintele copiilor pe care vrem sa-i vedem
// $level creste cand inaintam in arbore,
// folosit pentru a arata un arbore frumos indentat
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";
// foloseste din nou aceasta functie pt a arata
// copiii acestui copil
display_children($row['title'], $level+1);
}
}
?>$row =0; display_children(' ',0);
Pentru arborele magazinului nostru de alimente funcţia returnează:
Citat:
Food
Fruit
Red
Cherry
Yellow
Banana
Meat
Beef
Pork
Observaţi că, dacă vreţi să vedeţi un sub-arbore, puteţi indica funcţiei să pornească cu un 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
Cu aproximativ aceeaşi funcţie, puteţi căuta calea spre un nod, dacă ştiţi numele sau id-ul acelui nod. De exemplu, calea spre "Cherry" este "Food" > "Fruit" > "Red". Pentru a găsi această cale, funcţia noastră va trebui să pornească la cel mai profund nivel : "Cherry". După aceea, ea caută părintele acestui nod şi-l adaugă la cale. În exemplul nostru, acesta ar fi "Cherry". Dacă ştim că "Red" este părinte pentru "Cherry", putem calcula calea spre "Cherry", folosind calea spre "Red". Şi acest lucru ne este dat de funcţia pe care tocmai am folosit-o: căutând în mod recursiv părinţii, vom găsi calea către orice nod din arbore.
Cod:
Cod: Selectaţi tot
<?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
// (acesta este nodul fara nici un parinte)
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;
}
?>print_r(get_path('Cherry'));
Dacă faceţi acest lucru pentru "Cherry", veţi vedea că:
Citat:
ARRAY ( [0] => Food [1] => Fruit [2] => Red )
Dezavantaje
Aşa cum tocmai am văzut, aceasta este o metodă excelentă. E uşor de înţeles şi codul de care avem nevoie este de asemenea simplu. Atunci care sunt dezavantajele modelului acestei structuri de date? În majoritatea limbajelor de programare, este lentă şi ineficientă. Acest lucru se datorează în special recursivităţii. Avem nevoie de o interogare în baza de date pentru fiecare nod din arbore.
Cum fiecare interogare durează destul de mult, aceasta face ca funcţia să fie foarte lentă când se aplică pe arbori 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 limbaje cum ar fi Lisp, cele mai multe limbaje nu sunt concepute pentru funcţii recursive. Pentru fiecare nod, funcţia porneşte o altă instanţă a ei însăşi. Aşa că, pentru un arbore cu patru nivele, veţi pune în aplicare patru instanţe ale funcţiei în 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ă pe arbori mari.
Parcurgerea în preordine modificată a arborelui
Acum, să aruncăm o privire asupra unei alte metode de stocare a arborilor. Recursivitatea poate fi lentă, aş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. Am prefera să avem o singură interogare pentru fiecare activitate.
Vom începe prin a aşeza arborele nostru în poziţie orizontală. 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, puteţi vedea întregul arbore numerotat şi câteva săgeţi care arată ordinea numerotării.
sitepoint_numbering
Vom numi aceste numere stângul şi dreptul (de exemplu valoarea stângă pentru "Food" este 1, valoarea dreaptă este 18). După cum vedeţi, aceste numere indică relaţia care se stabileşte între fiecare dintre aceste noduri. Deoarece "Red" are numerele 3 şi 6, el este un descendent al nodului 1-18 "Food". În acelaşi fel, putem spune că toate nodurile cu valorile din 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 de jur împrejurul 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:
table02
După cum observaţi, cuvintele "left" şi "right" au un înţeles special în SQL. De aceea, va trebui să folosim "lft" şi "rgt" pentru a identifica coloanele. Observaţi de asemenea că nu prea mai avem nevoie de coloana părinte . Avem acum valorile "lft" şi "rgt" pentru a stoca structura arborelui.
Extragerea datelor din Arbore
Dacă vreţi să arătaţi arborele folosind un tabel cu valorile din stânga şi din dreapta, va trebui mai întâi să identificaţi nodurile pe care vreţi să le restabiliţi. De exemplu, dacă vreţi sub-arborele "Fruit", va trebui să selectaţi numai nodurile cu o valoare-stânga cuprinsă între 2 şi 11. În SQL, aceasta ar însemna:
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
Această interogare returnează:
table03
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ăugăm o clauză ORDONEAZA DUPA la 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;
Ultima problemă care ne-a mai rămas este indentarea.
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 valorilor 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.
Cod:
Cod: Selectaţi tot
<?php
function display_tree($root) {
// acum, 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 $right goala
$right = array();
// acum, 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'];
}
}
?>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:
Citat:
+-------+ | 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ă.
Cod:
Cod: Selectaţi tot
<?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;
}
?>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:
Citat:
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.