Ett B-träd är ett själv-balanserat sökträd där varje nod innehåller många nycklar och har många barn (högt fanout). Detta håller trädet grunt, vilket minimerar antalet diskläsningar — vilket är exakt vad databaser och filsystem behöver.
Ett B-träd är ett själv-balanserat sökträd där varje nod innehåller många nycklar och har många barn (högt fanout). Detta håller trädet grunt, vilket minimerar antalet diskläsningar — vilket är exakt vad databaser och filsystem behöver.
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 ett B+ träd ligger alla värden i bladen och bladen är länkade, så intervallsökningar går igenom en länkad lista av blad — ideal för frågor som WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operation | Tid | Disk I/O |
|---|---|---|
| sökning | O(log n) | O(höjd) |
| insättning / borttagning | O(log n) | O(höjd) |
| intervallsökning | O(log n + k) | sekventiella blad |
Disk- och SSD-åtkomst är storleksordningar långsammare än minne, så måttet som spelar roll är I/O-antal, inte jämförelser.
Högt fanout minskar I/O drastiskt genom att hålla trädet bara några få nivåer djupt.
Det är därför nästan alla relationsdatabas-index (och många filsystem) är byggda på B+ träd snarare än binära sökträd.