ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

تكنيك هاي بلاك بندي اطلاعات در سيستم فايل

 
Post new topic   Reply to topic    ParsX.com Forum Index -> ذخيره و بازيابي اطلاعات - سيستم و ساختار فايلها
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed May 04, 2005 2:42 pm    Post subject: تكنيك هاي بلاك بندي اطلاعات در سيستم فايل Reply with quote

بلاك بندي ركوردهاي با طول ثابت :
همانطور كه قبلا نيز اشاره كرديم . دو نوع ركورد از لحاظ نوع طول داريم : ركوردهاي باطول ثابت و ركوردهاي با طول متغير .
لذا بسته به اين نوع ركوردها ميتوانيم انواع بلاك بندي ها را داشته باشيم .
از خصوصيات اين روش انستكه مديريت و پياده سازي ان ساده و اسان است . اما انعطاف پذيري ندارد . يعني در صورتي كه طول ركوردي تغيير كند مجدادا فايل بايد تعريف و پياده سازي شود . همچنين است در رابطه با افزايش تعداد نمونه هاي ركورد .
بلاك بندي ركوردهايي كه طول انها در فايل ثابت است . بصورت زير انجام ميپذيرد .
فايل داراي واحدي بنام Tf يا Tracking Factor است كه در ان مشخص ميشود در يك ترك ( شيار ) چند بلاك ميتوانيم داشته باشيم . واحد دوم واحد Bf است يا Blocking Factor اين واحد به ان اشاره ميكند كه در يك بلاك چند ركورد ميتوانيم داشته باشيم .

استفاده از روش بلاك بندي مزايايي دارد كه بعدا راجع به انها صحبت خواهيم كرد . اما يكي از ان مزايا حذف شدن واحد IRG : Inter Block Gap يا همان گپ بين ركوردهاست .

همانطور كه قبلا گفتيم براي شروع كردن ركورد در فايل مقداري فضاي اضافه گرفته ميشود . در ان موقع واحد گنجايشي ما روي ديسك ركورد بود . اما در تكنيك بلاك بندي ركوردهاي با طول ثابت واحد بلاك است . لذا شروع هر بلاك مقدار فضا به خود ميگيرد كه منجر به ايجاد گپ بين بلاكي ميشود IBG : Inter Block Gap .

شكل فوق شمايي از يك شيار ( ترك) را نمايش ميدهد كه داراي دو بلاك است و هر بلاك ان داراي سه ركورد است .
همانطور كه در شكل ميبينيد در هر بلاك دو نوع فضاي هرز داريم . اولين فضاي هرز كه با G نمايش داده شده است مخفف Gap است كه گپ ناشي از شروع بلاك است و نوع دوم فضاي هرز در بلاك فوق فضاي هرزي است كه با W2 نمايش داده شده است . اين نوع فضاي هرز W2 به ان دليل است كه در اين فضا ركوردهاي ما كه طول ثابت دارند جا نشده اند ! ممكن است طول ركورد ها طوري طراحي شوند كه اين فضا از بين برود .
نوع فضاي هرز ديگري كه مربوط به شيار است و نه بلاك ها فضاي هرز ناشي از جا نشدن بلاك سومي در شيار است . از انجايي كه اين بلاك در شيار جا نشده است . لذا جاي ان خالي ميماند .
براي بدست اوردن Bf از فرمول زير استفاده ميكنيم :
Bf = B/R
در فرمول فوق اگر فرض كنيم Bf فاكتور بلاكينگ است يعني تعداد ركوردها دربلاك ! براي بدست اوردن تعداد ركوردها در بلاك كافيست . طول بلاك را كه با B نمايش ميدهيم بر طول يكي از ركوردها( ثابت هستند ) تقسيم كنيم . تا ببينيم چند ركورد در بلاك جا ميشود . البته تقسيم فوق مقداري اعشار دارد كه ان مقدار اعشار را پاك ميكنيم زيرا مثلا تعداد ركوردها در بلاك نميتواند 3.7 مقدار باشد !
براي محاسبه ميزان حافظه هرز ناشي از هر بلاك همانطور كه در بالا نيز اشاره كرديم . از فرمول زير استفاده ميكنيم :
WB = W1 + W2

WB مخفف Wasted Block است يعني فضاي هرز ناشي از هر بلاك هر بلاك دو نوع فضاي هرز داشت W1 يا G كه ناشي از گپ شروع بلاك بود و W2 كه بدليل ميزان نبودن طول ركوردهاي درون بلاك است كه در نتيجه مقداري فضاي هرز را بوجود اورده است . WB هيچ گاه صفر نميشود و حداقل مقدار ان W1 است .
اما W2 ميتواند صفر باشد چراكه بسته به ان دارد كه ركوردهاي شما به چه اندازه اي محاسبه شده اند .
W2 هميشه مقداري بين
 0<=W2<R 
دارد . گاهي اين بازه را به اينصورت نيز نمايش ميدهند : 0<=W2<=R-1 در اين بازه R-1 بيانگر ان است كه W2 حتما بايد يك واحد بزرگتر از R طول ركورد باشد . واحد طول ركورد را عموما بر حسب بايت اندازه ميگيريم .
اما اگر قرار باشد مقدار متوسط WB را در طول بلاك بصورت متوسط اندازه بگيريم . مقدار فضاي ناشي از جا نشدن بلاك اخري در شيار نيز بايد محاسبه شود W3 همانطور كه گفتيم بدليل جا نشدن بلاك اخر در شيار است . بنابراين بايد به ميزان متوسط بر اندازه فضاي هرز هر بلاك وارد شود . تا بفهميم كلا چقدر مقدار فضاي هرز داشته ايم :
WB=W1+W2+W3/Tf

W3/Tf طول فضاي هرز W3 است تقسيم بر تعداد بلاك هاي يك شيار . در نتيجه با وارد كردن طول متوسط W3 براي هر بلاك به اندازه دقيق فضاي هرز دست پيدا ميكنيم . طول W3 نيز بين بازه
0<=W3<B
است . يعني W3 ميتواند صفر شود .
مقدار متوسط W2 معادل طول ركورد است تقسيم بر 2
W2 = R / 2

البته اين عمليات عملياتي اضافي است . چرا كه طول ركوردها در شيار ثابت است ! نيازي نداريم به اينكه W2 را حساب كنيم . چون W2 در طول كل شيار تغيير نميكند . اما اگر قرار باشد W2 را خودمان محاسبه كنيم و به ما ان مقدار را نداده باشند . تنها راه محاسبه ان استفاده از فرمول فوق است . چرا كه اين فضا همانطور كه گفتيم ميتواند بين صفر و R باشد لذا ميانگين اين فضا ميشود R/2
بنابراين متوسط WB ازفرمول زير بدست مي ايد :
  WB=G + R/2 + W3/Tf

حال كه توانستيم فضاي هرز ناشي از يك بلاك را پيدا كنيم . ميتوانيم اين مقدار را بازاي ركوردها نيز حساب كنيم . هرچند ركوردها در اين نوع فضاگيري چندان موثر نيستند :
WR = 1/Bf ( G + R/2 + W3/Tf )
براي محاسبه ميزان فضاي هرز ناشي از هر ركورد كافيست مقدار فضاي هرز ناشي از بالك را پيدا كنيم سپس ان را بر تعداد ركوردهاي بلاك تقسيم كنيم . فرمول فوق معادل فرمول زير است :
WR = WB / Bf



بلاك بندي ركوردهاي با طول متغير و دوپاره :
نوع ديگري از بلاك بندي ان است كه ركوردهاي ما متغير باشند و همچنين بتوانند بين بلاك ها تكه تكه نيز بشوند . از مشكلات اين روش پيچيدگي پياده سازي ان است چرا كه نرم افزار بايد مديريت نشانه گر P اخر بلاك را نيز بر عهده داشته باشد . يكي از مشكلات اين روش ان است كه در اين روش براي خواندن ركورد دو پاره بافر سيستم ( در صورتي كه تنها گنجايش يك بلاك را داشته باشد ) بايد دو بلاك را بخواند كه نتيجتا عمليات ورودي خروجي دو برابر ميشود .
تكه تكه شدن ركوردها را ميتوانيد در شكل زير به وضوح ببينيد . در شكل زير ركورد شماره 5 به دو تكه ( دو پاره ) تقسيم شده است / چرا كه در بلاك اول نگنجيده است . در اين روش ديگر حافظه هرز ناشي از نگنجيدن ركورد در بلاك را نداريم . بلكه به جاي ان فضايي اشغال ميشود جهت بيان كردن طول ركوردها چون متغير هستند و هم اينكه اشاره گري براي انكه اگر ركورد دوتكه شد . به ادرس ركورد در بلاك بعدي اشاره كند .

W1 ها همان فضاهاي هرز ناشي از شروع بلاك هستند .
P يا L1 يا L2 يا ... همگي فضاهايي اضافي هستند . L1 طول R1 را در خود نگهداري ميكند . R2 طول R3 را نگهداري ميكند . و به همين ترتيب . بنابراين ركوردها ميتوانند طول متغيري داشته باشند .
ولي اگر تعداد P ها در شكل فوق را بشماريد ميبينيد مقدار P ها يك مقدار از L1 ها بيشتر است . در واقع يك P ‌ اضافي در شكل فوق ميبينيم . كه در شكل شروع يك فلش است .
اين P اشاره گريست )كه از انجهت كه R3 در بلاك B1 جا نشده است( به B2 تا ادامه R3 را مشخص كند .
حافظه هرز W3 نيز ناشي از نگنجيدن بلاك است . در اين روش طول بلاكها ثابت است !
البته ميتوان روشي را طراحي كرد كه طول بلاكها ثابت نباشد . ميتوانيد بعنوان تمرين اين روش را خودتان پياده سازي كنيد .
Bf در اين روش از فرمول زير بدست مي ايد :
 Bf = ( B – P ) / ( R + P )

در روش اول اگر يادتان باشد طول بلاك را بر طول ركورد تقسيم كرديم . در اين روش هم اصل عمليات همان است منتهي
در صورت تقسيم طول بلاك را منهاي طول P كرده ايم . اين تفريق از ان جهت است كه :
طول بلاك ما در شكل فوق برابر است با L1+R1+…+L3+R3+P اين P جزو طول بلاك نبايد حساب شود . چرا كه اگر قرار باشد جزو طول بلاك حساب شود انگاه بعنوان اطلاعات هرز حساب نخواهد شد .
در كسر فرمول فوق طول يك ركورد به علاوه اشاره گر خود (P) شده است . R متوسط طول ركوردهاست ( چون طول ركوردها در بلاك متغير هستند )
WB = G + R + P*Bf + P +  W3/Tf
در فرمول فوق هم همانطور كه ميبينيد P كه اشاره گر است براي يك ركورد دوپاره مستقلا نوشته شده است .
بنابراين براي محاسبه WR كافيست انرا بر Bf تقسيم كنيد
WR = WB / Bf

بلاك بندي ركوردهاي با طول متغير يك پاره
از مشكلات اين روش ان است كه در اين روش حداكثر طول ركورد اندازه طول بلاك ميتواند باشد . در حاليكه در تكنيك قبلي (‌دو پاره ) چنين مشكلي نداشتيم . طول فايل در اين روش بدليل وجود حافظه هرز افزايش ميابد .
اين روش نيز دقيقا همانند بلاك بندي روش اول است منتهي بر خلاف روش اول يك فضاي اضافي جهت نگهداري طول ركوردها ( چون متغير هستند ) نيز وجود دارد .
شكل زير را ببينيد :

Bf =  ( B – W4 ) / ( R + P )

ضريب بلاك بندي اين نوع بلاك بندي همانطور كه ميبيند همانند ضريب بلاك بندي روش قبلي ( دوپاره ) است منتهي در اين روش بجاي P مقدار W4 جايگزين شده است .
Bf بطور متوسط در اينگونه بلاك بندي بصورت شكل زير است :
 Bf = ( B – R/2 ) / ( R + P )
مقدار متوسط W4 تقريبا R/2 است دقيقا بهمان دليلي كه مقدار W2 در روش اول R/2 بود . منتهي در اين روش محاسبه مقدار متوسط منطقي و كاملا درست است .
WB = G + Bf*P + W4 + W3/Tf
WR = WB/Bf


تكنيك تركيبي : در اين تكنيك روش دوم و سوم ادغام ميشوند به اين ترتيب كه مثلا فايل در مرحله لود بصورت يكپاره درست ميشود و در طول پردازش و عمليات ركوردها ميتوانند بصورت دوپاره وارد شوند .يا برعكس .
Back to top
sama
مهمون يكي دو روزه


Joined: 24 Dec 2006
Posts: 6

PostPosted: Sun Dec 24, 2006 3:32 pm    Post subject: Reply with quote

سلام
واقعا عالیه ...
تقریبا بخش زیادی از مطالب کتاب اقای مقسمی و آوردید . فقط یه زحمت دیگه اگه امکان داره بقیه فصل ها مثل فایل های ترتیبی و شاخص دار و غیره رو هم قرار بدهید ....
دیگه لازم نیست برای خوندن مطالب درسی حتما کتاب دست بگیریم
باز هم ممنون
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Mon Dec 25, 2006 11:58 am    Post subject: Reply with quote

عالی بودنش که عالیه ...
ولی فرصت قرار دادنش نیست . در ضمن اینها از کتاب دکتر رانکوهی اومده نه کتاب استاد مقسمی ... Wink
Back to top
sama
مهمون يكي دو روزه


Joined: 24 Dec 2006
Posts: 6

PostPosted: Tue Dec 26, 2006 2:27 pm    Post subject: Reply with quote

خوب ... حالا نمی خواد من و ضایع کنی تقصیر من نیست که همه نویسنده های ما از روی هم کپی می کنند ....
Back to top
alpha_gr
مهمون يكي دو روزه


Joined: 11 Apr 2007
Posts: 12

PostPosted: Thu Apr 12, 2007 10:42 pm    Post subject: 1 سوال Reply with quote

اگر BF=1 باشد چه پيش مي آيد؟
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Fri Apr 13, 2007 12:57 pm    Post subject: Reply with quote

توي فرمول ها 1 بزار كلي نتيجه مي گيري .
Back to top
alpha_gr
مهمون يكي دو روزه


Joined: 11 Apr 2007
Posts: 12

PostPosted: Fri Apr 13, 2007 2:10 pm    Post subject: اينم حرفيه Reply with quote

vahid wrote:
توي فرمول ها 1 بزار كلي نتيجه مي گيري .


اما من مي خوام يه جواب كلي بگيرم و تحويل استاد مون بدم اگه ميشه خودت يه جواب خوب برام بنويس Embarassed
Back to top
Amir
مدير مباحث عمومي سايت


Joined: 30 Nov 2004
Posts: 1088
Location: Age Hammam Nabasham To Lebasamam

PostPosted: Sat Apr 14, 2007 8:08 pm    Post subject: Reply with quote

هر که طاووس خواهد ...
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> ذخيره و بازيابي اطلاعات - سيستم و ساختار فايلها All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum