İndeksleme ve Erişim Yöntemleri
İndeksler ve erişim yöntemleri, bir veritabanının tüm bir tabloyu taramadan eşleşen demetleri (tuple) bulmasını sağlayan ve optimize edicinin güvendiği hızlı erişim yollarını sunan, başlıca B+-ağaçları ve hash indeksleri olmak üzere yardımcı veri yapılarıdır.
Tanım
Bir indeks, bir ilişkinin bir veya daha fazla özniteliği üzerinde anahtar değerlerini eşleşen demetlerin konumlarına eşleyen, tablo boyutuna göre alt doğrusal (sublinear) sürede veri alımını mümkün kılan yardımcı bir veri yapısıdır; bir erişim yöntemi ise, bir sorgunun veriyi okumak için kullandığı, tam tarama veya indeks taraması gibi bir mekanizmadır.
Kapsam
Bu konu, veri erişim yollarının arkasındaki yapıları ve kavramları kapsamaktadır: kümelenmiş (clustered) ve kümelenmemiş (unclustered), birincil ve ikincil indeksler arasındaki ayrım; eşitlik ve aralık aramayı destekleyen temel sıralı indeks olarak B+-ağacı; eşitlik araması için hash tabanlı indeksler; ve indekslerin seçim, birleştirme (join) ve sıralama önlemedeki rolü. İndeks seçiminin sorgu maliyetini ve güncelleme yükünü nasıl etkilediği ele alınmaktadır. Maliyet tabanlı optimize edicinin genel plan seçimi, ayrı bir konu olduğundan bu kapsamın dışındadır.
Temel sorular
- Bir B+-ağacı hem eşitlik hem de aralık sorgularını nasıl verimli bir şekilde desteklemektedir?
- Kümelenmiş (clustered) ve kümelenmemiş (unclustered), birincil ve ikincil indeksler arasındaki fark nedir?
- Bir hash indeksi, bir ağaç indeksine ne zaman tercih edilmektedir?
- İndeksler seçimleri, birleştirmeleri (join) ve sıralı veri alımını nasıl hızlandırmaktadır?
- Ekleme, güncelleme ve silme işlemleri altında indeksleri sürdürmenin maliyeti nedir?
Anahtar kavramlar
- B+-ağacı indeksi
- hash indeksi
- kümelenmiş (clustered) ve kümelenmemiş (unclustered) indeks
- birincil ve ikincil indeksler
- yoğun (dense) ve seyrek (sparse) indeksler
- aralık ve eşitlik araması
- genişletilebilir (extendible) ve doğrusal (linear) hashing
- indeks bakım maliyeti
Temel kuramlar
- B+-ağacı indeksleri
- B+-ağacı, anahtarları sıralı düzende ve tüm veri referanslarını yapraklarda (leaves) saklayan, dengeli, yüksek dallanma faktörlü (high-fanout) bir arama ağacıdır; logaritmik G/Ç (I/O) ile eşitlik ve aralık sorgularını ve sıralı taramaları desteklemekte ve ekleme ile silme işlemleri altında dengeli kalmaktadır.
- Kümelenmiş (clustered) ve kümelenmemiş (unclustered) indeksler
- Kümelenmiş bir indeks, tablonun satırlarını indeks anahtarına göre fiziksel olarak sıralı tutmaktadır, bu da aralık taramalarını çok verimli hale getirmektedir; oysa kümelenmemiş (ikincil) bir indeks, sıralanmamış bir dosyaya işaret etmektedir, bu nedenle birçok eşleşen satırı almak, satır başına bir G/Ç (I/O) maliyetine neden olabilmektedir.
- Hash indeksleri
- Hash tabanlı indeksler, anahtarları beklenen sabit zamanlı eşitlik aramaları için kovalara (buckets) eşlemektedir ancak aralık sorgularını desteklememektedir; genişletilebilir (extendible) ve doğrusal (linear) hashing gibi dinamik şemalar, verilerle birlikte sorunsuz bir şekilde büyümelerini sağlamaktadır.
Klinik önem
İndeksleme, veritabanı performansı için en yaygın pratik kaldıraçtır: doğru indeksleri seçmek, tam tablo taramalarını işlem (transactional) ve analitik sorgular için milisaniyelik aramalara dönüştürebilmektedir; aşırı indeksleme ise güncellemeleri yavaşlatmaktadır, bu nedenle indeks tasarımı, gerçek sistemlerin işletilmesinde tekrarlayan bir karardır.
Tarihçe
Bayer ve McCreight, 1972'de disk üzerinde büyük sıralı indeksleri sürdürmek için B-ağacını tanıtmışlardır; tüm veriyi yapraklarda (leaves) tutan B+-ağacı varyantı, Comer'ın 1979 tarihli 'Ubiquitous B-tree' adlı çalışmasında incelendiği gibi standart veritabanı indeksi haline gelmiştir. Hash tabanlı erişim yöntemleri ve dinamik hash şemaları paralel olarak gelişmiş ve her iki aile de her ilişkisel motorun çekirdeğini oluşturmaya devam etmektedir.
Öne çıkan isimler
- Rudolf Bayer
- Edward McCreight
- Douglas Comer
İlgili konular
Temel eserler
- bayer1972
- comer1979
- ramakrishnan2003
Sıkça sorulan sorular
- Veritabanlarında ikili arama ağaçları yerine neden B+-ağaçları kullanılmaktadır?
- Veritabanları veriyi diskte saklamaktadır ve maliyet, sayfa okuma sayısıyla belirlenmektedir. B+-ağaçları yüksek dallanma faktörüne sahiptir, bu nedenle her düğüm bir disk sayfasını doldurur ve ağaç çok sığdır, herhangi bir kayda ulaşmak için yalnızca birkaç G/Ç (I/O) gerektirmektedir. İkili bir ağaç çok daha derin olacak ve çok daha fazla disk erişimine neden olacaktır.
- Bir B+-ağacı yerine ne zaman bir hash indeksi kullanmalıyım?
- Yalnızca eşitlik aramalarına (örneğin, belirli bir kimliğe sahip satırı bulma) ihtiyacınız olduğunda ve beklenen sabit zamanlı erişim istediğinizde bir hash indeksi kullanınız. Aralık sorgularına, sıralı taramalara veya önek eşleştirmeye de ihtiyacınız olduğunda bir B+-ağacı kullanınız, çünkü hash indeksleri anahtar sırasını korumaz ve aralık koşullarını verimli bir şekilde yanıtlayamaz.