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
Yorumlar
Yorum Gönder