ذخیره روحانی

[reza]

من اون سوالای تستی آخر کتاب روحانی روخواستم اگه دارین لط ف کنید به این آدرس بفرستید
maleky_a_12@yahoo.com
اگه میشه زودتر ممنون

[bahram_rad]

در این پست می خوام با وجود انکه تاریخ ان گذشته نخواستم تایپیک جدید بزنم خلاصه ای از درس ذخیره و بازیابی رو بنویسم

1-آشنايي با طراحي و مشخصات ساختار فايلها
ساختار فايل ترکيبي از نحوه نمايش داده ها در فايل ها و عمليات لازم براي دستيابي به داده ها است. ساختار فايل به برنامه کاربردي اين امکان را مي دهد که داده ها را بخواند ،بنويسد و اصلاح کند.

طي سه دهه اخير با بررسي تکامل ساختارهاي فايل مشاهده مي کنيم که طراحي ساختار فايل ابتدا از ترتيبي شروع شد ،سپس به ساختارهاي درختي رسيد و سرانجام دستيابي مستقيم مطرح شد. در همه اين موارد مشکلات و ابزارهاي طراحي مشابهي مشاهده شده است. اين ابزارها را ابزارهاي مفهومي مي نامند که روش هايي براي تنظيم و حل يک مسئله طراحي اند يک مشکل اصلي در توصيف کلاس هايي که بتوان براي طراحي ساختار فايل آنها را به کار برد ، آن است که اين کلاس ها پيچيده و در حال رشد هستند. کلاس هاي جديد غالباً شکل اصلاح شده يا توسعه يافته اي از کلاس ها ديگر بوده ،جزئيات ارائه داده ها و عمليات باز هم پيچيده تر مي شود.

در يک سيستم اطلاعاتي شيء گرا محتوا و رفتار داده ها ، در يک طراحي منسجم مي شود. اشياي سيستم به کلاس هاي اشيايي با ويژگي هاي مشترک تقسيم مي شوند. هر کلاس توسط اعضاي (members) خود توصيف مي شود که يا صفات داده ها (عضوهاي داده اي) يا توابع (توابع عضو يا متدها) هستند.

مشکل اصلي در طراحي ساختار فايل زمان نسبتاً زيادي است که براي گرفتن اطلاعات از ديسک مورد نياز است. در همه طراحي هاي ساختار فايل آنچه مورد توجه است به حد اقل رساندن دفعات دستيابي به ديسک و به حد اکثر رساندن احتمال وجود اطلاعات مورد نظر برنامه کاربردي در حافظه است.

____________________________
2-عمليات مهم پردازش فايل
هنگامي که درباره فايلي روي يک ديسک يا نوار صحبت مي کنيم ،منظور ما مجموعه اي از بايت ها است که در آنجا ذخيره شده اند. فايل در اين معنا داراي موجوديت فيزيکي است. يک ديسک ممکن است حاوي صدها و حتي هزاران فايل فيزيکي باشد.
برنامه غالباً نمي داند بايت ها از کجا مي آيند يا به کجا مي روند ، اين را مي داند که کدام خط را مورد استفاده قرار داده است. اين خطوط را معمولاً فايل منطقي مي نامند تا از فايل فيزيکي ،که روي ديسک يا نوار قرار دارد متمايز گردد.
هنگامي که شناسه (identifier) فايل منطقي با دستگاه يا فايل فيزيکي ارتباط پيدا کرد ،بايد اعلام کنيم که مي خواهيم با فايل چه کنيم :
۱) باز کردن يک فايل موجود ۲) ايجاد يک فايل جديد و حذف محتويات موجود در فايل فيزيکي


هنگامي که برنامه اي به صورت عادي پايان مي يابد فايل ها معمولاً به طور خودکار بسته مي شوند. در نتيجه اجراي يک دستور بستن در داخل برنامه فقط براي محافظت آن در برابر اتلاف داده ها در صورت توقف برنامه و آزاد کردن نام فايل هاي منطقي براي استفاده دوباره ضروري است.
خواندن و نوشتن در پردازش فايل اهميت بنيادي دارند ،اينها اعمالي هستند که پردازش فايل را به يک عمل ورودي/خروجي تبديل مي کنند.
براي دستيابي آسان به تعداد زياد از فايل ها کامپيوتر روشي براي سازماندهي فايل ها دارد. در يونيکس اين روش سيستم فايل ناميده مي شود. چون هر نام فايل در سيستم يونيکس بخشي از سيستم فايلي است که با ريشه آغاز مي شود ،هر فايل را مي توان انحصاراً با دادن نام مسير آن شناسايي کرد.
يکي از پر قدرت ترين ايده ها در يونيکس تعريفي است که از فايل مي شود. در يونيکس فايل مجموعه اي از بايت ها است و چگونگي و محل ذخيره آنها هم مهم نيست. همچنين مهم نيست که اين بايت ها از کجا مي آيند. اين نگرش معمولي به فايل موجب مي شود کاري را که در سيستم عامل هاي ديگر به زحمت انجام مي شوند ، در اين سيستم عامل به راحتي انجام پذير باشد.
يونيکس فرمان هاي بسياري براي دستکاري فايل ها دارد که عبارتند از :cat, tail, cp, mv, rm, chmod, ls, mkdir, rmdir
__________________________
3-حافظه جانبي و نرم افزار سيستم
دستگاه هاي حافظه جانبي ،با حافظه تفاوت بسيار دارند. همان طور که پيش از اين نيز متذکر شديم يک اختلاف از آنجا ناشي مي شود که در دستگاه هاي حافظه جانبي زمان بيشتري براي دستيابي مورد نياز است. اختلاف ديگر آن است که همه دستيابي ها يکسان نيستند.
ديسک ها انواع مختلفي دارند :
1-ديسک هاي سخت
2-(hard disks) ديسک هاي فلاپي
3-(floppy disks) کارتريج ديسک
4- ديسک هاي نوري

قسمت دوم

اطلاعات ذخيره شده روي ديسک ،در سطح يک يا چند صفحه نگهداري مي شود. ترتيب کار به صورتي است که اطلاعات به صورت شيارهايي (tracks) روي سطح ديسک نگهداري مي شوند. هر شيار غالباً به چند سکتور (sector) تقسيم مي شود.
سکتور کوچکترين بخشي از ديسک است که قابل آدرس دهي است.
ديسک گردان ها معمولاً چند صفحه دارند. شيارهايي که مستقيماً در بالا و پايين يکديگر قرار دارند ،يک سيلندر را تشکيل مي دهند. اهميت سيلندر در آن است که به همه اطلاعات روي يک سيلندر مي توان بدون حرکت دادن بازوي نگهدارنده هد (head) خواندن/نوشتن دستيابي داشت. حرکت اين بازو پيگرد (seeking) نام دارد.
ظرفيت ديسک تابعي از تعداد سيلندرها ،تعدا شيارها به ازاي هر سيلندر و ظرفيت هر شيار است.
دو روش براي سازماندهي داده ها بر روي ديسک وجود دارد :

۱) بر اساس سکتور
۲) بر اساس بلوک هاي تعريف شده توسط کاربر
کلاستر عبارت از تعداد ثابتي از سکتورهاي پيوسته است.

مديريت فايل براي در نظر گرفتن فايل به عنوان مجموعه اي از کلاسترها و در عين حال حفظ حالت سکتوري ،سکتورهاي منطقي را به کلاسترهاي فيزيکي که به آنها تعلق دارد ،به وسيله جدول تخصيص فايل (FAT) ارتباط مي دهد.
اگر فضاي زيادي روي ديسک باشد ، ممکن است بتوان کاري کرد که فايل به طور کامل از کلاسترهاي پيوسته تشکيل شود. در چنين موردي گفته مي شود که فايل حاوي يک حد (extent) است.
اتلاف فضا در داخل يک سکتور را پراکندگي داخلي مي نامند. سازماندهي بلوک ها مشکلات پوشايي سکتورها و پراکندگي را ندارد ،زيرا اندازه بلاک ها مي تواند تغيير کند تا سازماندهي منطقي داده ها امکان پذير شود.
بلوک معمولاً طوري سازماندهي مي شود که تعداد مناسبي از رکوردهاي منطقي را نگهداري کند. براي اشاره به تعداد رکوردهايي که قرار است در هر يک از بلاک هاي فايل نگهداري شوند ،از اصطلاح ضريب بلوک بندي استفاده مي شود.
در الگوهاي آدرس دهي بلاکي هر بلوک از داده ها معمولاً با يک يا چند زير بلوک (subblock) همراه است که حاوي اطلاعات اضافي راجع به بلوک داده ها است. معمولاً يک زيربلوک شمارشي وجود دارد که تعداد بايت هاي موجود در بلوک مربوط را نگه مي دارد. همچنين ممکن است که يک زيربلوک کليد ،حاوي کليد مربوط به آخرين رکورد در بلوک داده ها باشد.
هم بلاک ها و هم سکتورها نيازمند آنند که مقدار معيني از فضاي ديسک را به شکل سربار غير داده اي اشغال کنند. بخشي از اين سربار از اطلاعاتي تشکيل مي شود که طي فرمت کردن ،بر روي ديسک نگهداري مي شود. فرمت کردن ،پيش از آنکه ديسک بتواند مورد استفاده قرار گيرد ،صورت مي پذيرد.
فرمت کردن موجب مي شود تا شکاف (gap) و علامت هاي هم زمان سازي ،بين فيلدهاي اطلاعاتي قرار داده شود تا مکانيزم خواندن/نوشتن ، بين آنها تمايز قائل شود.
دستيابي به ديسک را مي توان به سه عمل فيزيکي متمايز تقسيم کرد که هر يک هزينه خود را دارد :
۱) زمان پيگرد (seek time)

۲) تأخير چرخشي (rotational delay)


۳) زمان انتقال (transfer time)
زمان پيگرد عبارت است از زمان لازم انتقال بازوي دستيابي ،به سيلندر مناسب.

تأخير در چرخش عبارت است از زمان لازم براي چرخش ديسک ،تا سکتور مورد نظر زير هد خواندن/نوشتن قرار گيرد.
یک مشکل:
علي رغم افزايش کارايي ديسک ها ،سرعت شبکه ها به حدي بالا رفته است که دستيابي به ديسک غالباً تنگناي مهمي در کل سيستم I/O به شمار مي رود.

چند تکنيک براي مقابله با اين مشکل وجود دارد :

۱) نواربندي
۲) استفاده از ديسک RAM
۳) حافظه نهان


نوارهاي مغناطيسي به دستگاه هايي تعلق دارند که دستيابي مستقيم به داده ها را فراهم نمي آورند ولي دستيابي ترتيبي به سرعت انجام مي شود. نوارها فشرده اند ،شرايط محيطي متفاوت را خوب تحمل مي کنند،نگهداري و حمل آنها آسان است و ارزانتر از ديسک ها هستند.

نقاط قوت CD-ROM شامل ظرفيت ذخيره سازي بالا،بهاي کم و دوام آن است. نقطه ضعف اصلي آن اين است که جستجو در CD-ROM بسيار کند است،يعني غالباً هر جستجو نيم تا يک ثانيه طول مي کشد.

در قالب سرعت خطي ثابت (CLV) ،سرعت چرخش ديسک هنگام خواندن لبه هاي بيروني ،کندتر از هنگام خواندن لبه هاي داخلي است.

در سرعت زاويه اي ثابت (CAV) ،ديسک با شيارهاي متحدالمرکز و سکتورهاي مدور خود ،داده ها را با تراکم کمتري در شيارهاي خارجي نسبت به شيارهاي داخلي مي نويسد.
بافر I/O سيستم ،به مديريت فايل اين امکان را مي دهد تا داده ها را در واحدهايي به اندازه سکتور يا بلوک بخواند يا بنويسد.

عمل کنترل عمليات ديسک توسط دستگاهي انجام مي شود که کنترلگر ديسک ناميده مي شود.

سيستم هاي I/O تقريباً هميشه حداقل دو بافر دارند. يکي براي ورودي و ديگري براي خروجي. برخي سيستم هاي فايل از يک طرح بافردهي موسوم به استخر بافري (buffer spooling) استفاده مي کنند.

با پراکنش ورودي ،با يک بار خواندن ،نه يک بار بافر بلکه مجموعه اي از بافرهايي که داده هاي يک بلوک بايد در آن ها پخش شود شناسايي مي شود.

با تمرکز خروجي ،چند بافر را مي توان گردهم آورد و يکباره بر روي همه آنها نوشت ،بدين ترتيب لازم نيست آنها را در يک بافر خروجي کپي کرد.

هسته به نوبت به اين چهار جدول زير مراجعه مي کند تا اطلاعاتي را که براي نوشتن در فايل موجود در ديسک نياز دارد به دست آورد :


۱) جدول توصيف گر فايل
۲) جدول فايل هاي باز
۳) جدول تخصيص فايل
۴) جدول گره هاي انديسي

اشاره گري از يک فهرست به اينود فايل را اتصال سخت (hard link) مي نامند و اتصال نرم (soft link) يا اتصال سمبوليک ، نام فايل را به جاي فايل واقعي ،به يک نام فايل ديگر مرتبط مي سازد.

سه نوع سيستم I/O متفاوت داريم :

۱) سيستم I/O بلوکي
۲) سيستم I/O کاراکتري
۳) سيستم I/O شبکه اي

براي هر دستگاه جانبي مجموعه اي از روال هاي جداگانه وجود دارد که راه انداز دستگاه ناميده مي شود.

قسمت سوم

1-مفاهيم اساسي ساختار فايل
واحد اصلي داده ها،فيلد است که حاوي يک مقدار داده است.

فيلدها به صورت مجموعه اي از داده ها يا به صورت کپي هاي متعددي از يک فيلد (آرايه) يا ليستي از فيلدهاي متفاوت (رکورد)سازماندهي مي شوند.

هنگامي که رکوردي در حافظه نگهداري شد آن را يک شيء و فيلدهاي آن را اعضاي آن مي نامند.

هنگامي که رکوردي در حافظه نگهداري شد آن را يک شيء و فيلدهاي آن را اعضاي آن مي نامند.

راههاي فراواني براي افزودن ساختار به فايل وجود دارد تا هويت فيلد حفظ شود.
چهار روش متداول عبارتند از :

۱) ثابت کردن طول فيلدها
۲) قرار دادن نشانگر طول فيلد در ابتداي هر فيلد
۳) جدا کردن فيلدها با فاصل
۴) استفاده از عبارت کليدي براي شناسايي فيلدها

رکورد مجموعه اي از فيلد ها است و مجموعه اي از رکوردها فايل را نشان مي دهند.

بعضي از روش هاي سازماندهي رکوردهاي فايل عبارتند از :

۱) قابل پيش بيني کردن طول رکوردها بر حسب بايت
۲) قابل پيش بيني کردن طول رکوردها بر حسب فيلدها
۳) شروع هر رکورد با نشانگر طول
۴) استفاده از انديس براي نگهداري آدرس ها
۵) قرار دادن فاصل در انتهاي هر رکورد

دو روش براي نمايش طول رکورد وجود دارد :

۱) طول رکورد به صورت يک عدد صحيح دو بايتي ، قبل از هر فيلد ديگر رکورد نوشته شود.

۲) تبديل طول به يک کاراکتر رشته اي با استفاده از خروجي فرمت بندي شده

با روبرداري فايل مي توان بايت هاي واقعي نگهداري شده در آن را مشاهده کرد.

++C وراثت را در اختيار قرار مي دهد تا چندين کلاس مي توانند از اعضا و متدهاي مشترک استفاده کنند.


2- قسمت اول مديريت فايلهايي از رکوردها
هنگامي که کارايي جستجوهاي انجام شده در حافظه الکترونيکي را توصيف مي کنيم معمولاً از تعداد مقايسه هاي مورد نياز براي جستجو ،به عنوان واحد کار استفاده مي کنيم.

به طورکلي ،کار مورد نياز براي جستجوي ترتيبي ، در فايلي با n رکورد با n متناسب است :
حداکثر n مقايسه و به طور ميانگين n/2 مقايسه مورد نياز است.

در تحليل و بحث درباره بلوک بندي رکورد چند چيز را بايد مورد توجه قرار داد :

۱) گرچه بلوک بندي مي تواند منجر به بهبود چشمگير کارايي شود ،مرتبه عملکرد جستجوي ترتيبي را تغيير نمي دهد.

۲) بلوک ساري ،اختلاف ميان سرعت دستيابي در حافظه و زمان دستيابي در حافظه ثانويه را نشان مي دهد.

۳) بلوک سازي تعداد مقايسه هايي را که بايد در حافظه انجام شوند ،تغيير نمي دهد و احتمالاً مقدار داده هاي انتقال يافته ميان حافظه و ديسک را افزايش مي دهد.

۴) با بلوک سازي ،در زمان صرفه جويي مي شود زيرا مقدار جستجو کاهش مي يابد.

جستجوي ترتيبي براي اکثر شرايط بازيابي زمان بسيار مي برد.
اين که آيا جستجوي ترتيبي توصيه مي شود يا خير تا حد زيادي به چگونگي استفاده از فايل ،سرعت سيستم عامل در انجام جستجو ،و چگونگي ساختار فايل بستگي دارد.

متداول ترين ساختار فايل که در يونيکس وجود دارد ، يک فايل اسکي با کاراکتر خط جديد به عنوان فاصل رکوردها و در صورت امکان ،فضاي خالي به عنوان فاصل فيلدها است.

روش ديگري که با جستجوي ترتيبي تفاوت بنيادي دارد ، دستيابي مستقيم است.

هنگامي که بتوانيم مستقيماً به ابتداي يک رکورد برويم و آن را به حافظه وارد کنيم ،به آن رکورد دستيابي مستقيم داريم.

قسمت چهارم

غالباً لازم است از برخي اطلاعات عمومي مربوط به فايل آگاه باشيم تا در آينده به استفاده از فايل کمک شود ، رکورد سرآيند غالباً در آغاز فايل قرار داده مي شود تا اين نوع اطلاعات را نگهداري کند.

هر فايل داراي يک رکورد سرآيند (header) است که حاوي سه مقدار در پايين است :

۱) اندازه سرآيند
۲) تعداد رکوردها
۳) اندازه هر رکورد

دو ساختار مختلف از رکوردها که حاوي فيلدهاي طول متغير در يک رکورد با طول ثابت است :

۱) فايل حاوي سرآيند ۳۲ بيتي و دو رکورد طول ثابت است که شامل فيلدهاي طول متغيري است که به NULL ختم مي شوند.

۲) فايل حاوي سرآيند ۶۶ بيتي و رکوردهايي با طول ۶۸ بايت است که با فيلدي دو بايتي شروع مي شوند.

تا کنون عمل نوشتن نيازمند به دو عمل جداگانه بود :

۱) فشرده سازي در يک بافر ۲) نوشتن بافر روي فايل

در اين بخش ،کلاس recordfile را معرفي مي کنيم که نوعي عمل خواندن را پشتيباني مي کند که شيئي از يک کلاس را گرفته، آن را در يک فايل مي نويسد. کاربرد بافرها در داخل کلاس پنهان مي شود.

در بحث هايي که طي اين فصل و فصل قبل داشتيم به موارد زير پرداختيم :

۱)رکوردهاي طول متغير
۲) رکوردهاي طول ثابت
۳) دستيابي ترتيبي
۴) دستيابي مستقيم

دو مورد اول به سازماندهي فايل و دو مورد آخر به دستيابي به فايل مربوط مي شود.

داده هايي مثل صوت ،تصاوير ،و اسناد به صورت فيلدها و رکوردها ذخيره نمي شوند.
اگر در زبان برنامه نويسي امکان داشته باشد، مي توانيم اطلاعات کاربردي بيشتري درباره ساختار فايل در سرآيند قرار دهيم.

هنگامي که سرآيند فايل حاوي اين نوع اطلاعات باشد، گفته مي شود اين فايل ،خود- توصيفگر است.

شبه داده ها را مي توان با هر فايلي همراه ساخت ،که داده هاي اصلي آن نياز به اطلاعات پشتيبان دارد .

تصوير راستر رنگي ،آرايه اي راست گوشه از نقاط رنگي يا پيکسل ها است ،که روي صفحه به نمايش در مي آيند.

انواع متفاوت فراواني از شبه داده ها وجود دارند که مي توانند با يک تصوير همراه شوند ،از جمله :

۱) تعداد بيت هاي به کار رفته در توصيف هرپيکسل

۲) ابعاد تصوير- تعداد پيکسل ها به ازاي هر سطر و تعداد سطرها

۳) يک جدول جستجوي رنگ يا جعبه رنگ (pallet) که نشان مي دهد کدام رنگ بايد به هر مقدار پيکسل در تصوير نسبت داده شود.


متدهايي براي کار با تصاوير به عنوان اشياي خاصي وجود دارد :

۱) نمايش يک تصوير پنجره اي در صفحه نمايش کنسول

۲) همراه کردن يک تصوير با يک جدول جستجوي رنگ خاص

۳) قرار دادن تصويري بر روي يک تصوير ديگر و ايجاد يک تصوير ترکيبي

۴) به نمايش در آوردن پياپي چند تصوير براي انيميشن (animation)

ايده دنبال کردن فايل ها براي قرار دادن دامنه وسيعي از اشياي گوناگون ،اجتناب ناپذير است ،بويژه براي کاربردهايي که نياز به مقدار زيادي از شبه داده ها يا ترکيب غير قابل پيش بيني از انواع متفاوت داده ها دارند ،زيرا به اين ترتيب ديگر لازم نيست رکوردها حتماً از يک نوع باشند.

براي توصيف ديدي که يک برنامه کاربردي از اشياي داده اي دارد ،از اصطلاح مدل داد هاي انتزاعي استفاده نموديم.

اين کار اساساً ديدي کاربردگرا و درون- حافظه اي از اشياء است و در آن از فرمت فيزيکي اشياء به آن صورت که در فايل ها نگهداري مي شود چشم پوشي مي گردد.

يکي از مزاياي استفاده از برچسب ها براي شناسايي اشياي موجود در فايل ها آن است که نيازي نيست که از پيش بدانيم همه اشيايي که نرم افزار با آنها سرو کار خواهد داشت به چه صورت خواهد بود.

اختلاف ميان زبان ها ،سيستم هاي عامل ،و معماري ماشين ،سه مشکل اصلي هستند که هنگام توليد فايل هاي قابل حمل با آن ها مواجهيم.

چند راه حل براي دستيابي به قابليت حمل :

۱) توافق بر سر يک فرمت فيزيکي استاندارد براي رکورد و وفاداري به آن

۲) توافق بر سر رمزگذاري دودويي استاندارد براي عناصر داده اي

۳) تبديل اعداد و متون

۴) تبديل ساختارهاي فايل

قسمت پنجم

سازماندهي فايلها براي کارايي

فشرده سازي يک فرايند دسته اي (batch) است که براي حذف حفره هاي خالي فايلي به کار مي رود که بارها و بارها مورد حذف و بهنگام سازي قرار گرفته است.

دلايل زيادي براي کوچک کردن فايلها وجود دارد :

۱) فايل هاي کوچکتر نياز به حافظه ي کمتري دارند که باعث صرفه جويي مي شود.

۲) سريع تر انتقال داده مي شوند که زمان دسترسي را کوتاهتر مي کند يا به جاي آن مي توان با همان زمان دسترسي از پهناي باند کمتر و ارزان تر استفاده کرد.

۳) به صورت ترتيبي ،سريع تر قابل پردازش هستند.

فشرده سازي داده ها عبارت است از رمزگذاري اطلاعات در فايل ،به صورتي که جاي کمتري بگيرد
تکنيک فشرده سازي که در آن تعداد بيت ها با استفاده از يک نمادگذاري فشرده تر کاهش مي يابد يکي از روش هاي فشرده سازي است که به عنوان کاهش زوايد شناخته مي شوند.

آرايه هاي اسپارس براي نوعي فشرده سازي به نام رمزگذاري طول رانش مناسب اند. ابتدا مقدار خاصي را براي شروع رمزگذاري طول اجرا در يک بايت ذخيره کرده سپس الگوريتم آن را اجرا مي کنيم.

الگوريتم آ رايه هاي اسپارس را به صورت زير اجرا مي کنيم :

۱) پيکسل هاي تشکيل دهنده ي شکل را خوانده آنها به ترتيب در فايل ذخيره کن.

۲) جايي که يک مقدار پيکسل بيش از يک بار پشت سر هم تکرار شود اين سه بايت را به ترتيب جايگزين کن :

الف) نشان دهنده کد طول اجرا
ب ) مقدار پيکسلي که تکرار شده
ج ) تعداد دفعاتي که اين مقدار تکرار شده است.

نوع ديگري از فشرده سازي کدهاي با طول متغير را بسته به تعداد دفعات ظاهر شدن مقادير ، به آن مقادير نسبت مي دهد. به مقاديري که بيشتر تکرار مي شوند کدهاي کوتاهتري نسبت داده مي شود بنابر اين جاي کمتري مي گيرند. کدهاي هافمن مثالي از کدهاي با طول متغير هستند.

راهي ديگر براي صرفه جويي فضا در يک فايل، بازيابي فضا در آن فايل پس از تغيير يافتن فايل است.

تغييرات فايل به سه شکل انجام مي شود :

۱) اضافه کردن رکورد

۲) بهنگام سازي رکورد

۳) حذف رکورد

متراکم کردن فايل از طريق پيدا کردن مکان هايي در فايل که حاوي هيچ داده اي نيستند و از بين بردن اين مکان هاي خالي فايل ها را کوچکتر مي کند. و مکان هاي خالي هم وقتي در فايل ايجاد مي شود که رکوردي را حذف مي کنيم.

متراکم کردن فايل آسان ترين و رايج ترين روش هاي بازيابي فضا است.

به طور کلي براي فراهم کردن مکانيسمي براي حذف رکوردها و به دنبال آن استفاده دوباره از فضاي آزاد شده بايد بتوانيم دو مسئله را تضمين کنيم :

۱) رکوردهاي حذف شده به طور خاصي علامت گذاري شوند.

۲) بتوانيم محلي را که توسط رکوردهاي حذف شده اشغال شده بود پيدا کنيم تا بتوانيم براي اضافه کردن رکوردهاي جديد از اين محل ها استفاده کنيم.

براي بازيابي سريعتر فضا به وارد زير نيازمنديم :

۱) راهي که بلافاصله بدانيم که حفره هاي خالي در فايل وجود دارد يا نه

۲) راهي که اگر چنين حفره اي وجود دارد مستقيماً به آن پرش کنيم.

استفاده از ليست هاي پيوندي براي پيوند دادن تمام رکوردها هر دو نياز فوق را برآورده مي کند.

آسان ترين راه براي کار کردن با ليست استفاده از آن به صورت پشته است.


پشته ليستي است که در آن اضافه و حذف گره ها از يک انتهاي ليست انجام مي شود.

براي بازيابي رکوردها از طريق ليست پيوندي به موارد زير نياز داريم :

۱) راهي براي پيوند دادن رکوردهاي حذف شده و تبديل آنها به يک ليست

۲) الگوريتمي براي اضافه کردن رکوردهاي حذف شده به ليست

۳) الگوريتمي براي پيدا کردن و خارج کردن يک رکورد از ليست هنگامي که مي خواهيم از آن رکورد استفاده کنيم.

براي مقابله با پراکندگي خارجي يک روش متراکم کردن فايل است و دو راه ديگر به قرار زير است:

۱) اگر دو حفره رکورد در ليست به صورت فيزيکي کنار هم قرار گيرند آنها را با هم يکي مي کنيم تا يک حفره رکورد بزرگتر ايجاد شود. به اين کار ادغام حفره ها در فايل ميگوييم.

۲) سعي مي کنيم پراکندگي را به حداقل برسانيم. به اين ترتيب که يک راهبرد انتخاب جا را در نظر مي گيريم که برنامه با استفاده از آن يک حفره رکورد را از ليست انتخاب کند.

هنگامي که نياز داريم يک حفره رکورد را از ليست خارج کنيم با شروع از ابتداي فايل عمل جستجو را انجام مي دهيم تا رکوردي به اندازه کافي بزرگ پيدا کنيم يا به انتهاي ليست برسيم. اين راهبرد انتخاب جا به عنوان راهبرد اولين جاي مناسب( first fit) ناميده مي شود.

سه مشکل اساسي مربوط به مرتب سازي و جستجوي دودويي عبارتند از :

۱) جستجوي دودويي نياز به بيش از يک يا دو دسترسي به ديسک دارد.

۲) نگهداري يک فايل به صورت مرتب شده خيلي گران تمام مي شود.

۳) مرتب سازي داخلي تنها در مورد فايل هاي کوچک عملي است.

مرتب سازي کليدي که گاهي به آن مرتب سازي با برچسب مي گويند بر اين ايده استوار است که وقتي فايلي را در حافظه مرتب مي کنيم تنها چيزيکه واقعاً به آن نياز داريم کليد رکوردها است.

عيب مرتب سازي کليدي اين است که مرتب کردن فايلي با n رکورد نياز به n دستيابي تصادفي به فايل اصلي دارد که مي تواند بسيار بيشتر از خواندن ترتيبي همان تعداد رکورد وقت بگيرد.

[farshidshd]

اگه ممکنه فایل PDF این متن رو هم بذارین خیلی عالی میشه
ممنونم

[bahram_rad]

دوباره یه دونه جزوه ذخیره و بازیابی اطلاعات رو که بصورت دست نویس هستش در اختیار شما قرار میدم

فصل اول

http://gholypur.googlepages.com/zakhireh-f1.pdf

فصل دوم

http://gholypur.googlepages.com/zakhireh-f2-1.pdf

http://gholypur.googlepages.com/zakhirehf2-2.PDF

http://gholypur.googlepages.com/zakhireh-f2-3.pdf

فصل سوم

http://gholypur.googlepages.com/zakhire-f3.PDF

فصل چهارم

http://gholypur.googlepages.com/zakhireh-fasle4.PDF

[shazde]

بهرام جان ممنون

[bahram_rad]

خواهش می کنم دوستان عزیزم هر کاری می کنم تا کمکی به دوستان خوبم انجام دهم

[reza-1365]

با عرض سلام و خسته نباشید خدمت تمام هم رشته ای های عزیز بنده رضا بهرامی راد دانشجوی رشته مهندسی فناوری اطلاعات بعد از مطالعه دروس سیستم عامل و ذخیره و بازیابی اطلاعات متوجه یک خلا بزرگ شدم. بعد از انکه این دروس را خوانده تمرین و مرور می کردم متوجه میشدم که بعضی از تعاریف عمومی وجود دارند که انها را می دانم ولی تعریف جامع و کاملی از انها ندارم لذا سعی کردم مطالعه بیشتری داشته و کتابهای متعددی رو در این زمینه بخونم و اطلاعات جالبی کسب کنم که پیش زمینه ای مناسب برای دروس سیستم عامل و ذخیره و بازیابی اطلاعات باشد لذا از تمام همه رشته هایی عزیز می خواهم در صورت صلاح دید ابتدا این جزوه را بخوانند و سپس اقدام به خواندن دروس ذکر شده کنند. و توصیه میکنم تمام دوستان از رشته های دیگر نیز برای افزایش اطلاعات عمومی و نیز برای درک مفاهیم پایه کامپیوتر که در زندگی امروز بیشتر با ان سر و کار دارند از این جزوه استفاده کنند این جزوه میتواند در درس مبانی کامپیوتر برای رشته کامپیوتر و سایر رشته ها هم استفاده شود.

دوست و هم رشته ای شما : رضا بهرامی راد

این هم دانلود فایل فقط نظراتتون رو به من بگین.
http://www.uplod.ir/download.php?file=475159