Contenuto

• Tabella di comparazione
• Definizione di B-tree
• Proprietà dell'albero B dell'ordine M
• Definizione di albero binario
• Tecniche trasversali
• Conclusione

L'albero B e l'albero binario sono i tipi di struttura dati non lineare. Anche se i termini sembrano essere simili ma diversi in tutti gli aspetti. Un albero binario viene utilizzato quando i record o i dati sono archiviati nella RAM anziché nel disco poiché la velocità di accesso della RAM è molto più alta del disco. D'altra parte, B-tree viene utilizzato quando i dati sono memorizzati nel disco, riduce il tempo di accesso riducendo l'altezza dell'albero e aumentando i rami nel nodo.

Un'altra differenza tra l'albero B e l'albero binario è che l'albero B deve avere tutti i suoi nodi figlio sullo stesso livello mentre l'albero binario non ha tale vincolo. Un albero binario può avere un massimo di 2 sottotitoli o nodi mentre in B-tree può avere M no di sottotitoli o nodi in cui M è l'ordine dell'albero B.

1. Tabella di comparazione
2. Definizione
3. Differenze chiave
4. Conclusione

Tabella di comparazione

Base per il confronto	B-tree	Albero binario
Vincolo essenziale	Un nodo può avere al massimo M numero di nodi figlio (dove M è l'ordine dell'albero).	Un nodo può avere al massimo 2 numero di sottotitoli.
Usato	Viene utilizzato quando i dati sono memorizzati su disco.	Viene utilizzato quando record e dati sono memorizzati nella RAM.
Altezza dell'albero	logM N (dove m è l'ordine dell'albero M-way)	log2 N
Applicazione	Struttura dei dati di indicizzazione del codice in molti DBMS.	Ottimizzazione del codice, codifica Huffman, ecc.

Definizione di B-tree

Un B-tree è l'albero M-way bilanciato e noto anche come albero dell'ordinamento bilanciato. È simile all'albero di ricerca binario in cui i nodi sono organizzati in base all'attraversamento interno. La complessità spaziale di B-tree è O (n). La complessità del tempo di inserimento e cancellazione è O (log n).

Ci sono alcune condizioni che devono essere vere per un albero B:

• L'altezza dell'albero deve essere il più bassa possibile.
• Sopra le foglie dell'albero, non dovrebbero esserci sottotitoli vuoti.
• Le foglie dell'albero devono arrivare allo stesso livello.
• Tutti i nodi dovrebbero avere il minor numero di figli tranne i nodi di uscita.

Proprietà dell'albero B dell'ordine M

• Ogni nodo può avere un numero M massimo di bambini e un numero M / 2 minimo di bambini o qualsiasi numero compreso tra 2 e il massimo.
• Ogni nodo ha una chiave in meno rispetto ai bambini con un massimo di chiavi M-1.
• La disposizione delle chiavi è in un ordine specifico all'interno dei nodi. Tutte le chiavi nella sottostruttura presente a sinistra della chiave sono predecessori della chiave e quelle presenti a destra della chiave sono chiamate successori.
• Al momento dell'inserimento di un nodo completo, l'albero si divide in due parti e la chiave con valore mediano viene inserita nel nodo padre.
• L'operazione di unione ha luogo quando i nodi vengono eliminati.

Definizione di albero binario

Un albero binario è una struttura ad albero che può avere al massimo due puntatori per i suoi nodi figlio. Significa che il grado più alto che un nodo può avere è 2 e che potrebbe esserci anche un nodo zero o un grado.

Esistono alcune varianti di un albero binario come l'albero rigorosamente binario, l'albero binario completo, l'albero binario esteso, ecc.

• L'albero rigorosamente binario è un albero in cui ogni nodo non terminale deve avere sottostruttura sinistra e sottostruttura destra.
• Un albero viene chiamato albero binario completo quando soddisfa la condizione di avere 2 ^io nodi ad ogni livello dove io sono il livello.
• Il binario threaded è un albero binario composto da 0 no di nodi o 2 numero di nodi.

Tecniche trasversali

Il traversal tree è una delle operazioni più frequenti eseguite sulla struttura dei dati degli alberi in cui ogni nodo ha visitato esattamente una volta in modo sistematico.

• Inorder: in questo attraversamento dell'albero la sottostruttura sinistra viene visitata in modo ricorsivo, quindi viene visitato il nodo radice e nell'ultima sottostruttura destra viene visitata.
• Preoratore: in questo attraversamento dell'albero il nodo radice viene visitato dapprima poi sottostruttura sinistra e infine sottostruttura destra.
• Postorder: questa tecnica visita la sottostruttura sinistra e poi la sottostruttura destra e infine il nodo radice.

1. In B-tree, il numero massimo di nodi figlio che un nodo non terminale può avere è M dove M è l'ordine dell'albero B. D'altra parte, un albero binario può avere al massimo due sottostrutture o nodi figlio.
2. B-tree viene utilizzato quando i dati vengono archiviati su disco mentre l'albero binario viene utilizzato quando i dati vengono archiviati in una memoria veloce come la RAM.
3. Un'altra area di applicazione per B-tree è la struttura dei dati di indicizzazione del codice in DBMS, al contrario, l'albero binario è impiegato nell'ottimizzazione del codice, nella codifica huffman, ecc.
4. L'altezza massima di un albero a B è log_MN (M è l'ordine dell'albero). Al contrario, l'altezza massima dell'albero binario è log₂N (N è il numero di nodi e base è 2 perché è per binario).

Conclusione

L'albero B viene utilizzato sull'albero di ricerca binario e binario, il motivo principale alla base di questa è la gerarchia di memoria in cui la CPU è collegata alla cache con i canali ad alta larghezza di banda mentre la CPU è collegata al disco attraverso un canale a bassa larghezza di banda. Un albero binario viene utilizzato quando i record sono archiviati nella RAM (piccola e veloce) e B-tree viene usato quando i record sono memorizzati nel disco (grande e lento). Pertanto, l'uso dell'albero B anziché dell'albero binario riduce significativamente i tempi di accesso a causa dell'elevato fattore di ramificazione e dell'altezza ridotta dell'albero.