Computed Chaining (Hesaplanabilen Zincirler) – 2
Bu yazımda computed chaining için farklılıkları (variant), multiple chaining, ve çakışma çözümleme tekniklerinin karşılaştırılmasından bahsedeceğim. Yazımın birinci bölümünü okumadıysanız buradan okuyabilirsiniz.
Örn: A kaydı için pseuodolink değeri 6 olsun ve fakat offset alanı için 2 bitlik bir alan ayrılsın. Bu durumda2 bit ile ifade edilebilecek en büyük sayı(11)2 olup A kaydının ardından gelen herhangi bir kayda erişmek için 1 probe yeterli olabilecek iken artık 2 probe’un kullanılması gerekecektir.
Farklılık (Variant)
Computed Chaining yaklaşımının performansınıarttırmak için bazıbir takım düzenlemeler yapılabilir.
Bir kaydıaradığımızda, bu işlemi olabildiğince kısa sürede ve etkili bir şekilde gerçekleştirmek isteriz. Aynıdurum günlük hayatımızda bir objeyi ararken de aynışekilde gerçekleşir.
Örn: Bir nesneyi ev içerisinde aramak istediğinizi düşünün. Eğer bu nesnenin evin hangi odasında olduğunu biliyorsanız, nesneyi direkt o oda içerisinde arayabilirsiniz. Diğer durumda ise arama işlemini evin tüm köşesinde yapmak zorunda kalabilirsiniz.
Böyle bir yaklaşımdan genel olarak BÖL ve YÖNET olarak söz etmek mümkündür.
Eğer kayıtlar daha küçük gruplara ayrılırsa ve aradığımız kaydın hangi grup içersinde yer aldığınıbiliyorsak arama işlemi daha basit olacaktır.
Bir probe chain birden fazla parçaya bölünür ve bir kayıt için sadece ilgili olduğu gruba bakılır.
Standart hash fonksiyonu ve arttırma fonksiyonun yanısıra bir de kaydın hangi gruba dahil olacağınıbelirten g(key) hash fonksiyonu bulunmaktadır.
g(key) = 0,1,…,R-1 olabilir. R alt grup sayısıdır.
g(key) = key Mod R
Kullandığımız bu anahtarlara ek olarak 2 anahtar değeri daha olsun. Bunlar :27, 18, 29, 28, 39, 13, 16, 38, 53
Artım fonksiyonu ise:i(key)=Quotient(Key/11) mod11
Halka seçim fonksiyonu ise:g(key) = key mod 2
Bu durumda, eğer anahtar değeri çift ise 0. halkaya, tek ise 1. halkaya dahil olacaktır.
27 ve 18 herhangi bir çakışma olmadan doğrudan 5. ve 7. konumlara yerleştirilebilir.
29 kaydı7 numaralı konuma yerleşmek istiyor fakat bu noktada daha önceki 18 anahtarıile çakışma meydana gelmektedir.
28 herhangi bir çakışma olmadan doğrudan 6. konumlara yerleştirilebilir.
39 kaydı6 numaralıkonuma yerleşmek istiyor fakat bu noktada daha önceki 28 anahtarıile çakışma meydana gelmektedir.
13 herhangi bir çakışma olmadan doğrudan 2. konumlara yerleştirilebilir.
16 kaydı5 numaralıkonuma yerleşmek istiyor fakat bu noktada daha önceki 27 anahtarıile çakışma meydana gelmektedir
38 kaydı5 numaralıkonuma yerleşmek istiyor fakat bu noktada daha önceki 27 anahtarıile çakışma meydana gelmektedir.
53 kaydı9 numaralıkonuma yerleşmek isteyeceğinden bir çakışma olacaktır. Fakat burada karşımıza farklıbir durum çıkmaktadır.
53 anahtarının konumu olan 9 numaralıkonumda bulunan 16 anahtarının home adresi farklıdır. Bu durumda 16 anahtarıve onun ardından gelen diğer anahtarların ötelenmesi gerekecektir. Bu işlem için öncelikle, 16 ve ardındaki anahtar değerleri sonra tekrar eklenmek üzere tablodan geçici olarak ayrılır.Böylelikle boşalan konuma 53 kaydıkolaylıkla yerleşebilir.
Burada kayıtların retrievallarıiçin gerekli olan probe sayısında çok fazla bir değişim olmamıştır. Değişimin fark edilebilmesi için örneğimize 49 anahtarınıekleyelim.
Çakışma Çözümleme Tekniklerinin Karşılaştırılması
Bunlara da Göz Atmak İsteyebilirsiniz.
<<< Önceki: Computed Chaining (Hesaplanabilen Zincirler)
Sonraki: JQuery ile Ajax Kullanımı >>>
Yorum Bırakın!