View previous topic :: View next topic |
Author |
Message |
vahid بي تو هرگز
Joined: 26 Nov 2004 Posts: 3067 Location: Tehran
|
Posted: Wed May 04, 2005 2:42 pm Post subject: تكنيك هاي بلاك بندي اطلاعات در سيستم فايل |
|
|
بلاك بندي ركوردهاي با طول ثابت :
همانطور كه قبلا نيز اشاره كرديم . دو نوع ركورد از لحاظ نوع طول داريم : ركوردهاي باطول ثابت و ركوردهاي با طول متغير .
لذا بسته به اين نوع ركوردها ميتوانيم انواع بلاك بندي ها را داشته باشيم .
از خصوصيات اين روش انستكه مديريت و پياده سازي ان ساده و اسان است . اما انعطاف پذيري ندارد . يعني در صورتي كه طول ركوردي تغيير كند مجدادا فايل بايد تعريف و پياده سازي شود . همچنين است در رابطه با افزايش تعداد نمونه هاي ركورد .
بلاك بندي ركوردهايي كه طول انها در فايل ثابت است . بصورت زير انجام ميپذيرد .
فايل داراي واحدي بنام Tf يا Tracking Factor است كه در ان مشخص ميشود در يك ترك ( شيار ) چند بلاك ميتوانيم داشته باشيم . واحد دوم واحد Bf است يا Blocking Factor اين واحد به ان اشاره ميكند كه در يك بلاك چند ركورد ميتوانيم داشته باشيم .
استفاده از روش بلاك بندي مزايايي دارد كه بعدا راجع به انها صحبت خواهيم كرد . اما يكي از ان مزايا حذف شدن واحد IRG : Inter Block Gap يا همان گپ بين ركوردهاست .
همانطور كه قبلا گفتيم براي شروع كردن ركورد در فايل مقداري فضاي اضافه گرفته ميشود . در ان موقع واحد گنجايشي ما روي ديسك ركورد بود . اما در تكنيك بلاك بندي ركوردهاي با طول ثابت واحد بلاك است . لذا شروع هر بلاك مقدار فضا به خود ميگيرد كه منجر به ايجاد گپ بين بلاكي ميشود IBG : Inter Block Gap .
شكل فوق شمايي از يك شيار ( ترك) را نمايش ميدهد كه داراي دو بلاك است و هر بلاك ان داراي سه ركورد است .
همانطور كه در شكل ميبينيد در هر بلاك دو نوع فضاي هرز داريم . اولين فضاي هرز كه با G نمايش داده شده است مخفف Gap است كه گپ ناشي از شروع بلاك است و نوع دوم فضاي هرز در بلاك فوق فضاي هرزي است كه با W2 نمايش داده شده است . اين نوع فضاي هرز W2 به ان دليل است كه در اين فضا ركوردهاي ما كه طول ثابت دارند جا نشده اند ! ممكن است طول ركورد ها طوري طراحي شوند كه اين فضا از بين برود .
نوع فضاي هرز ديگري كه مربوط به شيار است و نه بلاك ها فضاي هرز ناشي از جا نشدن بلاك سومي در شيار است . از انجايي كه اين بلاك در شيار جا نشده است . لذا جاي ان خالي ميماند .
براي بدست اوردن Bf از فرمول زير استفاده ميكنيم :
در فرمول فوق اگر فرض كنيم Bf فاكتور بلاكينگ است يعني تعداد ركوردها دربلاك ! براي بدست اوردن تعداد ركوردها در بلاك كافيست . طول بلاك را كه با B نمايش ميدهيم بر طول يكي از ركوردها( ثابت هستند ) تقسيم كنيم . تا ببينيم چند ركورد در بلاك جا ميشود . البته تقسيم فوق مقداري اعشار دارد كه ان مقدار اعشار را پاك ميكنيم زيرا مثلا تعداد ركوردها در بلاك نميتواند 3.7 مقدار باشد !
براي محاسبه ميزان حافظه هرز ناشي از هر بلاك همانطور كه در بالا نيز اشاره كرديم . از فرمول زير استفاده ميكنيم :
WB مخفف Wasted Block است يعني فضاي هرز ناشي از هر بلاك هر بلاك دو نوع فضاي هرز داشت W1 يا G كه ناشي از گپ شروع بلاك بود و W2 كه بدليل ميزان نبودن طول ركوردهاي درون بلاك است كه در نتيجه مقداري فضاي هرز را بوجود اورده است . WB هيچ گاه صفر نميشود و حداقل مقدار ان W1 است .
اما W2 ميتواند صفر باشد چراكه بسته به ان دارد كه ركوردهاي شما به چه اندازه اي محاسبه شده اند .
W2 هميشه مقداري بين دارد . گاهي اين بازه را به اينصورت نيز نمايش ميدهند : 0<=W2<=R-1 در اين بازه R-1 بيانگر ان است كه W2 حتما بايد يك واحد بزرگتر از R طول ركورد باشد . واحد طول ركورد را عموما بر حسب بايت اندازه ميگيريم .
اما اگر قرار باشد مقدار متوسط WB را در طول بلاك بصورت متوسط اندازه بگيريم . مقدار فضاي ناشي از جا نشدن بلاك اخري در شيار نيز بايد محاسبه شود W3 همانطور كه گفتيم بدليل جا نشدن بلاك اخر در شيار است . بنابراين بايد به ميزان متوسط بر اندازه فضاي هرز هر بلاك وارد شود . تا بفهميم كلا چقدر مقدار فضاي هرز داشته ايم :
W3/Tf طول فضاي هرز W3 است تقسيم بر تعداد بلاك هاي يك شيار . در نتيجه با وارد كردن طول متوسط W3 براي هر بلاك به اندازه دقيق فضاي هرز دست پيدا ميكنيم . طول W3 نيز بين بازه است . يعني W3 ميتواند صفر شود .
مقدار متوسط W2 معادل طول ركورد است تقسيم بر 2
البته اين عمليات عملياتي اضافي است . چرا كه طول ركوردها در شيار ثابت است ! نيازي نداريم به اينكه W2 را حساب كنيم . چون W2 در طول كل شيار تغيير نميكند . اما اگر قرار باشد W2 را خودمان محاسبه كنيم و به ما ان مقدار را نداده باشند . تنها راه محاسبه ان استفاده از فرمول فوق است . چرا كه اين فضا همانطور كه گفتيم ميتواند بين صفر و R باشد لذا ميانگين اين فضا ميشود R/2
بنابراين متوسط WB ازفرمول زير بدست مي ايد :
حال كه توانستيم فضاي هرز ناشي از يك بلاك را پيدا كنيم . ميتوانيم اين مقدار را بازاي ركوردها نيز حساب كنيم . هرچند ركوردها در اين نوع فضاگيري چندان موثر نيستند :
| WR = 1/Bf ( G + R/2 + W3/Tf ) | براي محاسبه ميزان فضاي هرز ناشي از هر ركورد كافيست مقدار فضاي هرز ناشي از بالك را پيدا كنيم سپس ان را بر تعداد ركوردهاي بلاك تقسيم كنيم . فرمول فوق معادل فرمول زير است :
بلاك بندي ركوردهاي با طول متغير و دوپاره :
نوع ديگري از بلاك بندي ان است كه ركوردهاي ما متغير باشند و همچنين بتوانند بين بلاك ها تكه تكه نيز بشوند . از مشكلات اين روش پيچيدگي پياده سازي ان است چرا كه نرم افزار بايد مديريت نشانه گر 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 تقسيم كنيد
بلاك بندي ركوردهاي با طول متغير يك پاره
از مشكلات اين روش ان است كه در اين روش حداكثر طول ركورد اندازه طول بلاك ميتواند باشد . در حاليكه در تكنيك قبلي (دو پاره ) چنين مشكلي نداشتيم . طول فايل در اين روش بدليل وجود حافظه هرز افزايش ميابد .
اين روش نيز دقيقا همانند بلاك بندي روش اول است منتهي بر خلاف روش اول يك فضاي اضافي جهت نگهداري طول ركوردها ( چون متغير هستند ) نيز وجود دارد .
شكل زير را ببينيد :
| 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
|
Posted: Sun Dec 24, 2006 3:32 pm Post subject: |
|
|
سلام
واقعا عالیه ...
تقریبا بخش زیادی از مطالب کتاب اقای مقسمی و آوردید . فقط یه زحمت دیگه اگه امکان داره بقیه فصل ها مثل فایل های ترتیبی و شاخص دار و غیره رو هم قرار بدهید ....
دیگه لازم نیست برای خوندن مطالب درسی حتما کتاب دست بگیریم
باز هم ممنون |
|
Back to top |
|
|
vahid بي تو هرگز
Joined: 26 Nov 2004 Posts: 3067 Location: Tehran
|
Posted: Mon Dec 25, 2006 11:58 am Post subject: |
|
|
عالی بودنش که عالیه ...
ولی فرصت قرار دادنش نیست . در ضمن اینها از کتاب دکتر رانکوهی اومده نه کتاب استاد مقسمی ... |
|
Back to top |
|
|
sama مهمون يكي دو روزه
Joined: 24 Dec 2006 Posts: 6
|
Posted: Tue Dec 26, 2006 2:27 pm Post subject: |
|
|
خوب ... حالا نمی خواد من و ضایع کنی تقصیر من نیست که همه نویسنده های ما از روی هم کپی می کنند .... |
|
Back to top |
|
|
alpha_gr مهمون يكي دو روزه
Joined: 11 Apr 2007 Posts: 12
|
Posted: Thu Apr 12, 2007 10:42 pm Post subject: 1 سوال |
|
|
اگر BF=1 باشد چه پيش مي آيد؟ |
|
Back to top |
|
|
vahid بي تو هرگز
Joined: 26 Nov 2004 Posts: 3067 Location: Tehran
|
Posted: Fri Apr 13, 2007 12:57 pm Post subject: |
|
|
توي فرمول ها 1 بزار كلي نتيجه مي گيري . |
|
Back to top |
|
|
alpha_gr مهمون يكي دو روزه
Joined: 11 Apr 2007 Posts: 12
|
Posted: Fri Apr 13, 2007 2:10 pm Post subject: اينم حرفيه |
|
|
vahid wrote: | توي فرمول ها 1 بزار كلي نتيجه مي گيري . |
اما من مي خوام يه جواب كلي بگيرم و تحويل استاد مون بدم اگه ميشه خودت يه جواب خوب برام بنويس |
|
Back to top |
|
|
Amir مدير مباحث عمومي سايت
Joined: 30 Nov 2004 Posts: 1088 Location: Age Hammam Nabasham To Lebasamam
|
Posted: Sat Apr 14, 2007 8:08 pm Post subject: |
|
|
هر که طاووس خواهد ... |
|
Back to top |
|
|
|