B-drevo je samouravnoteženo iskalno drevo, kjer vsako vozlišče vsebuje številne ključe in ima številne otroke (visok fanout). To drevo drži plitko, kar minimizira število branj s diska — kar je natanko tisto, kar potrebujejo baze podatkov in datotečni sistemi.
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
V B+ drevesu vse vrednosti živijo v listih in listi so povezani, zato pregledi območja hodijo po povezanem seznamu listov — idealno za poizvedbe kot WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operacija | Čas | Disk I/O |
|---|---|---|
| iskanje | O(log n) | O(višina) |
| vstavljanje / brisanje | O(log n) | O(višina) |
| pregled območja | O(log n + k) | zaporedni listi |
Dostop do diska in SSD je neskončno počasnejši kot dostop do pomnilnika, zato je metrika, ki je pomembna, število I/O, ne primerjav.
Visok fanout drastično zmanjša I/O s tem, da drevo drži samo na nekaj nivojih.
To je razlog, zakaj je skoraj vsak indeks relacijske baze podatkov (in številni datotečni sistemi) zgrajen na B+ drevesih namesto na binarnih iskalnih drevesih.