
B+ Tree Düğüm Yapısı, Sayfa Bölünmesi ve Rastgele G/Ç Analizi
Veritabanlarında B+ Tree indeks yapısı, yaprak düğüm bölünmesi (page split), rastgele disk G/Ç darboğazı ve kilit çekişmesi optimizasyon rehberi.
İlişkisel veritabanı motorlarında B+ Tree veri yapısı yarım asırdır birincil indeksleme standardı olarak kullanılır. PostgreSQL nbtree modülü, MySQL InnoDB depolama motoru ve SQLite btree katmanı verileri sıralı tutmak için bu ağaç yapısına güvenir. Okuma performansı O(log N) seviyesinde öngörülebilir kalsa da yoğun rastgele yazma iş yüklerinde B+ Tree mimarisi ciddi bir disk ve bellek darboğazına dönüşür. Sayfa bölünmeleri (page split), kilit çekişmeleri ve parçalanmış disk sayfaları üretim sistemlerinde beklenmedik gecikme patlamalarına sebep olur.
Kapsam Notu: Bu mimari analiz PostgreSQL 16/17 nbtree uygulaması ile InnoDB B+ Tree depolama sayfaları temel alınarak hazırlanmıştır.
B+ Tree Düğüm Hiyerarşisi ve Sayfa Yerleşimi
B+ Tree mimarisinde tüm kullanıcı verileri veya satır işaretçileri (tuple pointers) yalnızca yaprak düğümlerde (leaf nodes) tutulur. Kök ve iç düğümler (internal nodes) yalnızca arama yönlendirmesi sağlayan anahtar ve sayfa adresi çiftlerini barındırır. Yaprak düğümler çift yönlü bağlı liste (doubly linked list) ile birbirine bağlanır. Bu yapı aralık taramalarını (range scan) doğrudan yaprak seviyesinde sıralı okuma operasyonuna dönüştürür.
+-----------------------+
| Kök Düğüm |
| [ 20 | 50 ] |
+---+-------+-------+---+
| | |
+------------+ | +------------+
v v v
+-------------------+ +-------------------+ +-------------------+
| İç Düğüm 1 | | İç Düğüm 2 | | İç Düğüm 3 |
| [ 5 | 12 ] | | [ 30 | 42 ] | | [ 65 | 80 ] |
+---+-------+---+---+ +---+-------+---+---+ +---+-------+---+---+
| | | | | | | | |
v v v v v v v v v
+=====+ +=====+ +=====+ +=====+ +=====+ +=====+
|Yaprak<->|Yaprak<------>|Yaprak<->|Yaprak<------>|Yaprak<->|Yaprak
| 1..4| | 5..11 |20..29 |30..41 |50..64 |65..79
+=====+ +=====+ +=====+ +=====+ +=====+ +=====+
Tipik bir veritabanı sayfasında (PostgreSQL için 8 KB, InnoDB için 16 KB) düğüm yerleşimi şu parçalardan oluşur:
- Sayfa başlığı: LSN (Log Sequence Number), boş alan sınırları ve bayraklar.
- Dizi işaretçileri: Sayfa içindeki slot dizisi.
- Serbest alan: Yeni eklenecek anahtarlar için ayrılan dinamik boşluk.
- Anahtar ve veri hücreleri: Sayfanın sonundan başına doğru büyüyen sıralı girişler.
Sayfa Bölünmesi (Page Split) Mekanizması
Bir yaprak sayfasına yeni bir kayıt eklenmek istendiğinde ve sayfadaki serbest alan yetersiz kaldığında veritabanı motoru mecburen bir sayfa bölünmesi yürütür. Bu işlem klasik B+ Tree algoritmasında şu adımlarla gerçekleşir:
- Bellekte (Buffer Pool) yeni bir boş sayfa tahsis edilir.
- Dolu olan sayfadaki anahtarların yaklaşık yarısı (%50) yeni sayfaya taşınır.
- Yeni sayfanın en küçük anahtarı bir üstteki iç düğüme (internal node) yeni bir indeks girişi olarak eklenir.
- Yaprak seviyesindeki çift yönlü işaretçiler güncellenir. Sol sayfa yeni sayfayı, yeni sayfa sağ komşuyu gösterecek şekilde bağlanır.
Dolu Sayfa (8 KB):
[ K1 | K2 | K3 | K4 | K5 | K6 | K7 | K8 ] -> YENİ KAYIT: K5.5 SIĞMIYOR
Sayfa Bölünmesi Sonrası:
Eski Sayfa (Sol): Yeni Sayfa (Sağ):
[ K1 | K2 | K3 | K4 ] [ K5 | K5.5 | K6 | K7 | K8 ]
(Kalan Alan: %50 Boş) (Kalan Alan: %40 Boş)
Eğer üstteki iç düğüm de doluysa bölünme yukarıya doğru kaskat biçimde (cascading split) tırmanır. En uç noktada kök düğümün bölünmesi gerekir. Kök bölündüğünde ağacın derinliği bir basamak artar. Bu durum tüm okuma yollarına ilave bir sayfa erişim maliyeti ekler.
Rastgele G/Ç Darboğazı: UUIDv4 Felaketi
Monotonik artan bir birincil anahtar (örneğin BIGSERIAL veya TSID) kullanıldığında yeni kayıtlar daima ağacın en sağındaki yaprak sayfasına eklenir. Bu senaryoda motor 50/50 bölünme yerine optimize edilmiş sağa yaslı (right-leaning) ekleme yapar. Sayfa %99 dolulukla diske yazılır ve bölünme yalnızca en uçta gerçekleşir.
Rastgele anahtar (örneğin standart UUIDv4) seçildiğinde ise her yeni ekleme ağacın rastgele bir yaprak sayfasına düşer. Bu durum iki yıkıcı probleme yol açar:
- Buffer Pool tahribatı: Ağacın tüm yaprak sayfaları eşit olasılıkla hedef alınır. Veritabanının aktif çalıştığı indeks boyutu RAM miktarını aştığı anda her yazma işlemi diskten rastgele bir blok okumak (cache miss) ve kirli bir bloğu diske boşaltmak zorunda kalır. Rastgele disk erişimi (Random I/O) NVMe sürücülerde dahi G/Ç kuyruklarını tıkar.
- Düşük sayfa doluluğu ve parçalanma: Sürekli 50/50 bölünmeler sonucunda sayfaların ortalama doluluk oranı %67 seviyesine geriler. Ağaç disk üzerinde olması gerekenin neredeyse 1.5 katı yer kaplar. Bellekteki değerli tampon alanı boşluklarla israf edilir.
Latch Crabbing ve Kilit Çekişmesi
Sayfa bölünmesi yalnızca disk G/Ç maliyeti yaratmaz, bellek seviyesinde eşzamanlılığı da kilitler. Bir sorgu B+ Tree üzerinde arama yaparken düğümlere paylaşımlı kilit (Shared Latch) koyarak yapraklara doğru ilerler. Buna Latch Crabbing denir.
Bir yazma işlemi bölünme riski taşıdığında ilgili yolu korumak için münhasır kilit (Exclusive Latch) talep eder. Bölünme üst düğümlere tırmandıkça iç düğümler ve kök sayfa dahi Exclusive modda kilitlenebilir. Bu kilitlenme anında ağacın o alt dalına veya köke erişmek isteyen tüm okuma ve yazma iş parçacıkları beklemeye geçer. Yüksek işlem hacimli ortamlarda kilit çekişmesi CPU çekirdeklerinin işletim sistemi düzeyinde futex uyku döngülerine girmesine yol açar.
Üretim Sistemlerinde Önleme Yöntemleri
Yoğun yazma alan tablolarda B+ Tree parçalanmasını ve bölünme krizlerini hafifletmek için uygulanan temel stratejiler şunlardır:
- Sıralı Anahtar Seçimi: Tamamen rastgele UUIDv4 yerine zaman damgası önekli UUIDv7 veya ULID kullanılmalıdır. Bu sayede yazmalar daima sağ yaprağa toplanır ve aradaki sayfaların parçalanması engellenir.
- Doldurma Faktörü (fillfactor) Ayarı: Düzenli UPDATE alan indekslerde sayfada önceden boşluk bırakmak bölünmeleri geciktirir.
ALTER TABLE odemeler SET (fillfactor = 85)
REINDEX TABLE odemeler
- Çevrimiçi Yeniden İndeksleme: Parçalanmış ve doluluk oranı düşmüş indeksler arka planda kilit tutmadan yeniden inşa edilmelidir:
REINDEX INDEX CONCURRENTLY idx_odemeler_hesap_id
Doğru anahtar sıralaması ve kontrollü sayfa doluluğu seçildiğinde B+ Tree sayfaları disk bloklarıyla uyumlu çalışır ve G/Ç gecikmeleri dengede kalır.
Yazıyı Değerlendir
0 tepkiFikirlerinizi tek tıkla paylaşarak geri bildirim bırakın.
Ali Purtaş
@alipurtas • Hey, This is Ali!
Kendi halinde yazılım geliştiren bir öğrenci. Sistemler kuruyor, deniyor, bozuyor ve öğrendiği gerçek çözümleri burada belgeliyor.
Konu Kümesi & Önerilen Yazılar
Redis Pub/Sub ile L1/L2 Çok Katmanlı Önbellek Geçersizleştirme Ağı
Süreç içi yerel RAM (L1) ile merkezi Redis (L2) katmanlarını senkron tutan Pub/Sub tabanlı geçersizleştirme ve istemci önbellekleme mimarisi.
Önbellek İzdihamı ve XFetch Probabilistik Erken Yenileme Algoritması
Önbellek izdihamı (cache stampede) krizlerini önleyen XFetch olasılıksal erken yenileme algoritması ve tekil uçuş (singleflight) desen analizi.
Write-Behind Önbellekleme ve Veritabanı Toplu Yazma Yükü Mimarisi
Write-behind önbellekleme ile yazma gecikmesini düşürme, toplu veritabanı yazımları, veri kaybı riskleri ve çöküş kurtarma mimari rehberi.
Tartışma & Yorumlar
0Tartışmaya katılmak ve soru sormak için oturum açmalısınız.
Giriş Yap