B-Tree ve B+ Tree nedir? Ekleme, bölme (split), silme, birleştirme (merge) işlemleri, B+ Tree farkları ve veritabanı indeksleme mantığı — görsellerle anlatım.

Neden B-Tree? — Disk Erişim Problemi

Şimdiye kadar öğrendiğimiz ağaçlar (BST, AVL, RB) RAM'de çalışmak üzere tasarlanmıştır. Bir düğüme erişmek nanosaniyeler sürer. Ancak veritabanları ve dosya sistemleri verilerini diskte saklar — ve disk erişimi dramatik şekilde yavaştır.

Bir AVL ağacında 1 milyon anahtar varsa yükseklik ~20'dir. Her arama 20 düğüm erişimi gerektirir — RAM'de sorun olmaz ama diskte 20 ayrı disk okuması demektir. Çözüm: her düğüme çok sayıda anahtar koyarak ağacın yüksekliğini düşürmek. İşte B-Tree'nin temel fikri budur.

B-Tree Kuralları

B-Tree, minimum derece t (t ≥ 2) parametresiyle tanımlanan, kendiliğinden dengeli çok yollu arama ağacıdır. 1970'te Rudolf Bayer ve Edward McCreight tarafından geliştirilmiştir.

Sayısal Örnekler

Referans B-Tree (t = 3)

Düğüm Yapısı ve Arama

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define T  3   // minimum derece

typedef struct BTreeNode {
    int    keys[2*T - 1];       // anahtarlar (sıralı)
    struct BTreeNode* children[2*T]; // çocuk pointer'ları
    int    n;                    // mevcut anahtar sayısı
    bool   leaf;                 // yaprak mı?
} BTreeNode;

BTreeNode* yeniDugum(bool leaf) {
    BTreeNode* node = (BTreeNode*)calloc(1, sizeof(BTreeNode));
    node->leaf = leaf;
    return node;
}

BTreeNode* btreeAra(BTreeNode* node, int key) {
    if (!node) return NULL;
    int i = 0;
    while (i < node->n && key > node->keys[i]) i++;
    if (i < node->n && key == node->keys[i]) return node;
    if (node->leaf) return NULL;
    return btreeAra(node->children[i], key);
}

Ekleme ve Bölme (Insert & Split)

B-Tree'ye ekleme daima bir yaprak düğüme yapılır. Ekleme yapılacak yaprak doluysa (2t-1 anahtar), düğüm ekleme öncesinde bölünür (split). Bölme yukarıya propagate ederek köke kadar çıkabilir — kök bölünürse ağaç yukarıdan büyür.

Bölme (Split) İşlemi — Detay

t=3 olan bir düğümde max 5 anahtar vardır. Düğüm doluysa:

void splitChild(BTreeNode* parent, int i) {
    BTreeNode* y = parent->children[i]; // dolu çocuk
    BTreeNode* z = yeniDugum(y->leaf);  // yeni sağ yarı
    z->n = T - 1;

    // Sağ yarının anahtarlarını kopyala
    for (int j = 0; j < T - 1; j++)
        z->keys[j] = y->keys[j + T];
    // Çocukları da kopyala (iç düğümse)
    if (!y->leaf)
        for (int j = 0; j < T; j++)
            z->children[j] = y->children[j + T];
    y->n = T - 1;

    // Ebeveynde yer aç
    for (int j = parent->n; j > i; j--) {
        parent->children[j + 1] = parent->children[j];
        parent->keys[j] = parent->keys[j - 1];
    }
    parent->children[i + 1] = z;
    parent->keys[i] = y->keys[T - 1]; // medyan yukarı
    parent->n++;
}

Adım Adım — B-Tree Ekleme (t=3)

Ekleme sırası: 10, 20, 30, 40, 50, 25, 35, 5

void insertNonFull(BTreeNode* node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        // Yaprakta sıralı pozisyona ekle
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // Doğru çocuğu bul
        while (i >= 0 && key < node->keys[i]) i--;
        i++;
        // Çocuk doluysa önceden böl
        if (node->children[i]->n == 2*T - 1) {
            splitChild(node, i);
            if (key > node->keys[i]) i++;
        }
        insertNonFull(node->children[i], key);
    }
}

void btreeEkle(BTreeNode** root, int key) {
    BTreeNode* r = *root;
    if (r->n == 2*T - 1) {
        // Kök doluysa yeni kök oluştur ve böl
        BTreeNode* s = yeniDugum(false);
        s->children[0] = r;
        splitChild(s, 0);
        insertNonFull(s, key);
        *root = s;
    } else {
        insertNonFull(r, key);
    }
}

Silme ve Birleştirme (Delete & Merge)

B-Tree'den silme, eklemeden çok daha karmaşık bir operasyondur. Temel kısıt: silme sonrası hiçbir düğüm t-1'den az anahtar tutmamalıdır (kök hariç). Bu kısıtı korumak için ödünç alma (redistribution) ve birleştirme (merge) mekanizmaları devreye girer.

Eklemedeki proaktif bölme mantığına benzer şekilde, silmede de proaktif takviye (preemptive fix-up) uygulanır: kökten yaprağa inerken yolumuzun üzerindeki her düğümün en az t anahtarı olduğundan emin oluruz. Böylece yaprağa ulaştığında güvenle silebiliriz.

3 Temel Silme Durumu

Durum 2 Detay — Öncül ve Ardıl

İç düğümden silinen anahtar k_i için iki seçenek vardır:

Durum 3 Detay — Underflow Düzeltme Stratejileri

Silme yolundaki bir çocuk düğümde tam t-1 anahtar varsa, silme yapılırsa kural bozulur. İki düzeltme mekanizması vardır:

Adım Adım — Kapsamlı Silme Örneği

Başlangıç ağacı (t=3):

Ekleme ve Silme Kuralları — Özet Tablosu

B+ Tree — Veritabanlarının Gerçek Tercihi

B-Tree kavramsal olarak mükemmeldir, ancak gerçek dünya veritabanlarının büyük çoğunluğu (MySQL/InnoDB, PostgreSQL, SQLite, Oracle, SQL Server) B-Tree'nin bir varyantı olan B+ Tree kullanır. B+ Tree, B-Tree'nin disk I/O ve aralık sorgusu zayıflıklarını çözer.

B-Tree vs B+ Tree — 3 Kritik Fark

B+ Tree Yapısı — Görsel

B+ Tree'nin Avantajları — Neden Veritabanları Tercih Eder?

B-Tree vs B+ Tree — Detaylı Karşılaştırma

Aralık Sorgusu — B+ Tree vs B-Tree

B+ Tree Düğüm Yapısı

typedef struct BPlusNode {
    int    keys[2*T - 1];
    int    n;
    bool   leaf;

    union {
        struct BPlusNode* children[2*T]; // iç düğüm
        struct {
            void* values[2*T - 1];       // yaprak: veri pointer'ları
            struct BPlusNode* next;         // ★ sonraki yaprak
        };
    };
} BPlusNode;

/* B+ Tree aralık sorgusu (range scan) */
void rangeQuery(BPlusNode* root, int lo, int hi) {
    // 1) lo anahtarını içeren yaprağı bul
    BPlusNode* leaf = findLeaf(root, lo);

    // 2) Yapraklardan bağlı liste ile tara
    while (leaf) {
        for (int i = 0; i < leaf->n; i++) {
            if (leaf->keys[i] >= lo && leaf->keys[i] <= hi)
                printf("%d ", leaf->keys[i]);
            if (leaf->keys[i] > hi) return;
        }
        leaf = leaf->next;  // ★ sonraki yaprağa geç
    }
}

Veritabanı İndeksleme Mantığı

Bir veritabanı tablosunda milyonlarca satır olduğunda, SELECT * FROM users WHERE id = 42 sorgusu index olmadan tüm tabloyu taramak zorundadır (full table scan — O(n)). İndeks, arama süresini O(n) → O(log n) düşüren bir veri yapısıdır. Ve bu indeksin arkasında B+ Tree vardır.

İndeks Olmadan vs İndeks İle

Clustered vs Non-Clustered (Secondary) İndeks

SQL İndeks Oluşturma Örnekleri

-- Clustered index (PRIMARY KEY ile otomatik)
CREATE TABLE users (
    id    INT PRIMARY KEY,   -- ← otomatik clustered B+ Tree
    name  VARCHAR(100),
    age   INT,
    email VARCHAR(255)
);

-- Secondary index (non-clustered)
CREATE INDEX idx_age ON users(age);

-- Composite (bileşik) index — çok sütunlu B+ Tree
CREATE INDEX idx_age_name ON users(age, name);
-- ↑ (age, name) sırasına göre B+ Tree oluşturur
-- WHERE age=25 → kullanır ✓
-- WHERE age=25 AND name='Ali' → kullanır ✓
-- WHERE name='Ali' → kullanMAZ ✗ (leftmost prefix kuralı)

-- EXPLAIN ile indeks kullanımını kontrol et
EXPLAIN SELECT * FROM users WHERE age BETWEEN 20 AND 30;
-- type: range, key: idx_age → B+ Tree range scan ✓

Veritabanlarında B+ Tree Kullanımı

Gerçek Dünya Disk Sayfası Hesabı

Karmaşıklık Analizi

B+ Tree vs Diğer Yapılar — Genel Karşılaştırma

Gerçek Dünya Kullanımları

Sonuç

B-Tree ve B+ Tree, disk tabanlı depolama için tasarlanmış kendiliğinden dengeli çok yollu ağaçlardır. Temel motivasyon: disk erişimi RAM'den 100.000+ kat yavaştır — ağaç yüksekliğini düşürerek disk I/O sayısını minimize etmek gerekir. Her düğüm bir disk sayfası (4-16 KB) kadar veri tutarak yüzlerce dallanma sağlar → milyarlarca kayıt sadece 3-4 seviyeye sığar.

B+ Tree, B-Tree'nin veritabanı optimize edilmiş versiyonudur. İç düğümler sadece yol gösterici anahtar tutar (daha fazla dallanma), tüm veri yapraklardadır ve yapraklar bağlı liste ile birbirine bağlıdır (aralık sorguları için sıralı I/O). Bu yüzden MySQL, PostgreSQL, Oracle, SQLite gibi tüm modern veritabanları B+ Tree kullanır.

İndeksleme, veritabanı performansının en kritik konusudur. Doğru sütunlara doğru index'ler koymak, sorgu süresini saniyelerden milisaniyelere düşürebilir. Ama gereksiz index'ler yazma performansını olumsuz etkiler (her INSERT/UPDATE'de B+ Tree güncellenmeli). Denge: okuma ağırlıklı sorgularda index çok faydalı, yazma ağırlıklı iş yüklerinde dikkatli olunmalı.