B-Tree, B+Tree ve LSM-Tree İndeks Felsefesi: Veritabanı Bellek & Disk Mimarisi

▸1. Temel Sorun: Diskin Mekaniği ve Bellek Hiyerarşisi

Veritabanı indekslemesi tek bir fiziksel kurala dayanır: Disk I/O yavaştır, RAM ise hızlıdır. Ancak modern NVMe SSD sürücülerde bile, rastgele (random) 4KB veya 8KB'lık blok erişimleri, ardışık (sequential) okumalara kıyasla CPU cache ve I/O kontrolcüsü üzerinde yüksek ek yük (overhead) oluşturur.

Bir veritabanı motorunun indeks felsefesi iki ana soruya yanıt arar:

1*Arama yaparken en az sayıda disk bloğu nasıl okunur?* (Read Amplification minimization)
2*Satır güncellenirken veya eklenirken indeks ne kadar disk yazma maliyeti üretir?* (Write Amplification minimization)

▸2. B-Tree vs B+Tree: PostgreSQL ve MySQL Yaklaşımı

Karşılaştırma Kriteri	PostgreSQL (B-Tree)	MySQL InnoDB (B+Tree)
Tablo Depolama Düzeni	Heap Table (Satırlar rastgele sayfalara yazılır)	Clustered Index (Tablo bizzat Primary Key B+Tree ağacıdır)
Primary Key Arama	B-Tree kökten yaprağa iner ➔ Heap Pointer (TID: page/offset) ile heap sayfasına gider (2 aşama)	B+Tree yaprak bloğu bizzat satırın tüm kolonlarını barındırır (1 aşama)
İkincil İndeks (Secondary Index)	Doğrudan Heap Tuple ID (TID) adresini işaret eder	Primary Key değerini saklar; önce PK bulunur, sonra ana ağaçta ikinci arama yapılır (Index Lookup)
Aralık (Range) Taraması	B-Tree yaprakları çift yönlü bağlıdır; TID listesi taranır	B+Tree yaprakları ardışık bağlıdır, clustered aralık okuması olağanüstü hızlıdır
HOT (Heap-Only Tuple) Optimizasyonu	Var: İndekslenmemiş kolon güncellemeleri indeks yaprağını kirletmez	Yok: Satır boyutu değiştiğinde veya bölünme anında PK ağacı etkilenir

▸3. PostgreSQL Heap Mimarisi ve HOT (Heap-Only Tuples)

PostgreSQL tabloları 'Heap' formatında saklar. Yani satırlar (tuples) diske boş bulunan herhangi bir 8KB'lık sayfaya yazılır. B-Tree indeksi ise yalnızca arama anahtarı (key) ve hedef satırın disk koordinatını (ctid: sayfa no + sayfa içi index) tutar.

[!NOTE] HOT (Heap-Only Tuple) Mucizesi: PostgreSQL'de bir satır UPDATE edildiğinde, eğer güncellenen kolon üzerinde bir indeks yoksa ve aynı sayfada yeterli boş yer varsa, yeni versiyon aynı sayfaya yazılır ve eski satır yenisine bir zincir (pointer) bırakır. İndeks ağacına tek bir yeni kayıt yazılmaz! Bu, write amplification'ı %80 oranında düşürür. Tablolarınızda fillfactor parametresini %80-90 bandına çekmek bu yüzden hayati önem taşır.

sql

-- PostgreSQL: Tablo fillfactor değerini HOT optimizasyonu için optimize etme
ALTER TABLE orders SET (fillfactor = 85);
VACUUM FULL orders; -- Alanı yeniden organize etmek için

▸4. MySQL InnoDB Clustered Index ve İkincil İndeks Bedeli

MySQL InnoDB motorunda tablo diye ayrı bir yapı yoktur; tablonun kendisi Primary Key üzerinde inşa edilmiş bir B+Tree ağacıdır (Clustered Index).

•Avantajı: SELECT * FROM users WHERE id = 1042; sorgusu tek bir ağaç inişiyle hem indeksi hem de satırın tüm verilerini tek seferde bulur. Ekstra bir heap disk okuması yapılmaz.
•Bedeli (Secondary Index Penalty): İkincil bir indeks (örneğin email indeksi) oluşturduğunuzda, yaprakta satırın disk adresi değil, Primary Key değeri saklanır. Bu nedenle ikincil indeks üzerinden yapılan her arama, önce ikincil ağaçta PK'yi bulur, ardından ana PK ağacında ikinci bir arama (Bookmark Lookup) yapar.

[!WARNING] Geniş Primary Key Tuzağı: MySQL'de UUID (36 karakter string) gibi geniş bir alanı Primary Key seçerseniz, tablodaki TÜM ikincil indekslerin yapraklarında bu 36 bayt tekrarlanır. 5 indeksli 10 milyonluk bir tabloda gigabaytlarca fazladan bellek ve disk I/O tüketilir. MySQL'de PK daima küçük ve artan bir tam sayı (BIGINT AUTO_INCREMENT) olmalıdır.

▸5. Özel İndeks Felsefeleri: BRIN ve GIN

PostgreSQL, klasik B-Tree'nin ötesinde modern veri hacimlerine uygun özel indeksleme motorları sunar:

1BRIN (Block Range Index): Zaman serisi, log ve sürekli artan created_at veya id kolonlarında milyonlarca satırı birkaç yüz kilobayt ile indeksler. Her 128 disk sayfası için yalnızca min/max değerini saklar. 100 GB'lık tablo için 5 MB indeks!
2GIN (Generalized Inverted Index): JSONB, metin arama ve dizi (array) alanları için her elemanın hangi satırlarda geçtiğini saklayan ters indeks modelidir.

▸6. DBA Altın Kuralları (Felsefe Özeti)

1Her İndeks Bir Yazma Cezasıdır: Her INSERT, UPDATE ve DELETE, tablodaki tüm ilgili indeks ağaçlarını güncellemek, kilit (latch) almak ve WAL/Redo log üretmek zorundadır. Kullanılmayan her indeks üretim veritabanına doğrudan CPU ve I/O yüküdür.
2Kapsayan İndeks (Covering Index / Index-Only Scan): Sorgunun ihtiyaç duyduğu kolonları indeksin yaprağına ekleyerek (INCLUDE veya bileşik indeks) ana tabloya/heap sayfasına hiç gitmeden sorguyu yanıtlayın.
3Kardinaliteye Saygı Duyun: Düşük çeşitliliğe sahip (örneğin sadece true/false veya aktif/pasif) kolonlara yalın B-Tree indeks koymak çoğunlukla sorgu planlayıcı tarafından reddedilir; bunun yerine kısmi indeks (Partial Index) kullanın.