Index Yapısına Giriş

Bir veritabanının kendisine verilen veriyi saklayabilmesi ve bu veriye tekrar erişmek istendiğinde veriyi aynen geri verebilmesi gerekir. Şimdi de kendimizi bir veritabanıymış gibi düşünelim, bir de bu açıdan bakalım. Bize veri verildiğinde bunu nasıl saklarız ve bize bir veri sorulduğunda bu veriyi nasıl sağlarız.

Bir projeye başlarken oturup kendi veritabanı uygulamanızı sıfırdan yazmazsınız, halihazırda olan veritabanı motorlarının birkaçı arasından ihtiyacınıza uygun olarak seçim yaparsınız. Seçtiğiniz veritabanı motorunun workload altında nasıl bir performans sağlayacağını bilmeniz için de bu motorun arkaplanda nasıl çalıştığına dair biraz bilginizin olması gerekir.

Temelde transaction merkezli ve analitik merkezli veritabanı motorları arasında büyük farklar bulunmaktadır. Ama bundan önce geleneksel relational veritabanlarından ve NoSQL veritabanlarından bahsedeceğiz: log-structured storage engine ve page-oriented storage engine yapıları.

Normalde terminali açıp herhangi bir değeri bu değişkenlere atayabilirsiniz, daha sonrasında bu değişkeni tekrar kullanarak depolanan değeri tekrar çağırabilirsiniz. En başta bahsettiğimiz temel yapı üzerine terminaldeki bu yapıyı bir veritabanı olarak kullanabilirsiniz. Ancak belli bir yerden sonra çok kötü performans göstereceklerdir, örneğin bir değeri aramak istediğinizde baştan sonra tüm değerleri teker teker kontrol edecektir. Siz içerideki veri sayısını iki katına çıkardığınızda istediğiniz değişkeni arama süresi de iki katına çıkacaktır.

Bir veritabanında istediğiniz değere hızlıca ulaşmak için index dediğimiz bir veri yapısı bulunur. Bu yapısı, veri sayfaları içerisinde yer işareti gibidirler, bir şeyi aradığınızda hemen yerini size söyleyiverir. Bu index’leri veri sayfaları arasında farklı yerlerde oluşturduğumuzu düşünürsek verileri aradığımız verileri daha hızlı bir şekilde bulabiliriz.

Index yapısı, veritabanı içerisinde oluşturduğumuz veriden türetilebilen bir veri yapısıdır, index oluşturduğunuzda elimizdeki veri üstünde de herhangi bir negatif etkisi yoktur. Index’lerin veritabanı içerisine kaydettiğimiz veriden oluşturulduğunu söylemiştik, yani her veri güncelleme işleminde oluşturulan indexler üzerinde de değişim olacaktır, performansa diğer bir negatif etkisi bu tarafta olabilir. Eğer bir index okuma hızını önemli ölçüce artırsa da yazma hızını bir miktar artırabilmektedir. Bunun için veritabanları sadece index’leri oluşturma, değiştirme ve silme işlemlerini geliştiriciye sağlar, indexleri oluşturup yönetmek ise geliştiricinin veri ve sorgu yapılarını göz önüne alarak index’leri güzelce oluşturup gereksiz yükten kaçınmasına kalmıştır.

Log-structured index’ler arasında en yaygın olanı B-tree index’lerdir. B-tree indexi haricinde hash index’leri, LSM-tree indexleri de bulunmaktadır. B-tree indexleri neredese bütün relational veritabanı ve çoğu non-relational veritabanı sistemlerinde standart index yapısı olarak sunulmaktadır. B-tree yapıları da kay-value değerlerini key bazlı sıralar, böylelikle lookup dediğimiz değer aramaları da hızlı gerçekleşir. B-tree yapıları, veritabanını genel olarak sabit 4KB boyutta bloklar haline getirir ve buna sayfa yani page yapısı denir. Tek seferde bir page üzerinde read veya write işlemi yapılabilmektedir. Bu yapı aslında disk sistemine çok benzemektedir, diskler de sabit boyutta blok yapıları şeklinde düzenlenmişlerdir.

Her bir page’e, spesifik bir adres kullanılarak erişilebilir, bu sayede bir page başka bir page’e bağlanabilir. Tree yapısındaki bir page root olarak belirlenebilir. Lookup işlemine başlandığı zaman bu page içerisinde değer aranmaya başlanır. Page içerisinde birkaç key değeri ve child page’lere referans değerleri bulunur.  B-tree yapısında bir page dolduğu zaman, bu page iki farklı page’e ayrılır ve bu page’in parent page’in referansları da yeni iki child page’e referans olacak şekilde overwrite edilir. Bu tehlikeli bir işlemdir çünkü bu page’lerin birkaçı yazılırken veritabanı çökerse veri sayfaları bozulur ve index’ler çöker (yani parent page’i olmayan, orphan page dediğimiz page’ler oluşur). Veritabanını bu gibi bozulmalara karşı korumak için Write-Ahead-Log (WAL) isminde ekstra bir veri yapısı (diğer ismiyle redolog) bulunmaktadır. Her bir page değişikliği bu append-only redolog dosyasına yazılır. Veritabanı çöktükten sonra tekrar ayağa kaldırıldığında bu dosya yardımıyla B-tree yapısı tekrar düzenli hale getirilir.

 Page’lerde değişiklik yaparken önemli olan diğer bir sorun ise concurreny kontrolüdür, eğer birden fazla OS thread’i tarafından B-tree yapısına erişim sağlanıyorsa B-tree yapısındaki veriler tutarsız hale gelecektir. Bu tehlikeden korunmak içinse latch (lightweight lock) veri yapısı kullanılmaktadır.

B-tree yapılarında verileri saklarken page’ler içerisinde biraz boş alan bırakır. Bunun nedeni fragmentation yapısıdır. Saklanmak istenen veri bir page içerisinde sığamayacak kadar büyük olduğu durumlardan çoğu zaman kurtulmak için bu boş alanlar kullanılır.

Sonraki yazıda görüşmek üzere.