Albero binario etichettato in cui per ogni nodo il sottoalbero sinistro contiene solo etichette minori di quella del nodo e il sottoalbero destro etichette maggiori
Tempo di ricerca (e inserimento), pari alla profondità:
Ogni nodo ha (fino a) P figli e (fino a) P-1 etichette, ordinate
Nell’i-esimo sottoalbero abbiamo tutte etichette maggiori della (i-1)-esima etichetta e minori della i-esima
Ogni ricerca o modifica comporta la visita di un cammino radice foglia
In strutture fisiche, un nodo corrisponde di solito ad un blocco e quindi ogni nodo intermedio ha molti figli (un “fan-out” molto grande, pari al fattore di blocco dell’indice)
All’interno di un nodo, la ricerca è sequenziale (ma in memoria centrale)
La struttura è ancora (potenzialmente) rigida
Albero di ricerca in cui ogni nodo corrisponde ad un blocco, viene mantenuto perfettamente bilanciato (tutte le foglie sono allo stesso livello), grazie a:
