Gli alberi B* sono un caso speciale (di interesse per lo più storico) di alberi B+ che garantiscono che i nodi siano pieni almeno per 2/3.
Lo fanno richiedendo che il nodo radice sia grande 2 pagine di disco, e usando un algoritmo di divisione dei nodi che divide due nodi pieni in tre nodi pieni per 2/3, e un algoritmo di fusione dei nodi che unisce tre nodi pieni per 2/3 in due nodi pieni. L'algoritmo di divisione sposta anche gli elementi sui nodi adiacenti quando un nodo è pieno ma i suoi vicini non lo sono. L'algoritmo di fusione prende in prestito elementi dai nodi vicini quando è meno di 2/3 pieno ma i suoi vicini non lo sono. Il lavoro extra coinvolto in questi algoritmi significa che non sono stati implementati nella pratica.
Gli alberi B+ sono ancora la struttura ad albero di archiviazione secondaria più rilevante, quindi vale la pena conoscerli più in dettaglio. Garantiscono che i nodi siano pieni almeno per metà, e che tutti i dati siano memorizzati in un insieme sequenziale collegato di nodi foglia a cui si può accedere senza attraversare la struttura ad albero, quindi l'accesso sequenziale è molto efficiente. L'algoritmo di cancellazione prende anche in prestito i dati dai nodi vicini quando il nodo che ha cancellato un elemento è pieno per meno di metà, ma questo è raramente implementato correttamente, anche se comporta solo una modesta penalità in termini di prestazioni.
Gli alberi B non hanno l'accesso sequenziale efficiente o le garanzie di contenuto dei nodi, quindi nel caso patologico si accede a tanti nodi quanti sono gli elementi dei dati.
TL,DR Gli alberi B* sono un caso speciale degli alberi B+, che erano interessanti da considerare quando lo stoccaggio su disco era molto costoso, ma hanno penalità di prestazione e sincronizzazione che limitano la loro implementazione pratica.
Ilgiardino.wiki
Gli alberi B* sono un caso speciale (di interesse per lo più storico) di alberi B+ che garantiscono che i nodi siano pieni almeno per 2/3.
Lo fanno richiedendo che il nodo radice sia grande 2 pagine di disco, e usando un algoritmo di divisione dei nodi che divide due nodi pieni in tre nodi pieni per 2/3, e un algoritmo di fusione dei nodi che unisce tre nodi pieni per 2/3 in due nodi pieni. L'algoritmo di divisione sposta anche gli elementi sui nodi adiacenti quando un nodo è pieno ma i suoi vicini non lo sono. L'algoritmo di fusione prende in prestito elementi dai nodi vicini quando è meno di 2/3 pieno ma i suoi vicini non lo sono. Il lavoro extra coinvolto in questi algoritmi significa che non sono stati implementati nella pratica.
Gli alberi B+ sono ancora la struttura ad albero di archiviazione secondaria più rilevante, quindi vale la pena conoscerli più in dettaglio. Garantiscono che i nodi siano pieni almeno per metà, e che tutti i dati siano memorizzati in un insieme sequenziale collegato di nodi foglia a cui si può accedere senza attraversare la struttura ad albero, quindi l'accesso sequenziale è molto efficiente. L'algoritmo di cancellazione prende anche in prestito i dati dai nodi vicini quando il nodo che ha cancellato un elemento è pieno per meno di metà, ma questo è raramente implementato correttamente, anche se comporta solo una modesta penalità in termini di prestazioni.
Gli alberi B non hanno l'accesso sequenziale efficiente o le garanzie di contenuto dei nodi, quindi nel caso patologico si accede a tanti nodi quanti sono gli elementi dei dati.
TL,DR Gli alberi B* sono un caso speciale degli alberi B+, che erano interessanti da considerare quando lo stoccaggio su disco era molto costoso, ma hanno penalità di prestazione e sincronizzazione che limitano la loro implementazione pratica.