B-Ağaçları

Önceki ders, düğüm başına anahtar sayısını artırmanın ağacı sığlaştırdığını gösterdi. Bu dersin sorusu şudur: sayı neden ikide veya üçte durdurulsun?

Yanıt, verinin nerede durduğuna bağlıdır. Veri bellekteyse fark küçüktür — bellek erişimi zaten ucuzdur. Veri diskteyse durum değişir ve bu değişim, bir veri yapısı ailesinin tümüyle bu koşula göre tasarlanmasına yol açmıştır.

Blok Gerçeği

Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi, kalıcı depolamayı en alt katmana yerleştiriyordu: erişim, ana bellekten mertebelerce yavaştır.

İkinci ve daha belirleyici gerçek şudur: kalıcı depolama blok düzeyinde okunur. Tek bir bayt istense de bloğun tamamı — kilobaytlar mertebesinde — getirilir. Dolayısıyla maliyeti belirleyen şey okunan bayt sayısı değil, kaç blok okunduğudur.

Bu, ağaç tasarımını doğrudan değiştirir. Bellek içi bir ağaçta hedef, karşılaştırma sayısını azaltmaktır; disk üzerindeki bir ağaçta hedef, düğüm ziyareti sayısını azaltmaktır. Her düğüm ziyareti bir blok okumasıdır.

Sonuç açıktır: düğüm, bloğu dolduracak kadar büyük olmalıdır. Düğüm bloktan küçük olursa getirilen bloğun bir bölümü boşa gider; büyük olursa tek bir düğüm için birden çok blok okunur. İki durumda da okuma sayısı gereksiz yere artar.

B-Ağacı

B-ağacı, 2-3 ağacının genelleştirilmiş hâlidir. Bir $t$ parametresi (en küçük derece) seçilir ve şu kurallar korunur:

• Kök dışındaki her düğüm en az $t-1$, en fazla $2t-1$ anahtar taşır.
• Anahtar sayısı $k$ olan iç düğümün $k+1$ çocuğu vardır.
• Tüm yapraklar aynı derinliktedir.

$t = 2$ alındığında 2-3-4 ağacı elde edilir; pratikte $t$, düğümün bir bloğa sığacağı en büyük değer olarak seçilir — yüzler mertebesinde.

Ekleme ve silme, önceki dersteki bölünme ve birleştirme kurallarının aynısıdır. Taşan düğüm ikiye bölünür, orta anahtar terfi eder; anahtarsız kalan düğüm kardeşinden ödünç alır ya da onunla birleşir.

Yüksekliğin Sonucu

Dallanma çarpanının yüksek olması, yüksekliği çarpıcı biçimde düşürür:

$$h \approx \log_{b} n$$

Burada $b$ ortalama dallanma çarpanıdır.

import math

def yukseklik(kayit_sayisi: int, dallanma: int) -> int:
    """Verilen dallanma çarpanıyla ağacın yaklaşık yüksekliği."""
    return math.ceil(math.log(kayit_sayisi, dallanma))


for dallanma in (2, 3, 100, 500):
    print(dallanma, yukseklik(1_000_000, dallanma), yukseklik(1_000_000_000, dallanma))

# 2   20 30
# 3   13 19
# 100 3  5
# 500 3  4

Bir milyon kayıt, ikili ağaçta yirmi düğüm ziyareti gerektirir; dallanma çarpanı yüz olan bir B-ağacında üç. Disk erişimi baskın maliyet olduğunda bu, yirmi blok okuması ile üç blok okuması arasındaki farktır.

Bir milyar kayıtta bile derinlik beştir. Kökün ve üst seviyelerin bellekte önbelleklenmesi düşünüldüğünde, gerçek disk erişimi genellikle bir veya iki bloğa iner.

B+ Ağacı

Yaygın olarak kullanılan varyant B+ ağacıdır ve iki değişiklik içerir:

Kayıtlar yalnızca yapraklarda tutulur. İç düğümler yalnızca yönlendirme anahtarları taşır. Bu, iç düğümlerin daha çok anahtar sığdırmasını sağlar — dallanma çarpanı artar, ağaç daha da sığlaşır.

Yapraklar birbirine bağlıdır. Her yaprak, bir sonrakini gösterir; yapraklar sıralı bir bağlı liste oluşturur.

İkinci değişiklik, aralık sorgularını dönüştürür. “Değeri 100 ile 200 arasında olan tüm kayıtlar” sorgusu, sade B-ağacında ağacın tekrar tekrar gezilmesini gerektirirdi. B+ ağacında ise başlangıç noktası bir kez aranır, ardından yaprak zinciri boyunca sıralı ilerlenir.

Bu, veritabanı dizinlerinin neredeyse tamamının B+ ağacı olmasının nedenidir: hem tekil arama hem aralık taraması aynı yapıyla verimli yapılır. Veritabanları müfredatındaki dizin tasarımı bu yapının üzerine kurulur.

Karşılaştırma

Ölçüt	Dengeli ikili ağaç	B / B+ ağacı
Düğüm boyutu	Küçük (birkaç bağ)	Blok boyutunda
Yükseklik ($10^6$ kayıt)	~20	~3
Uygun ortam	Bellek	Disk, ağ, blok tabanlı depolama
Aralık sorgusu	Ağaç gezinmesi	B+ ağacında yaprak zinciri
Düğüm içi arama	Yok	İkili arama veya doğrusal tarama

Son satır bir ayrıntıyı açığa çıkarır: B-ağacında toplam karşılaştırma sayısı, ikili ağaçtan az değildir. Anahtarlar düğüm içinde de aranır ve toplamda benzer sayıda karşılaştırma yapılır. Kazanılan şey karşılaştırma değil, blok okuma sayısıdır.

Bu, veri yapısı seçiminin donanım bağlamından ayrılamayacağını gösteren en net örnektir: aynı algoritma, farklı bir bellek hiyerarşisinde farklı bir yapıyı doğru kılar.

Düğüm İçi Arama

Düğüm başına yüzlerce anahtar bulunduğunda, düğüm içinde doğru çocuğu seçmek de bir arama problemine dönüşür. İki seçenek vardır ve seçim, önceki kursların gözlemleriyle belirlenir.

İkili arama, karşılaştırma sayısını logaritmik yapar. Doğrusal tarama daha çok karşılaştırma yapar ama anahtarları bitişik okur ve önbellek satırlarından tam olarak yararlanır.

Düğüm bir bloğa sığdığına ve blok zaten bellekte olduğuna göre, iki yöntem arasındaki fark küçüktür; gerçekleştirimler çoğu zaman ikisini birleştirir — küçük düğümlerde doğrusal, büyük düğümlerde ikili arama.

Bu ayrıntı, kursun tekrarlayan dersini bir kez daha gösterir: karşılaştırma sayısı tek başına bir ölçüt değildir; hangi belleğe kaç kez gidildiği de sayılmalıdır.

Yazma Yükü ve Dayanıklılık

Blok tabanlı depolamanın ikinci gerçeği, yazmanın okumadan pahalı olmasıdır. Bir düğümün tek bir anahtarı değişse bile, bloğun tamamı yeniden yazılır.

Bu, iki tasarım kararını doğurur. Düğümlerin yarıdan fazla dolu tutulması, bölünme ve birleştirme sıklığını azaltır. Yazmaların toplu yapılması ise aynı bloğa art arda gelen değişikliklerin tek bir yazmada birleşmesini sağlar.

Kalıcılık gereksinimi de buradan çıkar: bir bölünme sırasında sistem durursa yapı tutarsız kalabilir. Veritabanları bu riski, değişiklikleri önce bir günlüğe yazarak yönetir — Bilgisayarlar Nasıl Çalışır kursundaki yazma öncesi günlük fikrinin veri yapısı düzeyindeki karşılığıdır.

Kullanım Alanları

• Veritabanı dizinleri. Birincil ve ikincil dizinler B+ ağacı olarak tutulur.
• Dosya sistemleri. Dizin girdilerinin ve blok eşlemelerinin saklanması.
• Anahtar–değer depoları. Sıralı erişim gerektiren gerçekleştirimler.
• Dosya biçimleri. Büyük veri dosyalarına gömülü dizin blokları.

Bu yapıların ortak özelliği, bellek hiyerarşisinin hangi katmanına göre tasarlandıklarının açıkça bilinmesidir; aynı ağaç, farklı bir katman için farklı parametrelerle kurulur.

Yazma ağırlıklı iş yüklerinde alternatif bir aile — günlük yapılı birleştirme ağaçları — tercih edilebilir: yazmaları toplu hâle getirip sıralı diske yazarlar. İki ailenin karşılaştırması veritabanları müfredatının konusudur.

Özet

• Kalıcı depolama blok düzeyinde okunur; maliyeti belirleyen, okunan blok sayısıdır.
• B-ağacında düğüm boyutu bloğa eşitlenir; dallanma çarpanı yüzler mertebesine çıkar.
• Yükseklik $\log_b n$ ile orantılıdır; bir milyon kayıt için üç düğüm ziyareti yeterlidir.
• Kurallar 2-3 ağacının genelleştirilmiş hâlidir: bölünme, terfi, ödünç alma ve birleştirme.
• B+ ağacında kayıtlar yalnızca yapraklarda tutulur ve yapraklar zincirlenir; aralık sorguları sıralı taramaya iner.
• Kazanç karşılaştırma sayısında değil, blok okuma sayısındadır.

Sonraki Adım

Buraya kadarki ağaçlar sıralamayı tam olarak korudu. Bazı problemlerde ise yalnızca en küçük (veya en büyük) elemana hızlı erişim gerekir; tam sıralama gereksiz bir maliyettir. Sonraki ders, bu gevşetilmiş koşulla çalışan yığın yapısını ve onun gerçeklediği öncelik kuyruğunu ele alacak.