B-tree, B+ tree ve disk I/O

B-tree yüksek dallanma ile disk erişim sayısını azaltır. Bir sayfaya birçok anahtar/sınırlayıcı sığar; bir sayfa okuması arama alanını büyük oranda daraltır. Minimum degree t sözleşmesinde root hariç düğümler t−1 ile2t−1 anahtar taşır ve bütün yapraklar aynı derinliktedir.

B+ tree iç düğümlerde yönlendirme anahtarları, yapraklarda kayıt/record referansları tutar; linked leaves aralık taramasını destekler. Eklemede dolu sayfa split edilir, ayırıcı yukarı çıkar. Silmede borrow/merge alt doluluk sınırını korur. Transaction, page latch, crash recovery ve write-ahead logging gerçek veritabanı indeksinde ayrıca gerekir.

“Bütün veritabanı ve dosya sistemleri aynı B+ tree kullanır” doğru değildir. İndeks tipleri, LSM-tree, hash, inverted ve spatial yapılar farklı işlerde seçilir; engine/indeks bazında doğrula. CPU karşılaştırmalarından ziyade blok I/O modelini kullan. Büyüyen anahtar boyutu fan-out'u düşürebilir.

İndeksi disk modeliyle düşün

Binary tree yükseklik O(log₂ n) olsa bile her node başka disk block'undaysa çok I/O gerekir. B-tree node'u çok sayıda key/child pointer'ı bir block'a paketler. Fanout F olduğunda yükseklik yaklaşık log_F n seviyesindedir. Key ve pointer boyutu büyüdükçe aynı block'a sığan F küçülür; covering index veya composite key maliyeti yalnız key sayısıyla ölçülmez.

B+ tree'de kayıt veya record pointer'ları leaf düzeyindedir; iç key'ler yönlendirme yapar. Leaf linkleri range scan'i destekler: önce başlangıç leaf'ini bul, sonra komşu leaf'lerde sırayla devam et. Duplicate key, separator seçimi ve split sonrası parent update kuralları uygulamaya bağlıdır.

Insertion bir leaf'i taşırırsa split, parent'a separator eklenmesi ve gerekirse root split yapılır. Deletion'da minimum occupancy korunur; komşudan borrow veya merge gerekir. Concurrent implementation latch coupling ve page recovery gibi ek sorunlar taşır. SQL index isolation ve durability garantileri yalnız B+ tree veri yapısından gelmez; transaction/log sistemi de çalışır.

Temel: Fanout 100 için milyon kayıt kabaca kaç seviye ister? Orta: Bir range scan'in output block maliyetini ekle. İleri: Random insert ile sequential insert'te page split, fill factor ve write amplification ölç; “her relational DB aynı index'i kullanır” genellemesinden kaçın.

from bisect import bisect_right
# Routing separators; records are not stored here.
separators = [20, 40]
assert bisect_right(separators, 19) == 0
assert bisect_right(separators, 20) == 1
assert bisect_right(separators, 41) == 2