Content

• Gràfic de comparació
• Definició de B-tree
• Propietats de l'arbre B de l'ordre M
• Definició de Binary tree
• Tècniques transversals
• Conclusió

L'arbre B i l'arbre binari són els tipus d'estructura de dades no lineals. Tot i que els termes semblen ser similars, però són diferents en tots els aspectes. S'utilitza un arbre binari quan els registres o les dades s'emmagatzemen a la RAM en lloc del disc ja que la velocitat d'accés a la RAM és molt superior a la del disc. D’altra banda, l’arbre B s’utilitza quan les dades s’emmagatzemen al disc redueix el temps d’accés reduint l’alçada de l’arbre i augmentant les branques del node.

Una altra diferència entre l’arbre B i l’arbre binari és que l’arbre B ha de tenir tots els nodes fills al mateix nivell mentre que l’arbre binari no té aquesta restricció. Un arbre binari pot tenir com a màxim 2 subratges o nodes mentre que en l'arbre B no es pot tenir cap número M de subtreus o nodes on M sigui l'ordre de l'arbre B.

1. Gràfic de comparació
2. Definició
3. Diferències claus
4. Conclusió

Gràfic de comparació

Bases per a la comparació	Arbre B	Arbre binari
Restricció essencial	Un node pot tenir al màxim un nombre M màxim de nodes fills (on M és l'ordre de l'arbre).	Un node pot tenir un màxim de 2 subratges.
Utilitzat	S'utilitza quan les dades es guarden al disc.	S'utilitza quan els registres i les dades es guarden a la RAM.
Alçada de l’arbre	registreM N (on m és l'ordre de l'arbre de la via M)	registre2 N
Aplicació	Estructura de dades d’indexació de codis en molts SGBD.	Optimització de codis, codificació Huffman, etc.

Definició de B-tree

Un arbre B és l’arbre de forma M equilibrat i també conegut com a arbre d’ordenació equilibrada. És semblant a l'arbre de cerca binària on els nodes s'organitzen sobre la base de la travessa d'ordres. La complexitat espacial de l’arbre B és O (n). La complexitat del temps d'inserció i supressió és O (log n).

Hi ha certes condicions que han de ser certes per a un arbre B:

• L’alçada de l’arbre ha d’estar al mínim possible.
• Per sobre de les fulles de l’arbre no hi ha d’haver subtrets buits.
• Les fulles de l’arbre han de situar-se al mateix nivell.
• Tots els nodes haurien de tenir el mínim nombre de fills, tret dels nodes deixats.

Propietats de l'arbre B de l'ordre M

• Cada node pot tenir un nombre M màxim de nens i un nombre mínim de 2 nens / o un número màxim de 2 fins al màxim.
• Cada node té una tecla menys que els nens amb tecles M-1 màxim.
• L’ordenació de les tecles és en algun ordre específic dins dels nodes. Totes les tecles del subtítol presents a l'esquerra de la clau són predecessores de la clau, i les presents a la dreta de la clau s'anomenen successores.
• En el moment d'inserir un node complet, l'arbre es divideix en dues parts i la clau amb valor mitjà s'insereix al node pare.
• L’operació de fusió té lloc quan s’eliminen els nodes.

Definició de Binary tree

Un arbre binari és una estructura d’arbre que pot tenir com a màxim dos indicadors per als seus nodes fills. Vol dir que el màxim grau que pot tenir un node és de 2 i també hi podria haver un node de zero o d’un grau.

Hi ha certes variants d’un arbre binari com ara arbre estrictament binari, arbre binari complet, arbre binari estès, etc.

• L’arbre estrictament binari és un arbre on cada node no terminal ha de tenir un subtítol esquerre i un subtítol dret.
• Un arbre s’anomena arbre binari complet quan satisfà la condició de tenir-ne 2 ^jo nodes a cada nivell on sóc el nivell.
• El binari roscat és un arbre binari que consisteix en un número de nodes o un número de dos nodes.

Tècniques transversals

El creuament arbre és una de les operacions més freqüents realitzades en l'estructura de dades de l'arbre en què cada node va visitar exactament una vegada de manera sistemàtica.

• Inorder: En aquest recorregut d'arbre es visita recursivament el subtree esquerre, després es visita el node arrel i es visita l'últim subtree dret.
• Preorer: en aquest recorregut arbre es visita el node arrel al principi, a continuació, al subtree esquerre ia la subdirecció dreta.
• Postorder: aquesta tècnica visita el subtree esquerre i el subtree dret i al final el node arrel.

1. Al arbre B, el nombre màxim de nodes secundaris que pot tenir un node no terminal és M on M és l'ordre de l'arbre B. D'altra banda, un arbre binari pot tenir com a màxim dos subratges o nodes secundaris.
2. L’arbre B s’utilitza quan les dades s’emmagatzemen al disc mentre que l’arbre binari s’utilitza quan les dades s’emmagatzemen en memòria ràpida com la RAM.
3. Una altra àrea d’aplicació per a l’arbre B és l’estructura de dades d’indexació de codis en DBMS, en canvi, l’arbre binari s’utilitza en l’optimització de codis, la codificació huffman, etc.
4. L’alçada màxima d’un arbre B és el registre_MN (M és l’ordre de l’arbre). En contraposició, l'altura màxima de l'arbre binari és el registre₂N (N és el nombre de nodes i la base és 2 perquè és per a binari).

Conclusió

L’arbre B s’utilitza sobre l’arbre de cerca binari i binari. El principal motiu d’aquest motiu és la jerarquia de memòria on la CPU està connectada a la memòria cau amb els canals d’ample de banda elevats mentre que la CPU es connecta al disc mitjançant un canal d’ample de banda baix. Un arbre binari s’utilitza quan els registres s’emmagatzemen a la memòria RAM (petita i ràpida) i l’arbre B s’utilitza quan els registres s’emmagatzemen al disc (gran i lent). Per tant, l’ús d’arbre B en lloc d’arbre binari redueix significativament el temps d’accés a causa de l’elevat factor de ramificació i l’alçada reduïda de l’arbre.