A B-tree is een zelf-balancerende zoekboom waar elk knooppunt veel sleutels bevat en veel kinderen heeft (hoge fanout). Dit houdt de boom ondiep, wat het aantal disk reads minimaliseert — precies wat databases en filesystemen nodig hebben.
Waarom hoge fanout beter is dan een binaire boom
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.
Structuur (B-tree order 4)
[ 17 | 35 ]
/ | \
[4|9|12] [20|28] [40|50|60]
each node packs many keys -> few levels
B+ tree verfijning
In een B+ tree leven alle waarden in de bladeren en bladeren zijn gekoppeld, dus range scans lopen door een gekoppelde lijst van bladeren — ideaal voor query's zoals WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
Complexiteit
| Operatie | Tijd | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Waarom het belangrijk is
Disk- en SSD-toegang is vele orden van grootte langzamer dan geheugen, dus de maatstaf die telt is I/O-aantal, niet vergelijkingen.
Hoge fanout vermindert I/O drastisch door de boom slechts enkele niveaus diep te houden.
Dit is waarom vrijwel elke relationele database-index (en veel filesystemen) is gebouwd op B+ trees in plaats van binaire zoekbomen.