Conţinut

• Diagramă de comparație
• Definiția B-tree
• Proprietățile arborelui B de ordin M
• Definiția Binary tree
• Tehnici de traversare
• Concluzie

Arborele B și arborele binar sunt tipurile de structură neliniară a datelor. Deși termenii par a fi similari, dar sunt diferiți în toate aspectele. Un arbore binar este utilizat atunci când înregistrările sau datele sunt stocate în memoria RAM în loc de disc, deoarece viteza de acces a RAM este mult mai mare decât discul. Pe de altă parte, arborele B este utilizat atunci când datele sunt stocate în disc, reduce timpul de acces prin reducerea înălțimii arborelui și creșterea ramurilor din nod.

O altă diferență între arborele B și arborele binar este că arborele B trebuie să aibă toate nodurile copilului la același nivel, în timp ce arborele binar nu are o asemenea constrângere. Un arbore binar poate avea maximum 2 subtrape sau noduri, în timp ce în arborele B nu poate avea M nici un subtrees sau noduri în care M este ordinea arborelui B.

1. Diagramă de comparație
2. Definiție
3. Diferențele cheie
4. Concluzie

Diagramă de comparație

Baza de comparație	B-tree	Arbore binar
Constrângere esențială	Un nod poate avea un număr maxim de M de noduri copil (unde M este ordinea arborelui).	Un nod poate avea cel mult 2 sub-straturi.
Folosit	Se utilizează atunci când datele sunt stocate pe disc.	Se utilizează atunci când înregistrările și datele sunt stocate în memoria RAM.
Înălțimea copacului	ButurugaM N (unde m este ordinea arborelui M-way)	Buturuga2 N
cerere	Structura datelor de indexare a codurilor în multe DBMS.	Optimizarea codului, codarea Huffman etc.

Definiția B-tree

Un copac B este arborele M-way echilibrat și, de asemenea, cunoscut sub numele de arbore de sortare echilibrat. Este similar cu arborele de căutare binară unde nodurile sunt organizate pe baza traversării inordonate. Complexitatea spațială a arborelui B este O (n). Complexitatea timpului de inserare și ștergere este O (log n).

Există anumite condiții care trebuie să fie adevărate pentru un arbore B:

• Înălțimea copacului trebuie să fie cât mai mică.
• Deasupra frunzelor copacului, nu trebuie să existe subterane goale.
• Frunzele copacului trebuie să vină la același nivel.
• Toate nodurile ar trebui să aibă cel puțin un număr de copii, cu excepția nodurilor părăsite.

Proprietățile arborelui B de ordin M

• Fiecare nod poate avea un număr M maxim de copii și un număr minim de copii M / 2 sau orice număr de la 2 la maxim.
• Fiecare nod are o singură cheie mai mică decât copiii cu taste M-1 maxim.
• Dispunerea tastelor este într-o anumită ordine în noduri. Toate cheile din subtree prezente în stânga tastei sunt predecesoarele cheii, iar cele prezente în dreapta cheii sunt numite succesoare.
• În momentul introducerii unui nod complet, arborele se împarte în două părți, iar cheia cu valoare mediană este introdusă la nodul părinte.
• Operația de îmbinare are loc la ștergerea nodurilor.

Definiția Binary tree

Un arbore binar este o structură de arbore care poate avea cel mult doi indicatori pentru nodurile copilului său. Înseamnă că cel mai înalt grad pe care îl poate avea un nod este de 2 și poate exista și un nod cu un grad sau cu un grad.

Există anumite variante ale unui arbore binar, cum ar fi arborele binar strict, arbore binar complet, arbore binar extins etc.

• Arborele strict binar este un arbore în care fiecare nod neterminal trebuie să aibă subtree stânga și subtree dreapta.
• Un copac se numește arbore binar complet atunci când satisface condiția de a avea 2 ^eu noduri la fiecare nivel unde sunt nivelul.
• Binarul filetat este un arbore binar care constă fie din 0 nr de noduri sau 2 număr de noduri.

Tehnici de traversare

Traversarea arborelui este una dintre cele mai frecvente operații efectuate pe structura de date arbore în care fiecare nod a vizitat exact o dată într-un mod sistematic.

• Inorder- În acest arbore de traversare, subtree stânga este vizitată recursiv, apoi nodul rădăcină este vizitat și în ultima sub-dreapta dreapta este vizitat.
• Preorer - În acest arbore traversare, nodul rădăcină este vizitat la început, apoi subtree stânga și în cele din urmă subtree dreapta.
• Postorder- Această tehnică vizitează subtree stânga apoi subtree dreapta și în final nodul rădăcină.

1. În arborele B, numărul maxim de noduri copil pe care le poate avea un nod non-terminal este M unde M este ordinea arborelui B. Pe de altă parte, un arbore binar poate avea cel mult două subtreze sau noduri copil.
2. Arborele B este utilizat atunci când datele sunt stocate pe disc, în timp ce arborele binar este utilizat atunci când datele sunt stocate în memorie rapidă, cum ar fi memoria RAM.
3. Un alt domeniu de aplicare pentru arborele B este structura datelor de indexare a codurilor în SGBD, în schimb, arborele Binary este folosit în optimizarea codului, codarea huffman etc.
4. Înălțimea maximă a unui arbore B este jurnalul_MN (M este ordinea arborelui). Spre deosebire, înălțimea maximă a arborelui binar este jurnalul₂N (N este numărul de noduri și baza este 2, deoarece este pentru binar).

Concluzie

Arborele B este utilizat peste arborele de căutare binare și binare. Motivul principal din spatele acesteia este ierarhia de memorie în care CPU este conectat la cache cu canale cu lățime mare de bandă în timp ce CPU este conectat la disc prin canal cu lățime de bandă mică. Un arbore binar este utilizat atunci când înregistrările sunt stocate în RAM (mici și rapide) și B-tree sunt utilizate atunci când înregistrările sunt stocate pe disc (mare și lent). Așadar, utilizarea arborelui B în locul arborelui binar reduce semnificativ timpul de acces din cauza factorului mare de ramificare și a înălțimii reduse a arborelui.