Prefazione

In una prima fase la presente relazione analizza alcune realta' che necessitano di maggiori prestazioni nelle operazioni di ricerca.
La struttura dati albero fornisce un costo di ricerca pari alla lunghezza del cammino da effettuare.
I B-Tree, alberi bilanciati, assicurano per tutti gli elementi un costo di ricerca inferiore ad un valore di soglia, determinato dall'altezza dell'albero.
Nei B-Tree* tale costo viene ulteriormente ridotto grazie ad una strategia che limita lo spreco di spazio.
La presente relazione presenta anche un'altra variante B-Tree, denominata B-Tree+, il cui scopo e' annullare il costo della lettura sequenziale dei dati.
La strategia di minor spreco, sfruttata con successo dai B-Tree*, applicata ai B-Tree+, da' origine alla variante B-Tree++.

Conclusioni

Per le sue proprieta' i B-Tree sono molto utilizzati nella la gestione della memoria secondaria, e per indicizzare le tabelle delle basi di dati.
Ulteriori studi su questa struttura dati hanno portato alla definizione di alcune varianti, al fine di migliorare le prestazioni in casi particolari.
La necessita' di occupare meno spazio e quindi avere B-tree con minore altezza ha portato alla definizione della variante denominata B-Tree*.
Questa, con la sua diversa gestione dei nodi pieni, risulta pero' molto piu' complessa della sua antenata.
Applicazioni in basi di dati hanno indotto a definire un'altra variante, denominata B-Tree+, che minimizza il tempo di lettura sequenziale dei dati,
anche a costo di un maggiore uso di memoria per la rappresentazione.
Queste due varianti possono essere fuse portando alla definizione dei B-Tree++, che inglobano i pregi di entrambe.
I B-Tree++ sono molto usati nei filesystem e come indici nelle basi di dati.