Anasayfa » Dosya Organizasyonu

Computed Chaining (Hesaplanabilen Zincirler) – 2

24 Nisan 2011 2.293 kez okundu Yorum yok
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...

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ı

 

 

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.