A B-tree er et selvbalanserende søketre der hver node holder mange nøkler og har mange barn (høy fanout). Dette holder treet grunt, noe som minimerer antallet disklesinger — noe som er nøyaktig det databaser og filsystemer trenger.
A B-tree er et selvbalanserende søketre der hver node holder mange nøkler og har mange barn (høy fanout). Dette holder treet grunt, noe som minimerer antallet disklesinger — noe som er nøyaktig det databaser og filsystemer trenger.
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
I et B+ tree bor alle verdier i bladene og bladene er lenket, så områdesøk går gjennom en lenket liste av bladene — ideelt for spørringer som WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operasjon | Tid | Disklesing |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk- og SSD-tilgang er størrelsesordener langsommere enn minne, så målingen som betyr noe er I/O-antall, ikke sammenligninger.
Høy fanout reduserer I/O dramatisk ved å holde treet bare noen få nivåer dypt.
Dette er grunnen til at nesten alle relasjonsdatabaseindekser (og mange filsystemer) er bygget på B+ trær i stedet for binære søketrær.