Un'altra differenza tra l'albero B e l'albero binario è che B-tree deve avere tutti i suoi nodi figli sullo stesso livello, mentre l'albero binario non ha tale vincolo. Un albero binario può avere un massimo di 2 sottoalberi o nodi, mentre in B-tree può avere M no di sottoalberi o nodi dove M è l'ordine dell'albero B.
Grafico comparativo
| Base per il confronto | B-tree | Albero binario |
|---|---|---|
| Vincolo essenziale | Un nodo può avere al massimo il numero M di nodi figli (dove M è l'ordine dell'albero). | Un nodo può avere al massimo 2 numero di sottoalberi. |
| Usato | Viene utilizzato quando i dati sono archiviati su disco. | Viene utilizzato quando record e dati sono archiviati nella RAM. |
| Altezza dell'albero | log M N (dove m è l'ordine dell'albero M-way) | log 2 N |
| Applicazione | Struttura dei dati di indicizzazione del codice in molti DBMS. | Ottimizzazione del codice, codifica Huffman, ecc. |
Definizione di B-tree
Un albero B è l'albero M-way bilanciato e noto anche come albero di ordinamento bilanciato. È simile all'albero di ricerca binario in cui i nodi sono organizzati sulla base di un attraversamento inorder. 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 minimo possibile.
- Sopra le foglie dell'albero, non ci dovrebbero essere sottostrutture vuote.
- Le foglie dell'albero devono venire allo stesso livello.
- Tutti i nodi dovrebbero avere il minor numero di bambini ad eccezione dei nodi di congedo.
Proprietà di B-tree di ordine M
- Ogni nodo può avere il numero M massimo di bambini e il numero minimo M / 2 di bambini o qualsiasi numero compreso tra 2 e il massimo.
- Ogni nodo ha una chiave in meno rispetto ai bambini con i tasti M-1 massimi.
- La disposizione delle chiavi è in qualche ordine specifico all'interno dei nodi. Tutti i tasti nella sottostruttura presente nella parte sinistra della chiave sono i predecessori della chiave e quelli presenti nella parte destra della chiave sono chiamati 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 cancellati.
Definizione di albero binario
Un albero binario è una struttura ad albero che può avere al massimo due puntatori per i suoi nodi figli. Significa che il massimo grado che un nodo può avere è 2 e potrebbe esserci anche il nodo zero o di primo grado.
Ci sono alcune varianti di un albero binario come albero strettamente binario, albero binario completo, albero binario esteso, ecc.
- L'albero strettamente binario è un albero in cui ogni nodo non terminale deve avere lasciato il sottoalbero e il sottoalbero destro.
- Un albero è chiamato albero binario completo quando soddisfa la condizione di avere 2 nodi i ad ogni livello in cui i è il livello.
- Il binario filettato è un albero binario che consiste in 0 no di nodi o 2 numeri di nodi.
Tecniche di Traversal
L'attraversamento dell'albero è una delle operazioni più frequenti eseguite sulla struttura dei dati dell'albero in cui ogni nodo ha visitato esattamente una volta in modo sistematico.
- Inorder: in questo albero trasversale il sottoalbero sinistro viene visitato in modo ricorsivo, quindi viene visitato il nodo principale e nell'ultima sottostruttura destra viene visitato.
- Preordina- In questo albero trasversale il nodo radice viene visitato in un primo momento, quindi il sottostruttura sinistro e infine il sottoalbero destro.
- Postorder: questa tecnica visita il sottoalbero sinistro, quindi il sottoalbero destro e infine il nodo radice.
Differenze chiave tra albero B e albero binario
- Nell'albero B, 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 sottoalberi o nodi figli.
- L'albero B viene utilizzato quando i dati vengono archiviati nel disco mentre l'albero binario viene utilizzato quando i dati vengono archiviati in una memoria veloce come la RAM.
- Un'altra area di applicazione per B-tree è la struttura dei dati di indicizzazione del codice in DBMS, al contrario, l'albero binario viene utilizzato nell'ottimizzazione del codice, nella codifica di huffman, ecc.
- L'altezza massima di un albero B è log M N (M è l'ordine dell'albero). Come contro, l'altezza massima dell'albero binario è log 2 N (N è il numero di nodi e base è 2 perché è per binario).
Conclusione
L'albero B viene utilizzato su albero di ricerca binario e binario il motivo principale dietro questo è 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 il canale a bassa larghezza di banda. Un albero binario viene utilizzato quando i record sono archiviati nella RAM (piccoli e veloci) e l'albero B viene utilizzato quando i record sono archiviati nel disco (grandi e lenti). Quindi, l'uso dell'albero B invece dell'albero binario riduce significativamente il tempo di accesso a causa dell'elevato fattore di ramificazione e dell'altezza ridotta dell'albero.
