Un albero B è un albero di ricerca auto-bilanciato dove ogni nodo contiene molte chiavi e ha molti figli (alto fanout). Questo mantiene l'albero poco profondo, minimizzando il numero di letture da disco — esattamente ciò di cui hanno bisogno i database e i filesystem.
Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks)
B-tree, 100 keys/node -> height ~3 (3 disk seeks)
Each node = one disk block/page read.
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
In un albero B+, tutti i valori risiedono nelle foglie e le foglie sono collegate, quindi le scansioni di intervallo percorrono una lista collegata di foglie — ideale per query come WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operazione | Tempo | I/O da disco |
|---|---|---|
| ricerca | O(log n) | O(altezza) |
| inserimento / cancellazione | O(log n) | O(altezza) |
| scansione intervallo | O(log n + k) | foglie sequenziali |
L'accesso a disco e SSD è ordini di grandezza più lento della memoria, quindi la metrica che conta è il numero di I/O, non il numero di confronti.
Un alto fanout riduce drasticamente gli I/O mantenendo l'albero a soli pochi livelli di profondità.
Ecco perché praticamente ogni indice di database relazionale (e molti filesystem) è costruito su alberi B+ piuttosto che su alberi di ricerca binari.