B-tree adalah pohon pencarian yang seimbang sendiri di mana setiap nod memegang banyak kunci dan memiliki banyak anak (tinggi fanout). Ini membuat pohon tetap cetek, meminimalkan jumlah pembacaan disk — yang sama sekali apa yang dibutuhkan oleh pangkalan data dan sistem berkas.
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
Dalam B+ tree, semua nilai tinggal di daun dan daun adalah tertaut, jadi pemindaian jangkauan berjalan melalui daftar tertaut daun — ideal untuk kueri seperti WHERE age BETWEEN 20 AND 40.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| Operasi | Waktu | I/O Disk |
|---|---|---|
| pencarian | O(log n) | O(tinggi) |
| sisipkan / hapus | O(log n) | O(tinggi) |
| pindai jangkauan | O(log n + k) | daun berurutan |
Akses disk dan SSD jauh lebih lambat daripada memori, jadi metrik yang penting adalah jumlah I/O, bukan perbandingan.
Fanout tinggi mengurangi I/O secara drastis dengan membuat pohon tetap hanya beberapa tingkat dalam.
Ini adalah mengapa hampir setiap indeks pangkalan data relasional (dan banyak sistem berkas) dibangun di atas B+ trees daripada pohon pencarian biner.