Et B-træ er et selvbalanceret søgetræ, hvor hver knude indeholder mange nøgler og har mange børn (høj fanout). Dette holder træet lavt, hvilket minimerer antallet af disk reads — hvilket er præcis det, som databaser og filsystemer har brug for.
Et B-træ er et selvbalanceret søgetræ, hvor hver knude indeholder mange nøgler og har mange børn (høj fanout). Dette holder træet lavt, hvilket minimerer antallet af disk reads — hvilket er præcis det, som databaser og filsystemer har brug for.
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+-træ lever alle værdier i bladene og bladene er forbundne, så rækkeviddescanninger går gennem en linket liste af blade — ideelt til forespørgsler som WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Tid | Disk I/O |
|---|---|---|
| search | O(log n) | O(height) |
| insert / delete | O(log n) | O(height) |
| range scan | O(log n + k) | sequential leaves |
Disk- og SSD-adgang er mange størrelsesordener langsommere end hukommelse, så den metrik, der betyder noget, er I/O-antal, ikke sammenligninger.
Høj fanout reducerer I/O drastisk ved at holde træet kun få niveauer dybt.
Dette er grunden til, at næsten alle relationelle databaseindekser (og mange filsystemer) er bygget på B+-træer snarere end binære søgetræer.