B-puu on itsestään tasapainottava hakupuu, jossa jokainen solmu sisältää monia avaimia ja joilla on monia lapsia (korkea fanout). Tämä pitää puun matalana, minimoiden levyjen lukumäärän — juuri sitä mitä tietokannat ja tiedostojärjestelmät tarvitsevat.
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
B+ puussa kaikki arvot asuvat lehdissä ja lehdet ovat linkitettyjä, joten alueen skannaamiset kävelevät linkitettynä lehtien luettelona — ihanteellinen kyselyille kuten WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operaatio | Aika | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Levyn ja SSD-käyttö on useita kertaluokkia hitaampaa kuin muisti, joten mittari joka merkitsee on I/O-luku, ei vertailut.
Korkea fanout vähentää I/O:ta dramaattisesti pitämällä puun vain muutaman tason syvyytenä.
Tämä on syy siihen, että lähes jokainen relaatiotietokannan indeksi (ja monet tiedostojärjestelmät) on rakennettu B+ puille binäärihakupuiden sijaan.