SQL İndeksleme: B-Tree, Trade-off

Bu makale, indeksin ne olduğundan başlayıp, veritabanlarının altında yatan B-Tree / B+Tree veri yapılarına ve okuma–yazma trade-off’una kadar uzanır. .NET / SQL Server bağlamında örnekler verir ama mantık tüm RDBMS’lerde (PostgreSQL, MySQL, Oracle) aynıdır.

1. İndeks Nedir?

Bir kitabın sonundaki dizin (index) sayfasını düşün. “B-Tree” kelimesinin hangi sayfalarda geçtiğini bulmak için kitabı baştan sona okumazsın; dizine bakar, sayfa numarasını görür, doğru sayfaya gidersin.

Veritabanı indeksi de tam olarak budur: asıl veriden ayrı tutulan, sıralı ve hızlı arama yapılabilen bir yardımcı yapı. Amaç, “şu satırı bul” sorusunu tüm tabloyu taramadan cevaplamaktır.

Peki indeks olmadan veritabanı ne yapar? Full Table Scan yani tablodaki her satırı tek tek okur.

full table scan

10 milyon satırlık bir tabloda fark: 10.000.000 işlem yerine ~24 işlem (log₂(10M) ≈ 23.3). İşte indeksin tüm hikayesi bu tek satırda saklı.

2. Temel Trade-off: Okuma Hızlanır, Yazma Yavaşlar

Peki indeks bu kadar iyiyse neden her tabloda yok. Çünkü bir şey en iyi olsa herkes her yerde kullanır. Her şeyin hem artısı hem eksisi vardır.

Okuma (SELECT) işlemi çok hızlanır aranan veri log(n) sürede bulunur. Yazma (INSERT/UPDATE/DELETE) işlemi ise yavaşlar her yazmada indeks de güncellenir. Diskte ekstra yer kaplar, indeks ayrı bir yapıdır

Mantık şu: İndeks sıralı tutulur. Sıralı bir yapıya yeni eleman eklemek, onu doğru yere yerleştirmek + gerektiğinde yapıyı yeniden dengelemek demektir. Yani:

• 1 tablo + 3 non-clustered indeks = 4 yazma.
• Bu yüzden yazma-yoğun (write-heavy) tablolarda indeksi cömertçe dağıtmak performansı öldürür.

index write

Püf nokta: “İndeks bir trade-off’tur: okuma karmaşıklığını O(n)’den O(log n)’e indirir, karşılığında her yazma işlemine ek maliyet ve disk alanı getirir. Bu yüzden indeks ‘her sütuna eklenen’ değil, ‘erişim desenine göre seçilen’ bir araçtır.”

3. Neden B-Tree? Önce Yanlış Yapıları Eleyelim

İndeks “sıralı arama” istiyorsa, akla ilk gelen veri yapıları neden yetmiyor?

3.1. Sıralı Dizi (Sorted Array)

Arama hızlı (binary search, O(log n)), ama araya eleman eklemek tüm elemanları kaydırmayı gerektirir, ekleme O(n). Büyük veride elverişsiz.

3.2. Binary Search Tree (BST)

Dengeli olduğunda O(log n). Sorun: veri sıralı gelirse ağaç dejenere olur, bağlı listeye döner → O(n).

bst

Sıralı insert (10,20,30…) sonucu dejenere BST artık ağaç değil, liste.

3.3. Self-Balancing Tree (AVL, Red-Black)

Dengeyi korur, O(log n) garanti eder. Ama ikili (binary) ağaçtır: her düğümde 1 anahtar, 2 çocuk var. Bu, disk için kötü bir tasarımdır.

3.4. Asıl Mesele: Disk I/O

Veritabanı veriyi RAM’de değil diskte tutar ve diski page birimleriyle okur. Bir disk okuması, bir RAM okumasından ~100.000 kat yavaştır.

Binary ağaçta her düğüm = 1 disk okuması. 1 milyar satır için log₂(10⁹) ≈ 30 disk okuması.

B-Tree’de ise her düğüm yüzlerce anahtar tutar. Aynı 1 milyar satır log₂₅₆(10⁹) ≈ 3–4 disk okuması ile bulunur.

Püf nokta: B-Tree ikili ağaçtan daha “şişman ve kısadır”. Az sayıda ama dolu düğümle ağacın derinliğini (disk okuması sayısını) minimuma indirir. B-Tree, disk I/O’yu minimize etmek için tasarlanmış bir ağaçtır.

4. B-Tree Derinlemesine

Bir B-Tree (order = m) şu kurallara uyar:

• Her düğüm en fazla m-1 anahtar ve m çocuk tutar.
• Anahtarlar düğüm içinde sıralıdır.
• Tüm yapraklar aynı derinliktedir (dengeli).
• Bir düğümdeki anahtarlar, çocuk alt-ağaçları aralıklara böler.

b-treee

45 değerini aramak: Root'ta 30 < 45 < 60 → ortadaki çocuğa in → N2'de 45 arası 40 ile 50 → bulundu/yok. Sadece 2 düğüm okundu.

İnsert Sırasında Ne Olur? Node Split

Bir yaprak dolduğunda (m-1 anahtar) ve yeni anahtar gelince bölünme (split) olur: ortadaki anahtar üst düğüme “terfi eder”, yaprak ikiye ayrılır. Bu, ağacın hep dengeli kalmasını sağlar ama maliyetli kısımdır.

node split

İşte 2. bölümdeki “yazma yavaşlar” maliyetinin somut kaynağı: page split. Üst düğüm de doluysa o da bölünür, en kötü ihalede kök’e kadar gider.

5. B+Tree Gerçek Dünyada Kullanılan Yapı

SQL Server, MySQL, Oracle, PostgreSQL… hepsi aslında B+Tree kullanır. B-Tree’den iki kritik farkı vardır:

1. Veri sadece yapraklarda tutulur. İç düğümler yalnızca yönlendirme için anahtar tutar.
2. Yapraklar birbirine bağlı listeyle (linked list) zincirlenir.

b+tree link list version

Bu tasarım neden bu kadar güçlü?

• Range query: WHERE age BETWEEN 30 AND 60 → ilk yaprağı bul, sonra yaprakları next zincirinden yan yana oku. Ağaçta yukarı-aşağı gezinmek yok. ORDER BY, BETWEEN, >, <, LIKE 'abc%' hep bundan faydalanır.
• Daha yüksek fanout: İç düğümler veri taşımadığından daha çok anahtar sığar → ağaç daha da sığ olur.
• Tahmin edilebilir performans: Her arama tam olarak kök→yaprak yolu kadar sürer.

Püf nokta: “B-Tree mi B+Tree mi?” sorusuna çoğu kişi “B-Tree” der. Doğru cevap: “Gerçek veritabanları B+Tree kullanır; veriyi yapraklarda toplar ve yaprakları bağlı listeyle zincirleyerek aralık sorgularını ve sıralı taramayı çok verimli yapar.”

6. Clustered vs Non-Clustered Index

Clustered Index

Tablonun fiziksel sıralama düzenidir. Yani veri satırlarının kendisi B+Tree’nin yapraklarındadır. Bir tabloda yalnızca bir tane clustered olabilir (çünkü veri tek bir düzende fiziksel olarak duramaz). SQL Server’da Primary Key default olarak clustered’dır.

clustered index

Yapraklarda PK ile sıralı gerçek satırlar duruyor.

Non-Clustered Index

Ayrı bir B+Tree’dir; yapraklarında veri değil, aranan sütun + asıl satıra giden bir işaretçi (clustered key veya RID) tutar.

non-clustered index

Email’e göre non-clustered indeks. Yaprakta sadece PK işaretçisi var.

Key Lookup Problemi

SELECT * FROM Users WHERE Email='m@x' çalışırsa:

1. Non-clustered indekste m@x bulunur → PK:100.
2. Asıl satırın diğer sütunları için clustered indekse ikinci bir gidiş yapılır.

Bu ikinci adıma Key Lookup denir ve maliyetlidir. Çözüm ise covering index (bölüm 7).

7. Pratikte İndeks Türleri

Composite İndeks “Leftmost Prefix” Kuralı

Birden fazla sütundan oluşur: INDEX (LastName, FirstName). Sütun sırası kritiktir. İndeks tek bir sıralı yapıdır ve önce LastName'e, sadece eşit LastName içinde FirstName'e göre sıralanır. Yani FirstName global olarak sıralı değildir; her LastName grubunun içinde sıralıdır.

Telefon rehberi analojisi: Rehber önce soyada, sonra ada göre dizilir.

• “Soyadı Güzel olanlar” → “G” bölümüne atlarsın, hepsi yan yana. Kolay.
• “Soyadı Güzel, adı Onur” → Güzel’e atla, içinde Onur’a in. Kolay.
• “Adı Onur olan herkes (soyadı fark etmez)” → Onur Ak, Onur Güzel, Onur Yılmaz… rehberin her yerine dağılmış. Bulmak için tüm rehberi taramak gerekir.

İşte mesele bu: FirstName='Onur' araması seek yapamaz çünkü Onur değerleri indeks içinde bitişik bir aralıkta değil, dağınıktır atlanacak tek bir blok yoktur. Buna karşılık LastName='Güzel' araması bitişik bir bloğa denk gelir, doğrudan oraya atlanır.

Güzel’ler bitişik (seek edilebilir) ↔ Onur’lar üç ayrı yerde (seek edilemez, scan).

Bu indeks şunlarda çalışır (soldan başladığı için):

• WHERE LastName = 'Güzel'
• WHERE LastName = 'Güzel' AND FirstName = 'Onur'

Şunda çalışmaz (sol sütun LastName atlandığı için):

• WHERE FirstName = 'Onur'

Püf nokta: Bileşik indekste en seçici / en sık eşitlikle filtrelenen sütunu sola koy. Tek başına FirstName ile de sık arıyorsan, ayrı bir INDEX (FirstName) oluştur.

Covering Index (INCLUDE)

Sorgunun ihtiyaç duyduğu tüm sütunları indeksin içinde tutarak Key Lookup’ı tamamen ortadan kaldırır.

CREATE NONCLUSTERED INDEX IX_Users_Email
ON Users (Email)
INCLUDE (FirstName, LastName);  -- bunlar yaprağa eklenir, Key Lookup gerekmez

Unique Index

Hem performans hem de veri bütünlüğü sağlar (tekrar engellenir).

Filtered Index

Sadece bir alt küme için: WHERE IsActive = 1. Küçük, hızlı, az bakım maliyeti.

Hash Index vs B-Tree Index

Bu yüzden default indeks tipi B-Tree’dir: hem eşitliği hem aralığı kapsar. Hash sadece saf eşitlik senaryolarında tercih edilir.

8. Yazma Maliyetinin Anatomisi: Page Split, Fragmentasyon, Fill Factor

İndeksin “yazmayı yavaşlatması” tek bir olay değil, birkaç mekanizmanın toplamıdır:

• Page Split: Dolu bir sayfaya araya insert gelince sayfa ikiye bölünür (bölüm 4). CPU + I/O + log yükü demektir.
• Fragmentasyon: Bölünmeler sonucu sayfalar disk üzerinde fiziksel olarak dağınık kalır bu yüzden sıralı tarama yavaşlar.
• Fill Factor: Sayfaların baştan %100 değil de örneğin %80 dolu bırakılması. Boşluk, gelecekteki insert’lerin split yaratmadan yerleşmesini sağlar. Yazma-yoğun tablolarda ayarlanır.
• Index Maintenance: Zamanla REBUILD veya REORGANIZE gerekir.

GUID (uniqueidentifier) tuzağı: Rastgele GUID’i clustered key yapmak, insert’lerin ağacın her yerine dağılmasına ve sürekli page split’e yol açar. Çözüm: NEWSEQUENTIALID() veya sıralı bir kolon (bigint identity).

9. EF Core / .NET Tarafı

Kod tarafından indeks tanımı:

protected override void OnModelCreating(ModelBuilder modelBuilder)
{
    // Tekil, isimlendirilmiş indeks
    modelBuilder.Entity<User>()
        .HasIndex(u => u.Email)
        .IsUnique();

    // Bileşik indeks (sütun sırası önemli!)
    modelBuilder.Entity<User>()
        .HasIndex(u => new { u.LastName, u.FirstName });

    // Covering index (INCLUDE)
    modelBuilder.Entity<User>()
        .HasIndex(u => u.Email)
        .IncludeProperties(u => new { u.FirstName, u.LastName });

    // Filtered index
    modelBuilder.Entity<User>()
        .HasIndex(u => u.Email)
        .HasFilter("[IsActive] = 1");
}

Veya attribute ile:

[Index(nameof(Email), IsUnique = true)]
public class User { ... }

Performans yakalama: dbContext.Database.Log / SQL Server'da SET STATISTICS IO ON ve execution plan'da "Index Seek" mi "Index Scan / Table Scan" mı çıktığına bakılır. Plan'da sarı uyarı üçgeni genelde "missing index" veya Key Lookup işaretidir.

9.5. İndeksi Bozan Yazım Hataları

İndeks var ama sorgu yine de tüm tabloyu tarıyorsa, suçlu genelde indeks değil sorgunun yazımıdır. Bir predicate’in indeksle aranabilir olmasına sargable (Search ARGument ABLE) denir.

Püf nokta: Sütunu olduğu gibi bırak. Sütunun üstüne fonksiyon/aritmetik/dönüşüm uygularsan indeks ölür. İşlemi her zaman sabit (constant) tarafa taşı.

En Sık Karşılaşılan Anti-Pattern’ler

1. Sütun üzerinde fonksiyon

-- ❌ Scan
WHERE YEAR(OrderDate) = 2024
WHERE UPPER(Email) = 'A@X.COM'
WHERE CONVERT(date, CreatedAt) = '2024-01-01'

-- ✅ Seek
WHERE OrderDate >= '2024-01-01' AND OrderDate < '2025-01-01'
WHERE Email = 'a@x.com'

2. Sütun üzerinde aritmetik

-- ❌ Scan  (sütun aritmetik içinde)
WHERE Price * 1.2 > 100

-- ✅ Seek  (matematiksel olarak aynı, ama Price'a dokunulmadı)
WHERE Price > 100 / 1.2          -- 100/1.2 sabittir, bir kez hesaplanı

3. Leading wildcard LIKE

-- ❌ Scan  (prefix bilinmiyor)
WHERE Name LIKE '%onur%'
WHERE Name LIKE '%onur'

-- ✅ Seek  (prefix biliniyor)
WHERE Name LIKE 'onur%'

4. Implicit type conversion (sessiz katil)

-- ❌ Scan  — sütun nvarchar, parametre int → SQL tüm sütunu dönüştürür
WHERE PhoneNumber = 5551234        -- PhoneNumber nvarchar ise

-- ✅ Seek  — tipler eşleşir
WHERE PhoneNumber = '5551234'

EF Core’da string property'yi yanlış tiple karşılaştırmak veya varchar sütunu nvarchar parametreyle sorgulamak bu tuzağı tetikler. Execution plan'da CONVERT_IMPLICIT görürsen sebep budur.

5. Composite indekste leftmost prefix ihlali

-- INDEX (LastName, FirstName)
-- ❌ Scan  — soldaki sütun (LastName) atlanmış
WHERE FirstName = 'Onur'

-- ✅ Seek
WHERE LastName = 'Güzel'
WHERE LastName = 'Güzel' AND FirstName = 'Onur'

6. OR ile farklı sütunlar

-- ❌ Çoğu zaman scan çünkü tek indeks her iki koşulu karşılayamaz
WHERE Email = 'a@x.com' OR Phone = '555'

-- ✅ UNION ile her dal kendi indeksini kullanır
SELECT ... WHERE Email = 'a@x.com'
UNION
SELECT ... WHERE Phone = '555'

7. Olumsuzlama ve düşük seçicilik

-- ❌ Genelde scan  — "olmayanı" bulmak indeksle zor
WHERE Status != 'Active'
WHERE Status NOT IN ('A','B')
WHERE Deleted = 0           -- seçicilik düşükse (satırların %90'ı) yine scan

!=, NOT IN, NOT LIKE ve düşük cardinality'li koşullar optimizer'ı scan'e iter. Çözüm: filtered index veya sorguyu pozitife çevirmek.

8. NULL ve fonksiyon sarmalama

-- ❌ Scan
WHERE ISNULL(MiddleName, '') = ''
WHERE COALESCE(EndDate, GETDATE()) > '2024-01-01'

-- ✅ Seek
WHERE MiddleName IS NULL
WHERE (EndDate IS NULL OR EndDate > '2024-01-01')

Özet Tablo

Püf nokta: “İndeks var ama kullanılmıyorsa ilk bakacağın yer execution plan’da ‘Seek mi Scan mı’ ve predicate’in sargable olup olmadığıdır. En sık sebep, sütunun bir fonksiyonla sarmalanması veya implicit type conversion’dır.”

10. Ne Zaman İndeks Kullanmalı / Kullanmamalı?

İndeks ekleme sinyalleri: çok okunan, az yazılan tablo; yüksek seçicilikli sütun; sık JOIN/WHERE/ORDER BY.

İndeks ekleme sinyalleri: küçük tablolar (full scan zaten ucuz); yazma-yoğun tablolar; düşük seçicilikli sütunlar (cinsiyet, boolean); neredeyse hiç sorgulanmayan sütunlar.

11. Mülakat Q/A

İndeks nedir, neyi feda eder? Asıl veriden ayrı tutulan sıralı arama yapısı. Okuma karmaşıklığını O(n)’den O(log n)’e indirir; karşılığında her yazma işlemine ek maliyet ve disk alanı getirir.

Neden BST/AVL değil de B-Tree? Veritabanı diski page birimleriyle okur ve disk I/O pahalıdır. İkili ağaçta her düğüm 1 disk okumasıdır, ağaç derin olur. B-Tree yüksek fanout’la (her düğümde yüzlerce anahtar) ağacı sığlaştırır, disk okuma sayısını minimize eder.

B-Tree mi B+Tree mi kullanılır? Gerçek RDBMS’ler B+Tree kullanır. Veri yalnızca yapraklarda tutulur ve yapraklar bağlı listeyle zincirlenir; bu da aralık sorgularını ve sıralı taramayı çok verimli yapar.

Clustered ve non-clustered farkı? Clustered, tablonun fiziksel sıralamasıdır; veri satırları yapraklardadır, tabloda 1 tane olur. Non-clustered ayrı bir yapıdır; yaprağında veri yerine satıra giden işaretçi (clustered key/RID) tutar. Non-clustered’da Key Lookup ek maliyet yaratabilir.

Key Lookup nedir, nasıl önlenir? Non-clustered indeksin bulamadığı sütunlar için clustered indekse yapılan ikinci gidiş. Covering index (INCLUDE) ile önlenir.

Composite indekste sütun sırası neden önemli? İndeks soldan sağa sıralıdır (leftmost prefix). (A, B) indeksi WHERE A ve WHERE A AND B'de çalışır, ama WHERE B'de çalışmaz.

İndeks her zaman kullanılır mı? Hayır. Optimizer seçicilik düşükse veya tablo küçükse full scan’i tercih edilebilir. Ayrıca where koşulundaki karşılaştırmanın sol tarafında fonksiyon olması (WHERE YEAR(date)=2024) indeksi devre dışı bırakır (non-sargable).

Hash index eşitlikte daha hızlıyken neden default B-Tree? Hash sadece eşitlik (=) için iyidir; sırayı korumadığından aralık sorgularını (BETWEEN, >, ORDER BY, LIKE 'a%') hiç hızlandıramaz, full scan'e döner. B-Tree hem eşitliği hem aralığı/sıralı taramayı karşıladığı için genel amaçlı default'tur.

İndeks var ama sorgu yavaş / scan yapıyor. Neden? Genelde predicate sargable değildir: sütun bir fonksiyonla (YEAR(), UPPER()) ya da aritmetikle sarmalanmış, LIKE '%..' leading wildcard kullanılmış veya implicit type conversion (CONVERT_IMPLICIT) olabilir. Ek sebepler: composite indekste leftmost prefix ihlali, OR/!=/NOT IN, veya seçicilik o kadar düşük ki optimizer scan'i daha ucuz buluyor. İlk adım execution plan'da Seek/Scan ve predicate'e bakmaktır.

Çok fazla indeks neden kötü? Her INSERT/UPDATE/DELETE tüm ilgili indeksleri de günceller böylece yazma yavaşlar, disk ve bakım maliyeti artar, page split olasılığı yükselir.

Rastgele GUID’i clustered key yapmak neden sorun? Insert’ler ağacın her yerine dağılır, sürekli page split ve fragmentasyon olur. Sıralı anahtar (bigint identity, NEWSEQUENTIALID()) tercih edilir.

Kapanış: “İndeks bir performans aracı değil, bir mühendislik trade-off’udur. Doğru sorusu ‘indeks ekleyeyim mi?’ değil, ‘bu erişim deseni için okuma kazancı, getireceği yazma maliyetine değer mi?’dir.”