Veritabanı indeksleme nasıl çalışır?

Neden ihtiyaç duyulur?

Veriler disk tabanlı belleklere depolandığında, bloklar halinde depolanır. Bu bloklara bütünlük içinde erişilmesi, onları atomik disk erişim operasyonları yapar. Disk blokları genelde bağlı listeler gibi yapılandırılmıştır; her ikisi de verinin tutulduğu kısım ve bir sonraki düğüme gösteren pointer kısmından oluşur ve her ikiside ardarda depolanmak zorunda değildir.

Sıralama yapılmamış bir alanda arama yapmak Lineer Arama yapmayı gerektirir, bu da N/2 blok erişimi gerektirir. Buradaki N tablonun disk üzerinde bulunduğu blok sayısıdır. Eğer bu alan key yani anahtar olmayan bir alan ise arama N tane blok erişimi gerektirir.

Halbuki sıralanmış bir alan olsaydı Binary Arama kullanılabilir, bu da log2 N blok erişimi gerektirir. Bununla birlikte key olmayan alan sıralanmış ise tablonun geri kalanı duplicate değerleri bulmak için aranmaz. Çünkü alan sıralanmış olduğu için aranandan değişik bir değere erişildiğinde arama bitmiş demektir. Böylece performans önemli ölçüde artar.

İndeksleme nedir?

İndeksleme belirli sayıdaki kaydın birden fazla alanda sıralanması demektir. Bir tablodaki bir alanda indeks oluşturunca, alanın değerini ve bu değerin ilişkili olduğu kaydı işaret eden bir pointer tutan diğer bir veri yapısı oluşturur. Daha sonra bu indeks yapısı üzerinde Binary Arama yapılabilmesi için sıralanır.

İndekslemenin dezavantajı disk üzerinde ekstradan alana ihtiyaç duymasıdır.

Nasıl Çalışır?

Öncelikle örnek bir veritabanı tablo şemasının ana hatlarını çizelim;

Alan adı           Veri tipi      Disk üzerinde kapladığı alan
id (Primary key)   Unsigned INT   4 byte
firstName          Char(50)       50 byte
lastName           Char(50)       50 byte
emailAddress       Char(100)      100 byte

Not: varchar yerine char kullanılmasının sebebi değerin disk üzerinde kapladığı alanın kesin boyutu belirlemek için kullanılmıştır. Bu örnek veritabanı 5 milyon row a sahiptir ve indexlenmemiştir. Değişik sorguların performansı analiz edilecektir.Bunlar id(sıralanmış anahtar alanı) ve firstName(sıralanmamış anahtar olmayan alan) dir.

Örnek 1

Örnek olarak verilen veritabanı r = 5,000,000 kayıtlı, R = 204 byte sabit boyutta kayıt uzunluğu ve blok boyutu B = 1024 byte tır. Tablonun bloklama faktörü bfr = (B/R) = 1024/204 = 5 her bir disk bloğundaki kayıt sayısı. Tabloyu tutmak için gerekli toplam blok sayısı N = (r/bfr) = 5000000/5 = 1,000,000 blok.

id alanındaki arama ortalama N/2 = 500,000 blok erişimi gerektirir, id alanının aranan değerde olup olmadığını kontrol etmek için. Ama id alanı sıralı olduğu için Binary Arama yapılarak ortalama log2 1000000 = 19.93 = 20 blok erişimi ile bulunabilir. Gördüğünüz gibi bu müthiş bir gelişmedir.

Şimdi firstName alanı ne sıralanmıştır, ki böyle olduğu için Binary Arama yapamayız, ne de değerler unique dir, bu yüzden de tablo sonuna kadar aranmalıdır yani N = 1,000,000 blok erişimi gerektirir. İşte burada indekleme yapmak çok faydalıdır.

Söylendiği gibi index kaydı sadece indexlenen alanı ve orijinal kayda işaret eden pointer ı barındırmaktadır. firstName alanı için index şeması aşağıdaki gibidir:

Alan adı            Veri tipi      Disk üzerinde kapladığı alan
firstName           Char(50)       50 byte
(record pointer)    Special        4 byte

Örnek 2

Örnek olarak verilen veritabanı r = 5,000,000 kayıtlı ve index kaydı uzunluğu R = 54 byte ve varsayılan blok büyüklüğü B = 1,024 byte tır. İndeksin bloklama faktörü bfr = 1024/54 = 18 herbir disk bloğu için kayıt sayısı. Tabloyu tutmak için gerekli blok sayısı N = (r/bfr) = 5000000/18 = 277,778 bloktur.

Şimdi firstName kullanarak yapılan arama indeks yapısından faydalanarak performansı arttırır. Yani bu indeksin Binary Aramasının ortalama blok erişimi log2 277778 = 18.08 = 19 dir.

Ne zaman kullanılmalı?

Görüldüğü gibi indeks oluşturmak fazladan disk alanı gerektirir. İndeksleme yapısı sadece aramalarda işe yarar. Yeni kayıt güncelleme ve silme işlemlerinde ekstra işlem zamanı ve disk alanı gerektirir. Bu yüzden sadece aramaları hızlandırmak için yapılmalı ve yüksek veri bulunan tablolarda gerekli alanlar için yapılmalıdır.