Metoda de stocare a copacilor în bd - traversal arbore preordonat (seturi imbricate)

Cuprins

1. Introducere

La proiectarea unei baze de date, adesea este necesar să se păstreze un copac și, din moment ce tabelele de baze de date nu sunt concepute special pentru stocarea arborilor, trebuie să recurgeți la diverse trucuri. Cea mai simplă și cea mai evidentă modalitate este de a stoca fiecare articol






arbore în plus față de identificatorul (id) referință la părinte (parent_id). Dar lucrul cu un astfel de copac implică o mulțime de cheltuieli, de exemplu, pentru a obține totul
arbore, trebuie să folosim recursiunea (sau emularea ei), făcând o interogare SQL
pe fiecare element al copacului. Mai jos este o descriere a metodei care minimizează costul de a efectua adesea operațiunile necesare cu copacii.

2. Descrierea metodei

Să presupunem că avem un copac și spunem că fiecare element al arborelui are o pereche de valori convențional numite stânga și dreapta. Mergem în jurul copacului din adâncimea rădăcinii (recursiv), și să alocați un indice secvențial al valorii din stânga de sus, atunci când vom ajunge la ea prima dată, iar valoarea din dreapta atunci când vom ajunge la a doua oară sau vârful este vârful final al arborelui (care nu are descendenți) . Deci, așa cum este reprezentat pe fotografia tabloului:

Metoda de stocare a copacilor în bd - traversal arbore preordonat (seturi imbricate)

3. Avantaje

Ce ne dă acest lucru? Ne dă posibilitatea efectuării mai multor operațiuni de copaci frecvent utilizate (care nu au legătură cu modificarea acestora) pentru 1 interogare SQL:

  1. Obținerea unui subtree (o listă de vârfuri care sunt un substrat al unui anumit vertex). Pentru a face acest lucru, trebuie doar să interogăm lista elementelor ale căror valori stângi sunt mai mari decât vârful dat, iar valorile corecte sunt mai mici:

SELECT * FROM `copac` WHERE` left`> AND `right` <

  • Cale de la rădăcină. Opusul operației anterioare este de a solicita o listă a elementelor ale căror valori stângi sunt mai mici decât vârful dat, iar valorile corecte sunt mai mari și se sortează după valoarea stânga sau dreapta:

    SELECT * FROM `tree` WHERE" stânga " ORDER CU "stânga" ASC;

  • Obținerea unei liste extinse de elemente de copac (ocolind în profunzime).
    Pentru a face acest lucru, trebuie doar să sortați eșantionul cu valoarea stângă:

    SELECT * FROM `copac` ORDER BY` left ';

    Combinând acest lucru cu punctul 1, puteți obține o listă detaliată a unui anumit subtree.
  • Obținerea volumului subtreei (numărul de elemente din interiorul acestui subtree). Pentru a face acest lucru, noi chiar
    Nu este nevoie să faceți o cerere suplimentară. În partea de sus, pentru care trebuie să obțineți volumul, luați doar (dreapta - stânga - 1) / 2.
  • Obținerea rădăcinii comune a subtreei volumului minim pentru două noduri date
    este posibil să se obțină dacă se interoghează elementul cu cea mai mare valoare stânga (sau cea mai mică dreaptă) pentru care valoarea stânga este mai mică decât ambele stânga și dreapta este mai mare decât amândouă dreapta:

    $ left = min ($ node1_left, $ node2_left);
    $ dreapta = max ($ node1_right, $ node2_right);
    SELECT * FROM `tree` WHERE" stânga " <$left AND ` right `> $ dreapta ORDER BY 'stânga' DESC LIMIT 1;

    În plus, arborele nostru are câteva proprietăți potențial utile:







    1. Vârful final al arborelui are o valoare stânga egală cu dreapta + 1;
    2. Primul descendent al unui vârf are o valoare stânga egală cu valoarea stângă a părintelui - 1;
    3. Ultimul descendent al unui vârf are valoarea corectă egală cu valoarea dreapta părinte + 1.

    Cu toate acestea, pentru o traversare recursivă a unui copac, este încă mai convenabil să folosiți o metodă mai tradițională de stocare a unui copac folosind id și parent_id. Nu văd nici un motiv să o abandonez - ambele metode de stocare a unui copac pot fi combinate cu succes și astfel să se utilizeze avantajele ambelor.

    4. Dezavantaje

    Această metodă are așa-numitul. dezavantaj, adică atunci când adăugăm, eliminăm și mutăm elemente de copac, trebuie să recalculează valorile stânga și dreapta ale arborelui.

    4.1. Adăugarea unui element

    Adăugarea unui nou copil la un anumit vârf poate fi făcută în două moduri: în partea de sus a listei de copii și la sfârșit.

    UPDATE `copac` SET` left` = `left` + 2 WHERE` left`>;
    UPDATE `tree` SET` dreapta` = `dreapta` + 2 WHERE` right`>;
    INSERTAȚI ÎN "arborele" SET "stânga" = + 1, "dreapta" = + 2;

    UPDATE `copac` SET` left` = `left` + 2 WHERE` left`>;
    UPDATE `copac` SET` dreapta` = `dreapta` + 2 WHERE` right`> =;
    INSERTAȚI ÎN "arborele" SET "stânga" =, "dreapta" = + 1;

    Unde $ parent_left și $ parent_right sunt valorile stânga și dreapta ale vertexului părinte, respectiv.

    Adăugarea de mai multe elemente în același element părinte poate fi optimizată nu efectua în mod necesar 2 actualizare pentru fiecare element adăugat - este posibil să se efectueze actualizarea 2 pentru toate elementele adăugate direct.

    4.2. Ștergerea unui element sau a unui subtree

    Eliminarea unui element sau a unui subtree este, de asemenea, relativ simplă:

    DELETE din "arborele" WHERE "left"> = AND `right` <= ;
    UPDATE `copac` SET` left` = `left` - + - 1 WHERE` left`>;
    UPDATE `tree` SET` dreapta` = `dreapta` - + - 1 WHERE` right`>;

    Unde $ left și $ right sunt valorile stânga și dreapta ale vârfului elementului sau sub-arborelui care urmează să fie șterse.

    4.3. Mutarea unui element sau a unui subtree

    Mutarea copac element este cel mai dificil în această operațiune, este necesar să se recalculeze valorile din stânga și din dreapta întregului copac, deși poate fi optim pusă în aplicare prin adăugarea mișcarea elementelor din lemn transportate pe unul și îndepărtarea vertex mobil cu întreaga subarbore.

    4.4. Asigurarea integrității

    Din păcate, integritatea unui astfel de copac este ușor de rupt și dificil de reparat. Mai precis, restaurarea constă într-o recalculare completă a copacului. Și perturba integritatea poate, de exemplu, întreruperea anormală a lucrării asociate cu modificarea structurii arborilor. Așa cum am menționat mai sus, adăugarea și ștergerea elementelor copacilor constă din mai multe interogări. Dacă faci doar o parte din ele, atunci integritatea arborelui va fi ruptă. Prin urmare: În primul rând, recomand cu tărie să păstreze un copac în tranzacțiile de întreținere de masă (de exemplu, InnoDB în MySQL) și funcționează adăugarea și eliminarea elementelor din lemn în cadrul tranzacției (START TRANZACȚII; ...; COMMIT;); în al doilea rând, să adăugăm indicii unici la valorile stânga și la dreapta - acest lucru, desigur, nu garantează integritatea, dar poate ajuta la prevenirea erorilor stupide atunci când lucrează cu un copac.

    4.5. Atenție la actualizarea arborelui

    Când efectuați o modificare arborescentă, nu uitați că valorile din stânga și din dreapta se modifică după fiecare schimbare de structură. Astfel, dacă selectați elemente de arbore din tabelul bazei de date, în paralel cu modificarea acesteia, atunci valorile din stânga și din dreapta din eșantion sunt depășite. Sau dacă obțineți valorile stânga și dreapta și salvate în variabilele corespunzătoare, după modificarea arborelui, valorile stocate în variabile sunt probabil depășite.

    5. Citirea ulterioară

    5 recenzii despre "Metoda de stocare a copacilor în baza de date - Traversal copac preordonat (seturi nets)"

    Este posibil să se păstreze mai mulți copaci în tabel când se folosește această metodă?

    Sau elementul rădăcină al întregului arbore poate fi doar unul?

    Este posibil, de altfel, să nu avem nici un mijloc de a furniza o listă a structurii copacilor, cu excepția, desigur, creierul nostru - nu controlăm absența ciclurilor și unicitatea rădăcinii. În plus, același nod poate intra în mai mulți copaci în același timp, dar apoi se obține "dag". Personal, am avut imediat această întrebare - bineînțeles, toate acestea sunt bune, cât de mult puteți lucra rapid cu copacii prin SQL?

    Rămâne să înțelegeți cum să obțineți un arbore formatat (cu indentare) din baza de date?

    Și cred că ar trebui să fie așa:
    - Primul descendent al unui vârf are o valoare stânga egală cu valoarea stângă a părintelui + 1; (mai degrabă decât -1)
    - Ultimul descendent al unui vârf are valoarea corectă egală cu valoarea corectă a părintelui - 1. (și nu +1)

    Scrie ceea ce crezi despre asta







    Articole similare

    Pagina anterioară

    Pagina următoare

    Trimiteți-le prietenilor: