B-tree huwa siġra ta' tfittxija li tqabbel ruħha, fejn kull nodu jżomm ħafna ċwievet u għandu ħafna ulied (fanout għoli fanout). Dan iżomm is-siġra mħallfa, it-tnaqqis tan-numru ta' qari mid-disk — li huwa eżattament dak li d-databases u l-filesystems għandhom bżonn.
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
F'B+ tree, il-valuri kollha jgħixu fil-weraqat u l-weraqat huma *maqsuma, għalhekk il-qari tal-firxa jikkamina minn lista maqsuma ta' weraqat — ideali għal queries bħal WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operazzjoni | Ħin | I/O tad-Disk |
|---|---|---|
| tfittxija | O(log n) | O(għolja) |
| daħħal / iħassar | O(log n) | O(għolja) |
| qari tal-firxa | O(log n + k) | weraqat sekwenzjali |
L-aċċess tad-disk u SSD huwa ordini ta' magnitude aktar bil-ġidwa mill-memorja, għalhekk il-metrika li tħareġ huwa *il-għadd ta' I/O, mhux il-parità.
Fanout għoli inaqqas l-I/O drastikament billi jżomm is-siġra ftit livelli biss il-fond.
Dan huwa għaliex kważi kull indiċi ta' database relazzjonali (u ħafna filesystems) huma mibnija fuq B+ trees minflok siġar ta' tfittxija binarja.