ذخیره و بازیابی اطلاعات جلسه هفتم (جلسه آخر)

- ادامه مبحث درهم سازي

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

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

 

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

 

 ۱) پراکنده کردن رکوردها

 

 ۲) استفاده از حافظه اضافي

 

 ۳) قرار دادن بيش از يک رکورد در يک آدرس

 .....

ادامه نوشته

ذخیره و بازیابی اطلاعات جلسه ششم

ادامه مبحث شاخص بندي چند سطحي و درختهايB

  

جستجو در درخت B :

 

 ۱) به صورت تکراري عمل مي کنند.

 

 ۲) در دو مرحله عمل مي کنند :

 

 

 الف) به صورت يک درميان روي کل صفحات

 

 ب) در داخل صفحات

 در مورد فرايند درج کردن ،تقسيم کردن و ارتقاء ملاحظات زير را در نظر مي گيريم :

 

 ۱) با جستجويي که تا سطح برگ پيش مي رود شروع مي شود.

 

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

 .....

ادامه نوشته

ذخیره و بازیابی اطلاعات جلسه پنجم

جلسه پنجم - ادامه شاخص ها

 يک اختلاف عمده ميان مرحله مرتب سازي و مرحله ادغام ،در تعداد دستيابي ترتيبي (در مقابل دستيابي مستقيم) است.

 با استفاده از مرتب سازي هرمي براي ايجاد رانش هايي در مرحله مرتب سازي ،مي توان تضمين نمود که همه I/O ها از يک لحاظ ترتيبي است.

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

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

 

 ۱) تخصيص سخت افزار بيشتر نظير ديسک گردان ،حافظه و کانال هاي I/O

 

 ۲) اجراي ادغام در بيش از يک مرحله ،کاهش دادن مرتبه هر ادغام و افزايش دادن اندازه بافر براي هر رانش

 

 ۳) افزايش طول رانش هاي مرتب شده از لحاظ الگوريتمي

 

 ۴) يافتن راههايي براي همپوشاني عمليات I/O

 در اين بخش سه تغيير ممکن در پيکربندي سيستم را در نظر مي گيريم که مي تواند زمان مرتب سازي را به طور چشمگيري کاهش دهد :

 

 ۱) افزايش مقدار حافظه

 

 ۲) افزايش تعداد ديسک گردان ها

 

 ۳) افزايش تعداد کانال هاي I/O

 

 

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

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

اساس انتخاب جايگزيني ،اين ايده است :

 

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

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

 

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

 

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

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

 

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

 

 ب) اگر مقدار کليد رکورد جديد کمتر باشد ،رکورد را در يک هرم ثانويه از رکوردها با مقادير کليدي کمتر از آنهايي که پيش از اين نوشته شده اند قرار مي دهيم.

 

۴) تا هنگاميکه رکوردي در هرم اوليه باقي باشد و رکوردهايي براي خواندن وجود داشته باشد مرحله ۳ را تکرار مي کنيم.

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

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

 

 يک بافر ورودي و يک بافر خروجي اختصاص مي دهيم تا بافردهي دوگانه امکان پذير گردد و بقيه حافظه را به تشکيل درخت انتخاب اختصاص دهيم.

 اختصاص دادن بيش از يک پردازنده به يک کار امري است متداول که به حالات زير امکان پذير است :

 

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

 

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

 

 ۳) ماشين هاي موازي انبوه ،هزاران و شايد ميليونها پردازنده دارند که مي توانند مستقل از هم کار کنند و در عين حال به شيوه هاي پيچيده با هم ارتباط برقرار کنند.

 

 ۴) شبکه هاي محلي بسيار سريع و نرم افزارهاي ارتباطي ،ارسال بخش هاي متفاوتي از يک فرايند به چند ماشين متفاوت را امکان پذير مي سازد.

 اگر در سيستمي برنامه نويسي چندگانه امکان پذير باشد زمان کل براي I/O ممکن است طولاني تر باشد ،زيرا کارما بايد منتظر بماند تا کارهاي ديگر نيز I/O خود را انجام دهند.

 

 يکي از دلايل برنامه ريزي چندگانه آن است که به سيستم عامل امکان دهيم تا راههايي براي افزايش بازدهي کل سيستم ،با هم پوشاني پردازش و I/O در ميان امور متفاوت بيابد.

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

 

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

 

 ۲) استفاده از حداکثر حافظه ممکن

 

 ۳) اگر تعداد رانش هاي اوليه چنان بزرگ باشد که زمان کل پيگرد و چرخش ،بسيار بزگتر از زمان انتقال کل باشد از ادغام چندمرحله اي استفاده مي کنيم.

 

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

 

 ۵) از بيش از يک ديسک گردان و کانال I/O استفاده مي کنيم.

 

 ۶) عناصر بنيادي مرتب سازي خارجي و هزينه هاي نسبي آنها را به خاطر مي سپاريم و به دنبال راه هايي براي بهره بردن از معماري ها و سيستمهاي جديد ،نظير پردازش موازي مي گرديم.

 درادغام موازنه شده دوجانبه ،توزيع اوليه بايد روي دو نوارگردان صورت پذيرد و در هر مرحله از ادغام ،به جز آخري خروجي بايد روي دو نوارگردان صورت گيرد.

 

 

 

 اين ادغام ساده ترين الگوريتم ادغام نواري است.

 

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

 

 

به طور کلي اين ادغام ها در ويژگي هاي زير با هم مشترکند :

 

 ۱) توزيع اوليه رانش ها چنان است حداقل ادغام اوليه يک ادغام 1- j جانبه است که در آن j تعداد نوارگردان ها است.

 

 ۲) توزيع رانش ها در ميان نوارها چنان است که نوارها غالباً حاوي تعداد متفاوتي از رانش ها هستند.

 

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

 

 

 

 چون نوارها دستگاه هاي دستيابي مستقيم نيستند براي هر رانش اضافي که بخواهيم ادغام کنيم به يک نوارگردان اضافي نياز داريم.

 

 بنابر اين ديسک ها بهترند.

 

شاخص بندي چند سطحي و درختهاي B

 مشکل اصلي نگهداشتن شاخص در حافظه جانبي اين است که دستيابي به حافظه جانبي کند است.

 

 

 

 اين مشکل مي تواند به دو مشکل ويژه تقسيم شود :

 

 ۱) جستجو بر حسب شاخص بايد سريعتر از جستجوي دودويي باشد.

 ۲) درج وحذف بايد با سرعت جستجو کردن انجام شود.

 

درخت جستجوي دودويي چه اشکالي دارد؟

 

 ۱) براي شاخص بندي روي ديسک سرعت لازم را ندارد.

 

 ۲) يک راهبرد مؤثر براي موازنه کردن درخت وجود ندارد.

 

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

 

 ۱) درخت هاي AVL

 

 ۲) درخت هاي دودويي صفحه صفحه

 

 درخت AVL درختي با ارتفاع موازنه شده است.

 

 يعني اينکه ،اختلاف مجاز ميان هر دو زيردرخت که ريشه مشترکي دارند محدوديت دارد و حداکثر تفاوت مجاز ۱ است.

 

دو مزيت که درخت هاي AVL را با اهميت مي کنند عبارتند از :

 

 ۱) با تعيين کردن حداکثر تفاوت مجاز در ارتفاع هر دو زيردرخت ،درخت هاي AVL حداقل کارايي را در جستجو تضمين مي کنند.

 

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

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

 

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

 مشکل اصلي درخت هاي صفحه اي هنوز هم استفاده از ديسک است.

 

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

 

 اين ويژگي باعث جذابيت درخت B مي شود ،زيرا اکنون درخت هاي B روش استاندارد شاخص سازي هستند و از پايين به بالا ساخته مي شوند و عملياتي نظي درج و حذف ،در حافظه روي گره هاي درخت B اعمال مي شود.

 

ذخیره و بازیابی اطلاعات جلسه چهارم

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

•  شاخص گذاري

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

 

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

 

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

 

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

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

 

 

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

 

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

 

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

 

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

 

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

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

 

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

 

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

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

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

 

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

 

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

 

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

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

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

 

شاخص گذاري

 همه شاخص ها بر اساس يک مفهوم اصلي واحد عمل مي کنند: کليدها و آدرس فيلدها.

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

 چون شاخص ها به طور غير مستقيم عمل مي کنند ، بدون دستکاري محتويات فايل ،به فايل نظم و ترتيب مي بخشند.

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

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

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

 

راه ديگر براي مرتب سازي ، ايجاد شاخص براي فايل است.

 

ساختار شيء شاخص بسيار ساده است.

 

اين ساختار ليستي است که هر عنصر آن دو فيلد دارد:

 

 يک فيلد کليد و يک فيلد براي آفست بايت.

عملياتي که براي يافتن داده هاي مورد نظر ،از طريق شاخص لازمند عبارتند از :

 

 ۱) ايجاد فايل داده ها و شاخص خالي اوليه

 

 ۲) باز کزدن فايل شاخص در حافظه ،قبل از به کارگيري آن

 

 ۳) نوشتن فايل شاخص بر روي ديسک ،پس از به کارگيري آن

 

 ۴) افزودن رکوردهايي به فايل و داده ها

 

 ۵) حذف رکوردها از فايل داده ها

 

 ۶) بهنگام کردن رکوردها در فايل داده ها

 

 ۷) بهنگام کردن شاخص براي انعکاس تغييرات به عمل آمده در فايل داده ها.

 

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

 

در ايجاد فايل ها بايد دو فايل ايجاد شوند :

 

 ۱) فايل داده ها براي نگهداري اشياي داده اي 

 

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

 

بهنگام سازي رکوردها به دو صورت انجام مي شود :

 

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

 

 ۲) بهنگام سازي ،در فيلد و کليد تأثير نمي گذارد.

آشکارترين بهينه سازي ،استفاده از جستجوي دودويي در متد find  است که توسط :

 

 insert , search  و remove به کار گرفته مي شود.

 

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

 

دستيابي به شاخص روي ديسک داراي معايب زير است :

 

 ۱) جستجوي دودويي شاخص به جاي آنکه با سرعت حافظه صورت پذيرد ،نياز به چندين پيگرد دارد.

 

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

 

هرگاه يک شاخص ساده در حافظه جا نشود بايد از موارد زير استفاده کرد :

 

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

 

 ۲) در صورتي که به هر دو نوع دستيابي کليدي و ترتيبي نياز داشته باشيد ،از يک شاخص چند سطحي با ساختار درختي نظير درخت B استفاده شود.

 

 شاخص هاي ساده نسبت به استفاده از فايل داده اي که بر حسب کليد مرتب شده اند مزاياي چشمگيري دارد :

 

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

 

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

 

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

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

 

 يک اختلاف مهم شاخص ثانويه و شاخص اوليه آن است که شاخص ثانويه مي تواند حاوي کليدهاي دوگانه باشد.

 حذف يک رکورد معمولاً به معناي حذف تمامي آدرس هاي آن رکورد در سيستم فايل است.

 

 

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

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

 

 بهنگام سا زي فايل داده ها فقط هنگامي شاخص ثانويه را تحت تأثير قرار مي دهد که کليد اوليه يا ثانويه تغيير يابند. که سه وضعيت ممکن است پيش بيايد :

 

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

 

 ۲) بهنگام سازي باعث تغيير کليد اوليه مي شود.

 ۳) بهنگام سازي محدود به فيلدهاي ديگر

 

ساختارهاي شاخص ثانويه اي که تا کنون ارائه کرديم دو مشکل دارند :

 

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

 

۲) اگر کليدهاي ثانويه وجود داشته باشد ،فيلد کليد ثانويه براي هر ورودي تکرار مي شود. اين کار باعث هدر رفتن فضا مي شود.

 

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

 

پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ

 

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

 

 

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

 

 

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

 گرچه روال همخواني بسيار ساده به نظر مي رسد ،براي آن که اين روال بهتر عمل کند به چند نکته بايد توجه داشت :

 

 ۱) آماده سازي

 ۲) دستيابي به عضو بعدي ليست

 ۳) همزمان سازي

 ۴) کنترل شرايط پايان فايل

 ۵) تشخيص خطاها

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

مرتب سازي در حافظه شامل سه مرحله است :

 ۱) خواندن کل فايل از روي ديسک به حافظه

 ۲) مرتب سازي رکوردها با استفاده از يک روال مرتب سازي استاندارد ،مثل مرتب سازي shell

 ۳) نوشتن دوباره فايل روي ديسک

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

 

 

 بله ،نام آن مرتب سازي هرمي (heapsort) است و مبتني بر همان اصل درخت انتخاب است.

هرم درختي دودويي با ويژگي هاي زير است :

 

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

 

۲) يک درخت دودويي کامل است.

 

۳) به خاطر ويژگيهاي ۱ و ۲ ،در نگهداري درخت مي توان آرايه اي اختصاص داد که در آن ،گره ريشه ،انديس ۱ و انديسهاي فرزندان چپ و راست گره i ،به ترتيب برابر با

 i۲ و ۱ + i۲ باشند.

 

 الگوريتم مرتب سازي هرمي دو بخش دارد:

 

 ابتدا هرم را ايجاد مي کنيم سپس کليدها را به صورت مرتب شده در خروجي قرار مي دهيم.

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

 

 ۱) تعيين مقدار کليد موجود در اولين موقعيت هرم . اين مقدار کوچکترين مقدار هرم است.

 

 ۲) انتقال بزرگترين مقدار هرم به اولين محل آن و کم کردن يک واحد از تعداد عناصر.

 

 ۳) ترتيب دوباره هرم. با اينکار بزرگترين عنصر با فرزند کوچکش جابجا مي شود.

 

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

مرتب سازي کليدي دو نارسايي دارد :

 

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

 

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

رانش داراي ويژگي هاي زير است :

 

 ۱) واقعاً قادر به مرتب سازي فايل هاي بزرگ هست و به فايل هايي به هر اندازه قابل بسط است.

 

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

 

 ۳) خواندن هر رانش طي مرحله ادغام و نوشتن رکوردهاي مرتب شده نيز ترتيبي است.

 

 ۴) اگر براي بخشي از ادغام که در حافظه انجام مي شود از مرتب سازي هرمي استفاده شود مي توانيم اين عمليات را با I/O همپوشاني کنيم تا زمان ادغام افزايش پيدا نکند.

 

 ۵) چون I/O تا حد زيادي ترتيبي است ،در صورت نياز مي توان براي هر دو عمليات ورودي و خروجي از نوار نيز استفاده کرد.

I/O  چهار بار اجرا مي گردد. 

 

در مرحله مرتب سازي :

 

 ۱) خواندن همه رکوردها به حافظه براي مرتب سازي و تشکيل رانش ها

 ۲) نوشتن رانش هاي مرتب شده روي ديسک.

 

در مرحله ادغام :

 

 ۱) خواندن رانش هاي مرتب شده به حافظه براي ادغام

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

 

ذخیره و بازیابی اطلاعات جلسه سوم

ادامه مبحث حافظه جانبي و نرم افزار سيستم

 زمان پيگرد عبارت است از زمان لازم انتقال بازوي دستيابي ،به سيلندر مناسب.

 تأخير در چرخش عبارت است از زمان لازم براي چرخش ديسک ،تا سکتور مورد نظر زير هد خواندن/نوشتن قرار گيرد.

 علي رغم افزايش کارايي ديسک ها ،سرعت شبکه ها به حدي بالا رفته است که دستيابي به ديسک غالباً تنگناي مهمي در کل سيستم 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 شبکه اي

 

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

 

مفاهيم اساسي ساختار فايل

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

 

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

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

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

 

 چهار روش متداول عبارتند از :

 

 ۱) ثابت کردن طول فيلدها

 ۲) قرار دادن نشانگر طول فيلد در ابتداي هر فيلد

 ۳) جدا کردن فيلدها با فاصل

 ۴) استفاده از عبارت کليدي براي شناسايي فيلدها

 

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

 

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

 

۱) قابل پيش بيني کردن طول رکوردها بر حسب بايت

۲) قابل پيش بيني کردن طول رکوردها بر حسب فيلدها

۳) شروع هر رکورد با نشانگر طول

۴) استفاده از انديس براي نگهداري آدرس ها

۵) قرار دادن فاصل در انتهاي هر رکورد

 

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

 

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

 

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

 

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

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

مديريت فايلهايي از رکوردها

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

 به طورکلي ،کار مورد نياز براي جستجوي ترتيبي ، در فايلي با n رکورد با n متناسب است :

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

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

 

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

 

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

 

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

 

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

 

جستجوي ترتيبي براي اکثر شرايط بازيابي زمان بسيار مي برد.

 

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

 

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

 

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

 

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

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

 

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

 

۱) اندازه سرآيند

۲) تعداد رکوردها

۳) اندازه هر رکورد

 

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

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

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

 

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

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

 

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

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

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

 

۱)رکوردهاي طول متغير

۲) رکوردهاي طول ثابت

۳) دستيابي ترتيبي

۴) دستيابي مستقيم

 

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

 

 داده هايي مثل صوت ،تصاوير ،و اسناد به صورت فيلدها و رکوردها ذخيره نمي شوند.

 

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

 

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

 

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

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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

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

 

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

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

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

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

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

 

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

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

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

 

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

 

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

 

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

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

 

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

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

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

 

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

 

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

الف) نشان دهنده کد طول اجرا

ب ) مقدار پيکسلي که تکرار شده 

ج ) تعداد دفعاتي که اين مقدار تکرار شده است.

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

 

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

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

 

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

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

 ۳) حذف رکورد

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

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

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

 

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

 

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

 

 

ذخیره و بازیابی اطلاعات جلسه دوم

ادامه مبحث حافظه جانبي و نرم افزار سيستم

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

 

<>

 

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

 

>>

 

ظرفيت ديسک تابعي از تعداد سيلندرها ،تعدا شيارها به ازاي هر سيلندر و ظرفيت هر شيار است.

دو روش براي سازماندهي داده ها بر روي ديسک وجود دارد :

 

 ۱) بر اساس سکتور

 ۲) بر اساس بلوک هاي تعريف شده توسط کاربر

کلاستر عبارت از تعداد ثابتي از سکتورهاي پيوسته است.

 

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

 اگر فضاي زيادي روي ديسک باشد ، ممکن است بتوان کاري کرد که فايل به طور کامل از کلاسترهاي پيوسته تشکيل شود. در چنين موردي گفته مي شود که فايل حاوي يک حد (extent) است.

 

>>

 

 اتلاف فضا در داخل يک سکتور را پراکندگي داخلي مي نامند. سازماندهي بلوک ها مشکلات پوشايي سکتورها و پراکندگي را ندارد ،زيرا اندازه بلاک ها مي تواند تغيير کند تا سازماندهي منطقي داده ها امکان پذير شود.

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

 در الگوهاي آدرس دهي بلاکي هر بلوک از داده ها معمولاً با يک يا چند زير بلوک (subblock) همراه است که حاوي اطلاعات اضافي راجع به بلوک داده ها است. معمولاً يک زيربلوک شمارشي وجود دارد که تعداد بايت هاي موجود در بلوک مربوط را نگه مي دارد. همچنين ممکن است که يک زيربلوک کليد ،حاوي کليد مربوط به آخرين رکورد در بلوک داده ها باشد.

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

 فرمت کردن موجب مي شود تا شکاف (gap) و علامت هاي هم زمان سازي ،بين فيلدهاي اطلاعاتي قرار داده شود تا مکانيزم خواندن/نوشتن ، بين آنها تمايز قائل شود.

 

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

 

 ۱) زمان پيگرد (seek time)

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

 ۳) زمان انتقال (transfer time)

 

 

ذخیره و بازیابی اطلاعات جلسه اول

فهرست جلسات

جلسه اول: آشنايي با طراحي و مشخصات ساختار فايلها، عمليات مهم پردازش فايل، حافظه جانبي و نرم افزار سيستم

جلسه دوم: ادامه مبحث حافظه جانبي و نرم افزار سيستم

جلسه سوم: ادامه مبحث حافظه جانبي و نرم افزار سيستم

جلسه چهارم: مفاهيم اساسي ساختار فايل، مديريت فايلهايي از رکوردها

جلسه پنجم: ادامه مبحث مديريت فايلهايي از رکوردها

جلسه ششم: ادامه مبحث مديريت فايلهايي از رکوردها، سازماندهي فايلها براي کارايي

جلسه هفتم: ادامه مبحث سازماندهي فايلها براي کارايي، شاخص گذاري

جلسه هشتم: ادامه مبحث شاخص گذاري

جلسه نهم: ادامه مبحث شاخص گذاري، پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ

جلسه دهم: ادامه مبحث پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ 

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

جلسه دوازدهم: ادامه مبحث شاخص بندي چند سطحي و درختهاي B 

جلسه سيزدهم: دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي B+

جلسه چهاردهم: ادامه مبحث دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي B+ ، درهم سازي

جلسه پانزدهم: ادامه مبحث درهم سازي

جلسه شانزدهم: ادامه مبحث درهم سازي، درهم سازي قابل توسعه

 

جلسه اول

آشنايي با طراحي و مشخصات ساختار فايلها

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

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

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

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

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

 

عمليات مهم پردازش فايل

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

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

  هنگامي که شناسه (identifier) فايل منطقي با دستگاه يا فايل فيزيکي ارتباط پيدا کرد ،بايد اعلام کنيم که مي خواهيم با فايل چه کنيم :

 

 ۱) باز کردن يک فايل موجود

 ۲) ايجاد يک فايل جديد و حذف محتويات موجود در    فايل فيزيکي

 

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

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

 

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

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

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

 

cat, tail, cp, mv, rm, chmod, ls, mkdir, rmdir

 

حافظه جانبي و نرم افزار سيستم

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

ديسک ها انواع مختلفي دارند :

 

 ۱) ديسک هاي سخت (hard disks)

 

 ۲) ديسک هاي فلاپي (floppy disks)

 

 ۳) کارتريج ديسک

 

  ۴) ديسک هاي نوري