Veri İndeksleme Yöntemleri

İndeks, veri tabanındaki tabloda tutulan verilere etkin ve hızlı bir şekilde erişmeyi sağlayan sistemdir. İndeks mekanizmalarında veriye hızlı bir şekilde erişmek için  basit anlamda ikili ağaçlar ve ikili arama algoritmaları kullanılmaktadır. Ancak bu yöntemin dezavantajları  vardır. İndekslenecek alana göre tüm kayıtların sıralı hale getirilmesi gerekmektedir. İkili arama algoritmasında, her bir adımda aranan değerin, sıralı verilerin orta değerine eşit olup olmadığı kontrol edilir. Eşit olmaması durumunda aranan değerin orta değer tarafından iki parçaya ayrılan kısımlardan hangisinde olduğu kontrol edilir. Aranan değeri içeren kısım bir sonraki adımda arama yapılacak liste olur ve bu sayede arama yapılan listedeki eleman sayısı her adımda yarıya indirgenmiş olur. Bu algoritma ile, aranan değerinin yeri, N elemanlı bir listede en fazla log2n karşılaştırma yaparak bulunur. Örneğin, 1 milyon kayıt için en fazla 20 karşılaştırma yaparak, 1 milyar kayıt için  en fazla 30 karşılaştırma yaparak, aranan değerin yeri bulunmaktadır.

Veri tabanında kullanılan ikili ağaçlardan farklı olarak. "elastik aramada" kullanılan yaklaşım inverted index yaklaşımıdır. Bu yaklaşım, dokümanlar içerisindeki kelimelerimizi bu kelimelerin hangi dokümanlar ile ilişkili olduklarını, dokümanın bilgisini bir yerde tutmaktadır. Terimler içerisinde bir arama yapıldığında, terimlere karşılık gelen dokümanları hızlıca bulmaktadır. Yani dokümanlara kelimeler üzerinden ulaşmaktadır. Bu yüzden "inverted (tersine) index" denilmektedir. Bu yaklaşımda, hızlı arama yapmak için kelimeler de sıralanmaktadır. Bu yaklaşıma örnek vermek gerekirse, iki dokümanımız  aşağıdaki gibi olsun.

Doküman 1: CRYPTTECH 2006 yılında Siber Güvenlik alanında teknolojiler ve ürünler geliştirmek üzere kurulan bir ARGE şirketidir.

Doküman 2: CRYPTTECH DLP ve Güvenlik İzleme ürünleri ile Siber Güvenlik alanında Türk teknoloji üreticisi olarak birçok firmaya öncü olmuştur.

Kelime	Doküman ID
2006	1
alan	1,2
arge	1
crypttech	1,2
dlp	2
güvenlik	1,2
izleme	2
kurulan	1
öncü	2
siber	1,2
şirket	1
teknoloji	1,2
türk	2
üretici	2
ürün	1,2
yıl	1

Bu yaklaşım için öncelikle log dosyası parse edilerek, indekslenecek alan ilgili bilgiler çekilir.   Herhangi bir dosya için farklı olan terimlerin ve dosyadaki satırların başlangıç pozisyonları belirlenir. Terimler ve terimlerin dosyadaki satırlarının yer aldığı başlangıç pozisyonları bloklar halinde, pozisyonların tutulduğu dosyaya yazılır.  Terimler ve terimlerin yer aldıkları file id ve o terimlerin pozisyonlarının tutulduğu dosyadaki yer aldıkları başlangıç ve bitiş pozisyonları ve sayısı ile birlikte indeksli bir şekilde sqlite veritabanında tutulur. Hazır indeks yapısının bulunması ve herhangi bir kurulum gerektirmediği için sqlite veri tabanı kullanılmıştır. Örnek bir şekilde ip verilerinin tutulduğu tablo aşağıdaki tabloda  görülmektedir.

Yukarıda, tablodaki ilk satırda, 10.105.94.51 ip terimi, pos alanındaki 0_0_3016 0 verisi, 10.105.94.51 ip sinin yer aldığı dosyanın id’sini belirtir. O dosyada yer aldığı satırlarının pozisyonları ise 0_3016 verisinde saklıdır. 0 ile 3016 byte arasında tutulmaktadır. 754 adet mevcuttur.

Bu yöntemin avantajları:

• Daha az yer kaplar. Yalnızca tekil olan kelimeler ve onların pozisyonları tutulur. İndeksli verilerde veri kayıt ekleme daha hızlıdır. Çünkü tekil olan kelimeler veri tabanına atıldığı için daha az kayıt atılır. İkinci olarak indeksli tablolarda kayıt ekleme hızı, veri sayısı artıkça azalır.
• Tekil olan kelimeler tutulduğu için daha az kayıt içerdiğinden, başlangıçta indeksli tablo bile olsa daha hızlı eklenecektir.
• Günlük olarak istatistiksel bilgiler elde edilecekse, tüm veriler eklendikten sonra indeks oluşturulabilir.

Önerilen indeks yaklaşımını indeks oluşturma süresi, kapladığı alan ve arama sürelerini  test etmek için lucene veritabanı, elastik arama ve yaklaşımımız ile ilgili testler yapılmıştır. Aşağıdaki tablodaki sonuçlar elde edilmiştir. Aşağıdaki  sonuçlar, 47 GB’lık yaklaşık 1000 dosya üzerinde aynı bilgisayar üzerinde elde edilmiştir.

Ürünler	İndeks Oluşturma süresi(dk)	Size (MB)	CPU kullanımı	Olmayan Kayıt Arama Süresi (ms)	Az Kayıt Arama Süresi (ms)	Çok Kayıt Arama Süresi (ms)
Lucene	179	8853	%20-%30	955 ms	988 ms	1600 ms
Elastik Arama	362	36288	%70-%80	3 ms	100 ms	1260 ms
Yaklaşımımız	27(başlangıçta indeksyok) Başlangıçta İndeks varsa 50 dk.	4014	%10-%30	1 ms	20-300 ms	300-600 ms

Ahmet BACAK
Information Security Researcher & Software Engineer