B-medis yra savaime balansuojamas paieškos medis, kuriame kiekvienas mazgas turi daug raktų ir turi daug vaikų (aukštas fanout). Tai leidžia medžiui likti sekliam, sumažinant disko skaitymo operacijų skaičių — tai būtent tai, ko reikalinga duomenų bazėms ir failų sistemoms.
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+ medyje visos reikšmės gyvena lapuose ir lapai yra susieti, todėl diapazonų nuskaitymas eina per susietą lapų sąrašą — idealu tokiems užklausoms kaip WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operacija | Laikas | Disko I/O |
|---|---|---|
| paieška | O(log n) | O(aukštis) |
| įterpimas / trynimas | O(log n) | O(aukštis) |
| diapazonų nuskaitymas | O(log n + k) | nuoseklūs lapai |
Disko ir SSD prieiga yra kelis dydžius lėtesnė nei atmintis, todėl svarbi metrika yra I/O skaičius, o ne palyginimų skaičius.
Aukštas fanout drastiškai sumažina I/O, laikydamas medį tik keliomis paklaidų.
Esnė yra, kad beveik kiekvienas reliacinis duomenų bazės indeksas (ir daugelis failų sistemų) yra pastatytas ant B+ medžių, o ne dvejetainių paieškos medžių.