A B-tree iku pohon pencarian sing mbales dhewe, ing kono saben node duwe akeh kunci lan duwe akeh anak (tinggi fanout). Iki njaga supaya pohon kasebut cethak, ngurangi jumlah waca disk — sing persis apa sing kuwi database lan filesystem butuh.
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
In a B+ tree, semua nilai manggon ing godhong lan godhong ketutupan, dadi range scan mlakoni linked list saka godhong — cocok banget kanggo query kaya WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operasi | Wektu | Disk I/O |
|---|---|---|
| pencarian | O(log n) | O(tinggi) |
| sisip / ilang | O(log n) | O(tinggi) |
| range scan | O(log n + k) | godhong urut |
Akses disk lan SSD luwih alon berkali-kali tinimbang memori, dadi metrik sing penting iku jumlah I/O, dudu comparisons.
Fanout tinggi nyudut I/O kanthi njaga pohon tetep cethak sawetara tingkat.
Iki sebabe meh saben indeks database relasional (lan akeh filesystem) dibangun ana B+ trees tinimbang binary search trees.