Differenza fondamentale: nei computer, gli alberi binari sono strutture di dati ad albero che memorizzano i dati e consentono all'utente di accedere, cercare, inserire ed eliminare i dati al momento dell'algoritmo. La differenza tra un albero B e B + è che, in un albero B, le chiavi e i dati possono essere memorizzati sia nei nodi interni che in quelli foglia, mentre in un albero B +, i dati e le chiavi possono essere memorizzati solo nei nodi foglia .
Gli alberi binari sono alberi di ricerca bilanciati progettati per funzionare correttamente su dispositivi di archiviazione secondari ad accesso diretto come i dischi magnetici. Rudolf Bayer e Ed McCreight hanno inventato il concetto di un albero B.
Un albero B è un albero di ricerca binario generalizzato, in cui ogni nodo può avere più di due figli. Ogni nodo interno in un albero B contiene un numero di chiavi. Queste chiavi separano i valori e formano ulteriormente i sotto-alberi. I nodi interni in un albero B possono avere numeri variabili di nodi figli, che sono disposti all'interno di un intervallo predefinito. Nel momento in cui qualsiasi dato viene inserito o rimosso da un rispettivo nodo, si verifica una modifica del numero di nodi figlio. Per mantenere l'intervallo predefinito, i nodi interni possono essere uniti o divisi. In un albero B, è consentito un intervallo di nodi figli, a causa del quale deve essere mantenuto l'intervallo predefinito.
Gli alberi B non devono essere ribilanciati frequentemente a differenza di altri alberi di ricerca autoequilibranti. I nodi in questi alberi non sono sempre pieni; quindi, gli spazi sono consumati inutili in questi alberi che conducono allo spreco di spazio. Solitamente i limiti inferiore e superiore sul numero di nodi figli sono generalmente fissati per una particolare implementazione. Ad esempio, in un albero B 2-3 (spesso chiamato semplicemente albero 2-3), ciascun nodo interno può avere solo 2 o 3 nodi figlio.
Inoltre, l'albero B è ottimizzato per i sistemi che leggono e scrivono grandi blocchi di dati. È comunemente usato nei database e nei file system. Nell'albero B, tutti i nodi vengono mantenuti alle stesse profondità di bilanciamento dai nodi radice. Queste profondità aumentano lentamente all'aumentare del numero di elementi; ciò comporta che tutti i nodi foglia sono un altro nodo più lontano dalla radice. Inoltre, gli alberi B sono più vantaggiosi rispetto ad altre implementazioni rispetto al tempo impiegato per accedere ai dati.
Un albero B + è un albero n-array con un nodo, che consiste in un numero elevato di bambini per nodo. La radice può essere una foglia o un nodo che contiene più di due bambini. Un albero B + è costituito da una radice, nodi interni e foglie.
Un albero B + è uguale a un albero B; l'unica differenza è che nell'albero B + c'è un ulteriore livello aggiunto in fondo con le foglie collegate. Inoltre, a differenza dell'albero B, ogni nodo in un albero B + contiene solo chiavi e non coppie chiave-valore.
Inoltre, il fattore di bilanciamento o l'ordine di un albero B + misura la capacità per i nodi interni di un albero, ovvero il numero di nodi che possono avere. Il numero effettivo di figli per un nodo è limitato per i nodi interni. La radice è tuttavia un'eccezione in quanto è consentito avere più di due numeri di bambini. Ad esempio, se l'ordine di un albero B + è 7, ciascun nodo interno (ad eccezione della radice) può avere tra 4 e 7 figli; mentre la radice può avere tra 2 e 7. Il valore primario dell'albero B + è nella memorizzazione dei dati per un recupero efficiente in un contesto di archiviazione orientato ai blocchi e in particolari sistemi di file.
Il valore primario dell'albero B + è nella memorizzazione e nella gestione dei dati, in modo che i dati non vadano persi. Questo approccio è applicato in particolare nel contesto di archiviazione orientato ai blocchi e in alcuni particolari sistemi di file. Le foglie, che sono i blocchi indice più in basso, dell'albero B + sono spesso collegate l'una con l'altra in una lista collegata; quindi questo semplifica e rende più efficienti le query di intervallo o un'iterazione ordinata attraverso i blocchi. Inoltre, il fattore spazio non viene sprecato negli alberi B +. L'albero B + fornisce un efficiente formato di struttura dei dati dell'alloggiamento, che li rende semplici nell'accesso e nella memorizzazione. Gli alberi B + sono particolarmente utili come indice di sistema del database, in cui i dati risiedono in genere su un disco.
Confronto tra Albero B e Albero B +:
B Albero | Albero B + | |
Brevi descrizioni web | L'albero AB è una struttura organizzativa per l'archiviazione e il recupero delle informazioni sotto forma di un albero in cui tutti i nodi terminali si trovano alla stessa distanza dalla base e tutti i nodi non terminali hanno tra n e 2 n sotto-alberi o puntatori (dove n è un numero intero). | L'albero B + è un albero n-array con un numero variabile ma spesso elevato di bambini per nodo. Un albero B + è costituito da una radice, nodi interni e foglie. La radice può essere una foglia o un nodo con due o più figli. |
Conosciuto anche come | Albero equilibrato | Albero B plus. |
Spazio | Sopra) | Sopra) |
Ricerca | O (log n) | O (log b n) |
Inserire | O (log n) | O (log b n) |
Elimina | O (log n) | O (log b n) |
Conservazione | In un albero B, chiavi di ricerca e dati memorizzati nei nodi interni o foglia. | In un albero B +, i dati sono memorizzati solo nei nodi foglia. |
Dati | I nodi foglia dei tre puntatori del negozio registrano anziché i record effettivi. | I nodi foglia dell'albero memorizzano il record effettivo anziché i puntatori ai record. |
Spazio | Questi alberi sprecano spazio | Lì gli alberi non sprecano spazio. |
Funzione dei nodi foglia | Nell'albero B, il nodo foglia non può essere memorizzato utilizzando la lista collegata. | Nell'albero B +, i dati del nodo foglia vengono ordinati in un elenco collegato sequenziale. |
Ricerca | Qui, la ricerca diventa difficile in B-tree poiché i dati non possono essere trovati nel nodo foglia. | Qui, la ricerca di qualsiasi dato in un albero B + è molto semplice perché tutti i dati si trovano nei nodi foglia. |
Cerca accessibilità | Qui in B tree la ricerca non è così facile rispetto a un albero B +. | Qui in B + tree la ricerca diventa facile. |
Chiave ridondante | Non memorizzano la chiave di ricerca ridondante. | Memorizzano la chiave di ricerca ridondante. |
applicazioni | Sono una versione precedente e non sono così vantaggiosi rispetto agli alberi B +. | Molti implementatori di sistemi di database preferiscono la semplicità strutturale di un albero B +. |
