İndeksleme: dense/sparse indeks, B+ ağacı, hash ve seçim maliyeti

Şimdiye kadar SQL sorgusunu yazdık ve sonucun ne olacağını konuştuk. Bu hafta soru değişiyor: veritabanı o sonucu ne kadar sürede buluyor? Cevap diskteki düzene ve indekslere bağlı. Sınavda bu konudan üç tip soru gelir: maliyet hesabı (ms cinsinden), B+ ağacına ekleme yapıp son ağacı çizme ve “hangi plan daha ucuz?” karşılaştırması.

Altın kurallar:

1. Maliyetin birimi disk erişimi. CPU ihmal edilir. Bir blok okumak = transfer ($t_T$), başka bir yere atlamak = seek ($t_S$).
2. Seek, transferden çok pahalı. Bu sayfada hep $t_S = 4$ ms, $t_T = 0.1$ ms kullanacağız.
3. İndeks her zaman kazandırmaz. Çok kayıt eşleşiyorsa ikincil indeks, düz taramadan yavaş olabilir.
4. B+ ağacında yaprak bölünürken anahtar yukarı kopyalanır, iç düğüm bölünürken yukarı taşınır.

Depolama: blok, kayıt, dosya

Disk, veriyi sabit boyutlu bloklar (block) halinde okur ve yazar. Bir kayıt (record) tek başına okunmaz; içinde bulunduğu blok komple belleğe gelir. Bu yüzden önemli sayılar şunlardır:

$f_r = \left\lfloor \frac{\text{blok boyutu}}{\text{kayıt boyutu}} \right\rfloor \qquad b_r = \left\lceil \frac{n_r}{f_r} \right\rceil$

Örnek: blok 4096 bayt, kayıt 200 bayt. $f_r = \lfloor 20.48 \rfloor = 20$. 10000 kayıt varsa $b_r = 500$ blok.

Dosya düzenleri:

• Heap file: kayıtlar boş yer neredeyse oraya yazılır, sıra yok. Ekleme ucuz, arama pahalı.
• Sequential (sorted) file: kayıtlar bir arama anahtarına (search key) göre sıralı. İkili arama ve aralık sorguları mümkün, ama ekleme sırayı korumak için taşma bloklarına ihtiyaç duyar.

İndeks kavramları

İndeks (index), kitabın arkasındaki dizin gibidir: “anahtar değeri → kaydın yeri” çiftleri tutar. İndeksi kurduğumuz öznitelik(ler)e arama anahtarı (search key) denir. Dikkat: arama anahtarı, tablonun birincil anahtarı olmak zorunda değil.

Sparse indekste stu_id = 'S4471' arıyorsan, indekste S4471’den küçük ya da ona eşit en büyük girdiyi bulursun, o bloğa gidip sırayla ilerlersin. Bu sadece dosya sıralıysa çalışır. Secondary indeks sparse olamaz, çünkü kayıtlar dağınıktır ve “bu bloktan sonra devam et” diyemezsin.

Sayılarla: 10000 kayıt, 500 blok, bir indeks bloğuna 100 girdi sığıyor. Dense indeks 10000 girdi, yani 100 blok. Sparse indeks 500 girdi, yani 5 blok. Sparse daha küçük, dense ise bazı sorguları veriye hiç gitmeden cevaplar (örneğin “bu anahtar var mı?”).

Çok seviyeli indeks

İndeks büyüyünce kendisi de diskte aranacak bir dosya olur. Çözüm: indeksin üstüne sparse bir indeks daha kur, en üst seviye tek bloğa sığana kadar devam et. Buna çok seviyeli indeks (multilevel index) denir. Her seviyeden bir blok okunur, sonra veri bloğu. B+ ağacı bu fikrin dengeli ve güncellenebilir halidir.

B+ ağacı

B+ ağacı (B+ tree) veritabanlarının varsayılan indeksidir. Parametresi $n$: bir düğümdeki en fazla işaretçi sayısı. Bir düğüm en fazla $n - 1$ anahtar tutar.

Özellikler:

• Bütün yapraklar aynı derinlikte. Ağaç her zaman dengeli.
• Gerçek kayıt işaretçileri sadece yapraklarda. İç düğümlerdeki anahtarlar sadece yol gösterir.
• Yapraklar soldan sağa zincirli (son işaretçi bir sonraki yaprağı gösterir). Aralık sorgusunda ilk yaprağı bulup zincir boyunca yürürsün.

Yükseklik sınırı, $K$ farklı anahtar için:

$h \le \left\lceil \log_{\lceil n/2 \rceil} K \right\rceil$

Gerçek sayılar: 4 KB blok, 32 baytlık anahtar, 8 baytlık işaretçi. $(n-1)\cdot 32 + n \cdot 8 \le 4096$ eşitsizliğinden $n = 103$ çıkar. Kabaca $n = 100$ alırsak, bir milyon anahtar için $h \le \lceil \log_{50} 10^6 \rceil = \lceil 3.53 \rceil = 4$. Bir milyon kayıt içinde arama en fazla 4 düğüm okur. İkili aramada bu sayı 20 civarındadır.

Arama: kökten başla. Düğümde aranan değerden büyük ilk anahtarın solundaki işaretçiyi izle; eşit ya da büyükse sağa geç. Yaprağa gelince anahtarı orada ara.

Ekleme ve bölünme (adım adım)

$n = 4$ (en fazla 3 anahtar). Taşan yaprakta ilk $\lceil n/2 \rceil = 2$ anahtar solda kalır, gerisi yeni yaprağa gider, yeni yaprağın ilk anahtarı ebeveyne kopyalanır. Taşan iç düğümde ilk $\lceil (n+1)/2 \rceil = 3$ işaretçi solda kalır, aradaki anahtar ebeveyne taşınır (alt düğümde kalmaz).

Sırayla 10, 20, 30, 40, 50, 25, 35, 5, 45, 55 ekleyelim. Seviyeler / ile ayrıldı, en sağdaki yapraklar:

ekle 10 -> [10]
ekle 20 -> [10 20]
ekle 30 -> [10 20 30]
ekle 40 -> [30] / [10 20] [30 40]                    yaprak taştı, 30 kopyalandı
ekle 50 -> [30] / [10 20] [30 40 50]
ekle 25 -> [30] / [10 20 25] [30 40 50]
ekle 35 -> [30 40] / [10 20 25] [30 35] [40 50]       sağ yaprak bölündü, 40 yukarı
ekle 5  -> [20 30 40] / [5 10] [20 25] [30 35] [40 50]
ekle 45 -> [20 30 40] / [5 10] [20 25] [30 35] [40 45 50]
ekle 55 -> [40] / [20 30] [50] / [5 10] [20 25] [30 35] [40 45] [50 55]

Son adımı aç: [40 45 50 55] taşar, [40 45] ve [50 55] olur, 50 köke gider. Kök [20 30 40 50] olur, 5 çocuk, $n = 4$ sınırını aşar. İç düğüm bölünür: solda 3 işaretçi ([20 30]), 40 yeni köke taşınır, sağda [50]. Ağaç bir seviye uzadı. B+ ağacı aşağı doğru değil, yukarı doğru büyür. Bu yüzden yapraklar hep aynı derinlikte kalır.

TUZAK · 40 nerede? Son ağaçta 40 hem kökte hem yaprakta [40 45] var. Bu doğru: yaprak bölünmesinde kopyalanan değer yaprakta da durur. Ama iç düğüm bölünmesinde yukarı çıkan 40, ikinci seviyede tekrar yazılmaz. [20 30 40] / [50] yazan puan kaybeder.

Silme (kısaca)

Silmede yaprak minimum doluluğun altına düşerse önce kardeşten ödünç alınır (redistribution), olmuyorsa kardeşle birleştirilir (merge/coalesce) ve ebeveynden bir anahtar silinir. Birleşme köke kadar yayılabilir; kökün tek çocuğu kalırsa kök silinir ve ağaç bir seviye kısalır.

Hash ile indeksleme

Statik hash (static hashing): $m$ kova (bucket) ve bir hash fonksiyonu $h$. Kayıt $h(k)$ numaralı kovaya yazılır. Eşitlik araması tek kova okur; aralık sorgusu için hash işe yaramaz çünkü komşu değerler dağılır.

$h(k) = k \bmod 4$ ile 12, 7, 21, 30, 16, 9, 43:

Kova dolarsa taşma bloğu (overflow bucket) zincirlenir. Zincir uzadıkça arama yavaşlar. Veri büyüdükçe $m$ sabit kaldığı için statik hash bozulur.

Extendable hashing bu sorunu çözer: hash değerinin ilk $i$ bitine bakan bir dizin (directory) tutar. Bir kova taşınca sadece o kova ikiye bölünür; gerekirse dizin boyutu ikiye katlanır ($i$ bir artar). Bütün dosyayı yeniden hash’lemek gerekmez.

Seçim (selection) maliyetleri

$\sigma_{A = v}(r)$ ya da $\sigma_{A \ge v}(r)$ için kullanılan yöntemler. Kitabın baskısına göre A1, A2 numaraları değişir; sınavda yöntemin adını ve formülünü bilmen yeter. $h_i$: B+ ağacının yüksekliği. Örneklerde $b_r = 500$, $h_i = 3$.

Mantık hep aynı: indeks ağacında her seviye rastgele bir okuma (seek + transfer). Birincil indekste veri sıralı olduğu için eşleşen kayıtlar ardışık bloklarda: bir seek, sonra $b$ transfer. İkincil indekste her eşleşen kayıt başka bir yerde olabilir, her biri ayrı seek ister.

TUZAK · ikincil indeks + çok eşleşme. 40 eşleşme ile ikincil indeks 176.3 ms, düz tarama 54 ms. Eşleşen kayıt sayısı arttıkça ikincil indeks hızla pahalanır. “İndeks varsa her zaman indeks kullanılır” cevabı yanlış.

Gerçek bir sistemde bunu görmek için örnek veritabanımızda (takes tablosu) SQLite’ın planına bakalım:

EXPLAIN QUERY PLAN SELECT * FROM takes WHERE course_id = 'MA101';
CREATE INDEX idx_takes_course ON takes(course_id);
EXPLAIN QUERY PLAN SELECT * FROM takes WHERE course_id = 'MA101';

SCAN takes
SEARCH takes USING INDEX idx_takes_course (course_id=?)

İndeks yokken tablo baştan sona taranıyor (SCAN). İndeksten sonra B+ ağacında arama yapılıyor (SEARCH). Sonuç iki durumda da aynı üç satır: S1, S3, S4. İndeks sonucu değil, yolu değiştirir.

Sık yapılan hatalar