B-albero

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Un B-albero (in inglese B-tree) è una struttura dati che permette la rapida localizzazione dei file (record o chiavi), specie nelle basi di dati, riducendo il numero di volte che un utente necessita per accedere alla memoria in cui il dato è salvato. Essi derivano dagli alberi binari di ricerca, in quanto ogni chiave appartenente al sottoalbero sinistro di un nodo è di valore inferiore rispetto a ogni chiave appartenente ai sottoalberi alla sua destra; inoltre, la loro struttura ne garantisce il bilanciamento: per ogni nodo, le altezze dei sottoalberi destro e sinistro differiscono al più di una unità. Questo è il vantaggio principale del B-albero, e permette di compiere operazioni di inserimento, cancellazione e ricerca in tempi ammortizzati logaritmicamente.

Sono utilizzati spesso nell'ambito delle basi di dati, in quanto permettono di accedere ai nodi in maniera efficiente sia nel caso essi siano disponibili in memoria centrale (tramite una cache), sia qualora essi siano presenti solo sulla memoria di massa.