B-ağaç, her düğümün birçok anahtarı tuttuğu ve birçok çocuğa sahip olduğu kendi kendine dengeli bir arama ağacıdır (yüksek fanout). Bu, ağacı sığ tutarak disk okuma sayısını en aza indirir — bu da veritabanlarının ve dosya sistemlerinin ihtiyaç duyduğu şeydir.
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
Bir B+ ağaçta, tüm değerler yapraklarda yaşar ve yapraklar bağlantılı olduğundan, aralık taramaları yaprakların bağlantılı bir listesinde yürür — WHERE age BETWEEN 20 AND 40 gibi sorgular için idealdir.
internal nodes: keys only (routing)
leaves: [..]<->[..]<->[..] <- linked for fast range scans
| İşlem | Zaman | Disk I/O |
|---|---|---|
| arama | O(log n) | O(yükseklik) |
| ekleme / silme | O(log n) | O(yükseklik) |
| aralık taraması | O(log n + k) | sıralı yapraklar |
Disk ve SSD erişimi bellekten büyüklük sırası kadar daha yavaştır, bu nedenle önemli olan metrik karşılaştırma değil, I/O sayısıdır.
Yüksek fanout, ağacı sadece birkaç seviyede tutarak I/O'yu drastik şekilde azaltır.
Bu nedenle hemen hemen her ilişkisel veritabanı indeksi (ve birçok dosya sistemi) ikili arama ağaçları yerine B+ ağaçlar üzerine inşa edilmiştir.