Gerçekleştirim (implementation) detaylarına girmeden index nedir, nasıl çalışır kısaca anlatayım. İsteğin doğrultusunda ufak tefek çizimler de yaptım senin için :)
Öncelikle bir veri tabanı yönetim sistemi olmadan veriyi nasıl saklayabileceğimiz üzerinde biraz kafa yoralım. Örneğin bir uygulama yazıyorsun ve uygulama içinde bir üyelik sistemi geliştiriyorsun. Tabii olara üye bilgilerini biryerde tutmak istiyorsun. İlk seçenek olarak bütün veriyi bir dosyaya yazalım diye düşünelim. Eskiden (80-90 lı yıllar diyebilirim) verileri .dat dosyalarına kaydeder ve o dosya üzerinde iş yapardık. Şahsen yazmışlığım var. Her yeni kaydı dosyanın sonuna append ederek eklediğimizi düşünelim. Elimizde nasıl bir dosya olur? Aşağıdaki resimde kısaca onu anlatmaya çalıştım.
Şekilde gördüğün mavi bloklar bir kayıt olduğunu düşünüyoruz. Veri tabanı da kullansan index oluşturmadığın durumda görüntü benzer birşey olacak.
Hemen kısaca bir model belirleyelim.
Üye
Adı varchar2(25)
Soyadı varchar2(25)
Şeklinde olsun. Bir kayıt adı ve soyadı bilgilerinden oluşacağını düşünürsek 50 byte olacak diyebiliriz. Uygulamamızda da 10.000 üyemiz olduğunu düşünelim. Toplamda dosyamız 50 x 10.000 byte kadar tutacak. Buraya kadar anlaşılmayan birşey yok sanıyorum. Şimdi bir arattırma yapalım. Aradığımız isim "Tolga". Zaman hesaplamasına (time-complexity) baktığımız zaman O(n) bir zaman göreceğiz. Yani 10K kayıtta en kötü son kayıt olur. Baştan aşağı aramak durumunda kalırız.
Peki hızlandırmak için ne yapabiliriz?
- Sıralattırma algoritmalarında her ne kadar bir sürü seçeneğimiz olsa da arattırmalarda pek bir seçenek
- Bir lineer arattırma var ki zaten yukarıda yazdığımız o.
- İkinci olarak binary search var.
- Elimizdeki veri sıralı mı? Değil. Her geleni en sona ekledik çünkü.
- Her geleni sıralamaya kalksak disk üzerinde kayıtların yerlerini değiştirmek için bütün kayıtları oynatmak gerekecek. Her ekleme işlemi de bizim için çile olacak.
- Bir diğer seçenek hash kullanmak ki bu kadar büyük kayıtlarda ona uygun bir hash algoritması bulmak da sıkıntı.
Bu durumda hangisini seçmen gerekir?
İndex olmayan bir alan üzerinde arattırma yaptığın zaman sonucun yavaş dönmesinin sebebi bu, lineer arattırma yapıyorsun ve kayıt sayın ne kadar çoksa o kadar uzun süren bir sorgun oluyor.
Zamanında akıllı abilerimiz bu işleri daha performanslı halledebilmek için yöntemler geliştirmek istemişler ve ikinci arattırma yani binary search daha iyi olur demişler. Peki elimizdeki veri sıralı değil onu ne yapacağız sorusuna cevap olarak da bütün veriyi olmasa bile sadece arattıracağımız veriyi hafızaya sıralı olarak yükleyip öyle tutalım ve oradan arattıralım demişler. Aşağıdaki gibi bir görüntü ortaya çıkmış.
Temel mantık sadece indexlenecek alanı hafızada tutalım, tree olarak tutalım ve hızımızı arttıralım. Veri yapıları dersinden hatırlanacağı üzere normal bir binary tree üzerinde arattırma maliyeti log(n) Burada log işleminin tabanı 2. O zaman 10.000 kayıt içinde arattırma maliyeti ne oluyor O(logn) oluyor ki 10K kayıtda maliyet 13,28 oluyor. Yani en kötü ihtimalle 14 hamlede kaydı buluyoruz. Yukarıdaki gördüğün üzere kırmızı kutu içine aldığım kısım yani tree direk olarak hafızada (RAM) tutuluyor ki disk erişimi minimum olsun. Burada aranan kayıt bulunduğu zaman o kaydın disk üzerindeki yerinden gidilip kaydın tamamı alınıyor.
Index kullanımında şöyle sorular çıkıyor:
Bu tree nasıl dengeli duruyor ve log(n) i nasıl garantiliyor?
Bu sorunun cevabı için binary-tree ve B+ tree kavramlarına bakman gerekiyor. Onları buraya yazmayayım. Ama db'ler genellikle B+ ve B- tree kullanarak bu işlemleri yapıyor.
Peki her alana index koyarsak ne olur?
Kırmızı işaretlenen alan ne kadar çoksa RAM üzerinde o kadar çok yük var. Sunucunuz ne kadar kuvvetli ona göre bakacaksınız. Her yere index koyup bu sefer de RAM yetmeyip diske pagination felan yaptırırsanız lineer (indexsiz) hıza geri yaklaşırsınız.
Son olarak ufak bir detay B+ ve B- ağaçlarda işlem maliyeti log(n) olarak alınırken burada log tabanı 2 olmaz. Her seferinde kaç parçaya bölünürse o kadar olur. Benim çizdiğim şekilde her node içinde 3 tane veri olduğunu düşünürsek bu tabloda log 3 tabanında olur. Bu oracle'da ayarlanabiliyordu sanıyorum.
İyi çalışmalar.