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

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

اسلاید 1: 1بسم الله الرحمن الرحیم

اسلاید 2: 2دانشگاه پيام نوردانشكده فناوري اطلاعات

اسلاید 3: 3تعداد واحد: 3تهيه‌كننده: دكتر احمد فراهيساختار فایل ها(ذخیره و بازیابی اطلاعات)ترجمه: مهندس عين ا... جعفرنژاد قمي ابراهيم محرابي

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

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

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

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

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

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

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

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

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

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

اسلاید 14: 14عمليات مهم پردازش فايل

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

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

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

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

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

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

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

اسلاید 22: 22 يونيکس فرمان هاي بسياري براي دستکاري فايل ها دارد که عبارتند از :cat, tail, cp, mv, rm, chmod, ls, mkdir, rmdir

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

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

اسلاید 25: 25 ديسک ها انواع مختلفي دارند :۱) ديسک هاي سخت (hard disks)۲) ديسک هاي فلاپي (floppy disks)۳) کارتريج ديسک ۴) ديسک هاي نوري

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

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

اسلاید 28: 28

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

اسلاید 30: 30

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

اسلاید 32: 32 دو روش براي سازماندهي داده ها بر روي ديسک وجود دارد :۱) بر اساس سکتور۲) بر اساس بلوک هاي تعريف شده توسط کاربر

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

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

اسلاید 35: 35

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

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

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

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

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

اسلاید 41: 41 دستيابي به ديسک را مي توان به سه عمل فيزيکي متمايز تقسيم کرد که هر يک هزينه خود را دارد : ۱) زمان پيگرد (seek time) ۲) تأخير چرخشي (rotational delay) ۳) زمان انتقال (transfer time)

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

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

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

اسلاید 45: 45 علي رغم افزايش کارايي ديسک ها ،سرعت شبکه ها به حدي بالا رفته است که دستيابي به ديسک غالباً تنگناي مهمي در کل سيستم I/O به شمار مي رود. چند تکنيک براي مقابله با اين مشکل وجود دارد : ۱) نواربندي ۲) استفاده از ديسک RAM ۳) حافظه نهان

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

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

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

اسلاید 49: 49

اسلاید 50: 50 بافر I/O سيستم ،به مديريت فايل اين امکان را مي دهد تا داده ها را در واحدهايي به اندازه سکتور يا بلوک بخواند يا بنويسد.

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

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

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

اسلاید 54: 54 هسته به نوبت به اين چهار جدول زير مراجعه مي کند تا اطلاعاتي را که براي نوشتن در فايل موجود در ديسک نياز دارد به دست آورد : ۱) جدول توصيف گر فايل ۲) جدول فايل هاي باز ۳) جدول تخصيص فايل ۴) جدول گره هاي انديسي

اسلاید 55: 55

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

اسلاید 57: 57سه نوع سيستم I/O متفاوت داريم :۱) سيستم I/O بلوکي۲) سيستم I/O کاراکتري۳) سيستم I/O شبکه اي

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

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

اسلاید 60: 60مفاهيم اساسي ساختار فايل

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

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

اسلاید 63: 63 راههاي فراواني براي افزودن ساختار به فايل وجود دارد تا هويت فيلد حفظ شود. چهار روش متداول عبارتند از : ۱) ثابت کردن طول فيلدها ۲) قرار دادن نشانگر طول فيلد در ابتداي هر فيلد ۳) جدا کردن فيلدها با فاصل ۴) استفاده از عبارت کليدي براي شناسايي فيلدها

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

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

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

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

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

اسلاید 69: 69

اسلاید 70: 70مديريت فايلهايي از رکوردها

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

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

اسلاید 73: 73در تحليل و بحث درباره بلوک بندي رکورد چند چيز را بايد مورد توجه قرار داد :۱) گرچه بلوک بندي مي تواند منجر به بهبود چشمگير کارايي شود ،مرتبه عملکرد جستجوي ترتيبي را تغيير نمي دهد.۲) بلوک ساري ،اختلاف ميان سرعت دستيابي در حافظه و زمان دستيابي در حافظه ثانويه را نشان مي دهد.۳) بلوک سازي تعداد مقايسه هايي را که بايد در حافظه انجام شوند ،تغيير نمي دهد و احتمالاً مقدار داده هاي انتقال يافته ميان حافظه و ديسک را افزايش مي دهد.۴) با بلوک سازي ،در زمان صرفه جويي مي شود زيرا مقدار جستجو کاهش مي يابد.

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

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

اسلاید 76: 76روش ديگري که با جستجوي ترتيبي تفاوت بنيادي دارد ، دستيابي مستقيم است. هنگامي که بتوانيم مستقيماً به ابتداي يک رکورد برويم و آن را به حافظه وارد کنيم ،به آن رکورد دستيابي مستقيم داريم.

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

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

اسلاید 79: 79هر فايل داراي يک رکورد سرآيند (header) است که حاوي سه مقدار در پايين است :۱) اندازه سرآيند۲) تعداد رکوردها۳) اندازه هر رکورد

اسلاید 80: 80دو ساختار مختلف از رکوردها که حاوي فيلدهاي طول متغير در يک رکورد با طول ثابت است :۱) فايل حاوي سرآيند ۳۲ بيتي و دو رکورد طول ثابت است که شامل فيلدهاي طول متغيري است که به NULL ختم مي شوند.۲) فايل حاوي سرآيند ۶۶ بيتي و رکوردهايي با طول ۶۸ بايت است که با فيلدي دو بايتي شروع مي شوند.

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

اسلاید 82: 82تا کنون عمل نوشتن نيازمند به دو عمل جداگانه بود :۱) فشرده سازي در يک بافر۲) نوشتن بافر روي فايل

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

اسلاید 84: 84 در بحث هايي که طي اين فصل و فصل قبل داشتيم به موارد زير پرداختيم :۱)رکوردهاي طول متغير۲) رکوردهاي طول ثابت۳) دستيابي ترتيبي۴) دستيابي مستقيم دو مورد اول به سازماندهي فايل و دو مورد آخر به دستيابي به فايل مربوط مي شود.

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

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

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

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

اسلاید 89: 89انواع متفاوت فراواني از شبه داده ها وجود دارند که مي توانند با يک تصوير همراه شوند ،از جمله :۱) تعداد بيت هاي به کار رفته در توصيف هرپيکسل۲) ابعاد تصوير- تعداد پيکسل ها به ازاي هر سطر و تعداد سطرها۳) يک جدول جستجوي رنگ يا جعبه رنگ (pallet) که نشان مي دهد کدام رنگ بايد به هر مقدار پيکسل در تصوير نسبت داده شود.

اسلاید 90: 90متدهايي براي کار با تصاوير به عنوان اشياي خاصي وجود دارد :۱) نمايش يک تصوير پنجره اي در صفحه نمايش کنسول۲) همراه کردن يک تصوير با يک جدول جستجوي رنگ خاص۳) قرار دادن تصويري بر روي يک تصوير ديگر و ايجاد يک تصوير ترکيبي۴) به نمايش در آوردن پياپي چند تصوير براي انيميشن (animation)

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

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

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

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

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

اسلاید 96: 96چند راه حل براي دستيابي به قابليت حمل :۱) توافق بر سر يک فرمت فيزيکي استاندارد براي رکورد و وفاداري به آن۲) توافق بر سر رمزگذاري دودويي استاندارد براي عناصر داده اي۳) تبديل اعداد و متون۴) تبديل ساختارهاي فايل

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

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

اسلاید 99: 99دلايل زيادي براي کوچک کردن فايلها وجود دارد :۱) فايل هاي کوچکتر نياز به حافظه ي کمتري دارند که باعث صرفه جويي مي شود.۲) سريع تر انتقال داده مي شوند که زمان دسترسي را کوتاهتر مي کند يا به جاي آن مي توان با همان زمان دسترسي از پهناي باند کمتر و ارزان تر استفاده کرد.۳) به صورت ترتيبي ،سريع تر قابل پردازش هستند.

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

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

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

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

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

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

اسلاید 106: 106تغييرات فايل به سه شکل انجام مي شود : ۱) اضافه کردن رکورد ۲) بهنگام سازي رکورد ۳) حذف رکورد

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

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

اسلاید 109: 109به طور کلي براي فراهم کردن مکانيسمي براي حذف رکوردها و به دنبال آن استفاده دوباره از فضاي آزاد شده بايد بتوانيم دو مسئله را تضمين کنيم :۱) رکوردهاي حذف شده به طور خاصي علامت گذاري شوند.۲) بتوانيم محلي را که توسط رکوردهاي حذف شده اشغال شده بود پيدا کنيم تا بتوانيم براي اضافه کردن رکوردهاي جديد از اين محل ها استفاده کنيم.

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

اسلاید 111: 111براي بازيابي سريعتر فضا به وارد زير نيازمنديم :۱) راهي که بلافاصله بدانيم که حفره هاي خالي در فايل وجود دارد يا نه۲) راهي که اگر چنين حفره اي وجود دارد مستقيماً به آن پرش کنيم.

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

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

اسلاید 114: 114براي بازيابي رکوردها از طريق ليست پيوندي به موارد زير نياز داريم : ۱) راهي براي پيوند دادن رکوردهاي حذف شده و تبديل آنها به يک ليست ۲) الگوريتمي براي اضافه کردن رکوردهاي حذف شده به ليست ۳) الگوريتمي براي پيدا کردن و خارج کردن يک رکورد از ليست هنگامي که مي خواهيم از آن رکورد استفاده کنيم.

اسلاید 115: 115 براي مقابله با پراکندگي خارجي يک روش متراکم کردن فايل است و دو راه ديگر به قرار زير است: ۱) اگر دو حفره رکورد در ليست به صورت فيزيکي کنار هم قرار گيرند آنها را با هم يکي مي کنيم تا يک حفره رکورد بزرگتر ايجاد شود. به اين کار ادغام حفره ها در فايل ميگوييم. ۲) سعي مي کنيم پراکندگي را به حداقل برسانيم. به اين ترتيب که يک راهبرد انتخاب جا را در نظر مي گيريم که برنامه با استفاده از آن يک حفره رکورد را از ليست انتخاب کند.

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

اسلاید 117: 117 سه مشکل اساسي مربوط به مرتب سازي و جستجوي دودويي عبارتند از : ۱) جستجوي دودويي نياز به بيش از يک يا دو دسترسي به ديسک دارد. ۲) نگهداري يک فايل به صورت مرتب شده خيلي گران تمام مي شود. ۳) مرتب سازي داخلي تنها در مورد فايل هاي کوچک عملي است.

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

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

اسلاید 120: 120شاخص گذاري

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

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

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

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

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

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

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

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

اسلاید 129: 129ساختار شيء شاخص بسيار ساده است. اين ساختار ليستي است که هر عنصر آن دو فيلد دارد: يک فيلد کليد و يک فيلد براي آفست بايت.

اسلاید 130: 130عملياتي که براي يافتن داده هاي مورد نظر ،از طريق شاخص لازمند عبارتند از : ۱) ايجاد فايل داده ها و شاخص خالي اوليه ۲) باز کزدن فايل شاخص در حافظه ،قبل از به کارگيري آن ۳) نوشتن فايل شاخص بر روي ديسک ،پس از به کارگيري آن ۴) افزودن رکوردهايي به فايل و داده ها ۵) حذف رکوردها از فايل داده ها ۶) بهنگام کردن رکوردها در فايل داده ها ۷) بهنگام کردن شاخص براي انعکاس تغييرات به عمل آمده در فايل داده ها.

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

اسلاید 132: 132در ايجاد فايل ها بايد دو فايل ايجاد شوند : ۱) فايل داده ها براي نگهداري اشياي داده اي ۲) فايل شاخص براي نگهداري شاخص کليد اوليه

اسلاید 133: 133بهنگام سازي رکوردها به دو صورت انجام مي شود : ۱) بهنگام سازي ،تعداد فيلد و کليد را تغيير مي دهد. ۲) بهنگام سازي ،در فيلد و کليد تأثير نمي گذارد.

اسلاید 134: 134آشکارترين بهينه سازي ،استفاده از جستجوي دودويي در متد find است که توسط : insert , search و remove به کار گرفته مي شود.

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

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

اسلاید 137: 137هرگاه يک شاخص ساده در حافظه جا نشود بايد از موارد زير استفاده کرد : ۱) در صورتي که سرعت دستيابي در اولويت قرار داشته باشد ،از سازماندهي درهمسازي استفاده شود. ۲) در صورتي که به هر دو نوع دستيابي کليدي و ترتيبي نياز داشته باشيد ،از يک شاخص چند سطحي با ساختار درختي نظير درخت B استفاده شود.

اسلاید 138: 138 شاخص هاي ساده نسبت به استفاده از فايل داده اي که بر حسب کليد مرتب شده اند مزاياي چشمگيري دارد : ۱) شاخص ساده استفاده از جستجوي دودويي را براي دستيابي کليدي به يک رکورد در فايلي که طول رکوردهاي آن متغير است امکان پذير مي سازد. ۲) اگر ورودي هاي شاخص بسيار کوچکتر از رکوردهاي فايل داده ها باشد ،مرتب سازي و نگهداري شاخص نسبت به مرتب سازي و نگهداري فايل داده ها زمان کمتري مي برد. ۳) اگر در فايل داده ها رکوردهايي وجود دارند که در جاي خود مستقر هستند ،با استفاده از شاخص مي توان ترتيب کليدها را بدون جابجايي رکوردهاي داده ها عوض کرد.

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

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

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

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

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

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

اسلاید 145: 145ساختارهاي شاخص ثانويه اي که تا کنون ارائه کرديم دو مشکل دارند :۱) هربارکه رکورد جديدي به فايل افزوده مي شود ،بايد فايل شاخص را دوباره مرتب کنيم ،حتي اگر رکورد جديد به يک کليد ثانويه موجود مربوط باشد.۲) اگر کليدهاي ثانويه وجود داشته باشد ،فيلد کليد ثانويه براي هر ورودي تکرار مي شود. اين کار باعث هدر رفتن فضا مي شود.

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

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

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

اسلاید 149: 149 گرچه روال همخواني بسيار ساده به نظر مي رسد ،براي آن که اين روال بهتر عمل کند به چند نکته بايد توجه داشت : ۱) آماده سازي ۲) دستيابي به عضو بعدي ليست ۳) همزمان سازي ۴) کنترل شرايط پايان فايل ۵) تشخيص خطاها

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

اسلاید 151: 151مرتب سازي در حافظه شامل سه مرحله است : ۱) خواندن کل فايل از روي ديسک به حافظه ۲) مرتب سازي رکوردها با استفاده از يک روال مرتب سازي استاندارد ،مثل مرتب سازي shell ۳) نوشتن دوباره فايل روي ديسک

اسلاید 152: 152 آيا يک الگوريتم مرتب سازي داخلي وجود دارد که به قدر کافي سريع باشد و بتواند مرتب سازي اعداد را بلافاصله پس از خوانده شدن آنها آغاز کند و منتظر قرار گرفتن کل فايل در حافظه نشود؟ بله ،نام آن مرتب سازي هرمي (heapsort) است و مبتني بر همان اصل درخت انتخاب است.

اسلاید 153: 153هرم درختي دودويي با ويژگي هاي زير است :۱) هر گره داراي کليدي است که آن کليد بزگتر يا مساوي کليد واقع در گره پدرش است.۲) يک درخت دودويي کامل است.۳) به خاطر ويژگيهاي ۱ و ۲ ،در نگهداري درخت مي توان آرايه اي اختصاص داد که در آن ،گره ريشه ،انديس ۱ و انديسهاي فرزندان چپ و راست گره i ،به ترتيب برابر با i۲ و ۱ + i۲ باشند.

اسلاید 154: 154

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

اسلاید 156: 156بازيابي ترتيبي کليدها به صورت زير انجام مي شود : ۱) تعيين مقدار کليد موجود در اولين موقعيت هرم . اين مقدار کوچکترين مقدار هرم است. ۲) انتقال بزرگترين مقدار هرم به اولين محل آن و کم کردن يک واحد از تعداد عناصر. ۳) ترتيب دوباره هرم. با اينکار بزرگترين عنصر با فرزند کوچکش جابجا مي شود.هر بار که اين سه مرحله اجرا مي شود ،کوچکتري مقدار بازيابي شده از هرم حذف مي گردد.

اسلاید 157: 157مرتب سازي کليدي دو نارسايي دارد : ۱) هنگاميکه کليدها مرتب سازيمي شوند ،بايد زمان زيادي صرف اين موارد شود. پيگرد هر رکورد در رکوردهاي مرتب شده ،خواندن هر رکورد به حافظه و نوشتن آن روي فايل مرتب شده جديد شود. ۲) در مرتب سازي کليدي ،اندازه فايلي که قابل مرتب سازي است به تعداد جفت کليد/اشاره گري که در حافظه جا شود ،محدود مي شود. در نتيجه هنوز نمي توانيم فايل هاي واقعاً بزرگ را مرتب سازي کنيم.

اسلاید 158: 158رانش داراي ويژگي هاي زير است : ۱) واقعاً قادر به مرتب سازي فايل هاي بزرگ هست و به فايل هايي به هر اندازه قابل بسط است. ۲) خواندن فايل ورودي در مرحله ايجاد رانش ،ترتيبي است و لذا بسيار سرعتر از ورودي است ،زيرا ورودي به ازاي هر رکورد نياز به پيگرد دارد. ۳) خواندن هر رانش طي مرحله ادغام و نوشتن رکوردهاي مرتب شده نيز ترتيبي است. ۴) اگر براي بخشي از ادغام که در حافظه انجام مي شود از مرتب سازي هرمي استفاده شود مي توانيم اين عمليات را با I/O همپوشاني کنيم تا زمان ادغام افزايش پيدا نکند. ۵) چون I/O تا حد زيادي ترتيبي است ،در صورت نياز مي توان براي هر دو عمليات ورودي و خروجي از نوار نيز استفاده کرد.

اسلاید 159: 159I/O چهار بار اجرا مي گردد. در مرحله مرتب سازي : ۱) خواندن همه رکوردها به حافظه براي مرتب سازي و تشکيل رانش ها ۲) نوشتن رانش هاي مرتب شده روي ديسک.در مرحله ادغام : ۱) خواندن رانش هاي مرتب شده به حافظه براي ادغام ۲) نوشتن فايل مرتب شده روي ديسک

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

اسلاید 161: 161 يک اختلاف عمده ميان مرحله مرتب سازي و مرحله ادغام ،در تعداد دستيابي ترتيبي (در مقابل دستيابي مستقيم) است. با استفاده از مرتب سازي هرمي براي ايجاد رانش هايي در مرحله مرتب سازي ،مي توان تضمين نمود که همه I/O ها از يک لحاظ ترتيبي است.

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

اسلاید 163: 163 با بزرگ شدن فايل ها زمان لازم براي مرتب سازي ادغامي به سرعت افزايش مي يابد. براي کاهش اين زمان چند راه وجود دارد : ۱) تخصيص سخت افزار بيشتر نظير ديسک گردان ،حافظه و کانال هاي I/O ۲) اجراي ادغام در بيش از يک مرحله ،کاهش دادن مرتبه هر ادغام و افزايش دادن اندازه بافر براي هر رانش ۳) افزايش طول رانش هاي مرتب شده از لحاظ الگوريتمي ۴) يافتن راههايي براي همپوشاني عمليات I/O

اسلاید 164: 164 در اين بخش سه تغيير ممکن در پيکربندي سيستم را در نظر مي گيريم که مي تواند زمان مرتب سازي را به طور چشمگيري کاهش دهد : ۱) افزايش مقدار حافظه ۲) افزايش تعداد ديسک گردان ها ۳) افزايش تعداد کانال هاي I/O

اسلاید 165: 165

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

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

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

اسلاید 169: 169الگوريتم انتخاب جايگزيني را مي توان به طريق زير پياده سازي نمود : ۱) خواندن مجموعه اي از رکوردها و مرتب سازي آنها با استفاده از مرتب سازي هرمي ۲) به جاي نوشتن کل هرم اوليه به شکل مرتب شده فقط رکوردي را مي نويسيم که کليد آن داراي کمترين مقدار است.

اسلاید 170: 170۳) آوردن يک رکورد جديد و مقايسه مقدار کليد آن با مقدار کليدي که به تازگي در خروجي قرار گفته است.الف) اگر مقدار کليد جديد بزرگتر باشد رکورد جديد را در محل مناسب آن در هرم اوليه ،به همراه رکوردهايي قرار مي دهيم که از خروجي گزينش مي شوند.ب) اگر مقدار کليد رکورد جديد کمتر باشد ،رکورد را در يک هرم ثانويه از رکوردها با مقادير کليدي کمتر از آنهايي که پيش از اين نوشته شده اند قرار مي دهيم.۴) تا هنگاميکه رکوردي در هرم اوليه باقي باشد و رکوردهايي براي خواندن وجود داشته باشد مرحله ۳ را تکرار مي کنيم.

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

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

اسلاید 173: 173 اختصاص دادن بيش از يک پردازنده به يک کار امري است متداول که به حالات زير امکان پذير است : ۱) کامپيوترهاي بزرگ که بسياري از آنها مقدار زيادي از وقت خود را صرف مرتب سازي مي کنند ،معمولاً داراي دو يا چند پردازنده هستند که همزمان روي بخش هاي متفاوت يک مسئله کار مي کنند. ۲) پردازنده هاي برداري و آرايه اي را مي توان طوري برنامه ريزي کرد که انواع گوناگون الگوريتم مرتب سازي را سريعتر از پردازنده هاي اسکالر اجرا کند. ۳) ماشين هاي موازي انبوه ،هزاران و شايد ميليونها پردازنده دارند که مي توانند مستقل از هم کار کنند و در عين حال به شيوه هاي پيچيده با هم ارتباط برقرار کنند. ۴) شبکه هاي محلي بسيار سريع و نرم افزارهاي ارتباطي ،ارسال بخش هاي متفاوتي از يک فرايند به چند ماشين متفاوت را امکان پذير مي سازد.

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

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

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

اسلاید 177: 177 ليست کاملي از مجموعه جديد ابزاهايي که کارايي مرتب سازي خارجي را بهبود مي بخشند شامل موارد زيراست : ۱) براي مرتب سازي درون حافظه اي ،از مرتب سازي هرمي براي تشکيل ليست اوليه عناصر مرتب شده در يک رانش استفاده مي کنيم. ۲) استفاده از حداکثر حافظه ممکن ۳) اگر تعداد رانش هاي اوليه چنان بزرگ باشد که زمان کل پيگرد و چرخش ،بسيار بزگتر از زمان انتقال کل باشد از ادغام چندمرحله اي استفاده مي کنيم. ۴) استفاده از گزينش جايگزيني براي تشکيل رانش هاي اوليه را در نظر بگيريم. ۵) از بيش از يک ديسک گردان و کانال I/O استفاده مي کنيم. ۶) عناصر بنيادي مرتب سازي خارجي و هزينه هاي نسبي آنها را به خاطر مي سپاريم و به دنبال راه هايي براي بهره بردن از معماري ها و سيستمهاي جديد ،نظير پردازش موازي مي گرديم.

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

اسلاید 179: 179 ايده هاي استفاده از الگوريتم هاي ادغام مرتبه بالاتر و ادغام رانش ها از روي يک نوار در چند مرحله مبناي دو روش معروف براي ادغام ،موسوم به ادغام چند مرحله اي يا ادغام آبشاري است. به طور کلي اين ادغام ها در ويژگي هاي زير با هم مشترکند : ۱) توزيع اوليه رانش ها چنان است حداقل ادغام اوليه يک ادغام 1- j جانبه است که در آن j تعداد نوارگردان ها است. ۲) توزيع رانش ها در ميان نوارها چنان است که نوارها غالباً حاوي تعداد متفاوتي از رانش ها هستند.

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

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

اسلاید 182: 182 مشکل اصلي نگهداشتن شاخص در حافظه جانبي اين است که دستيابي به حافظه جانبي کند است. اين مشکل مي تواند به دو مشکل ويژه تقسيم شود : ۱) جستجو بر حسب شاخص بايد سريعتر از جستجوي دودويي باشد. ۲) درج وحذف بايد با سرعت جستجو کردن انجام شود.

اسلاید 183: 183درخت جستجوي دودويي چه اشکالي دارد؟ ۱) براي شاخص بندي روي ديسک سرعت لازم را ندارد. ۲) يک راهبرد مؤثر براي موازنه کردن درخت وجود ندارد.

اسلاید 184: 184 تلاشهايي براي حل مشکلات درخت جستجوي دودويي انجام گرفت که دو تا از آنها عبارتند از : ۱) درخت هاي AVL ۲) درخت هاي دودويي صفحه صفحه

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

اسلاید 186: 186

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

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

اسلاید 189: 189

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

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

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

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

اسلاید 194: 194جستجو در درخت B : ۱) به صورت تکراري عمل مي کنند. ۲) در دو مرحله عمل مي کنند :الف) به صورت يک درميان روي کل صفحاتب) در داخل صفحات

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

اسلاید 196: 196 از مرتبه درخت B به عنوان حداقل تعداد کليدهايي که مي تواند در يک صفحه درخت وجود داشته باشد تعريف مي شود.

اسلاید 197: 197 پايين ترين سطح کليدها در درخت B را برگ مي نامند.

اسلاید 198: 198 با استفاده از تعاريف ارائه شده از مرتبه و برگ ،مي توانيم خواص يک درخت B از مرتبه m را دقيقاً بيان کنيم : ۱) هر صفحه حد اکثر m فرزند دارد. ۲) هر صفحه ،به جز ريشه و برگ ها ،حداقل] [ فرزند دارد. ۳) ريشه حداقل دو فرزند دارد.۴) تمام برگ ها در يک سطح قرار دارد.۵) سطح برگ ها ،يک شاخص کامل و مرتب شده از فايل داده هاي مربوط به درخت را ايجاد مي کند.

اسلاید 199: 199 تضمين اين که درخت پهن و کم عمق باشد ،نه باريک و عميق ،مربوط به اين قوانين است : ۱) هر صفحه به جز ريشه و برگ ها حداقل ] [ فرزند دارد. ۲) هر صفحه حاوي حداقل] [ و حداکثر m کليد است.

اسلاید 200: 200قوانين حذف کليد k از گره n در يک درخت B به اين ترتيبند : ۱) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در nنيست ،کافي است k را از n حذف کنيد. ۲) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در nاست ،k را حذف کنيد و شاخص هاس سطح بالاتر را متناسب با بزرگترين کليد جديد در n تغيير دهيد. ۳) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي n به اندازه کافي خالي است n را در برابرش ادغام کنيد و يک کليد را از گره مادر حذف کنيد. ۴) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي n کليدهاي زيادي دارد ،با انتقال دادن بعضي از کليدها از يک برادر به n ،کليدها را دوباره توزيع کنيد و شاخص هاي سطح بالاتر را متناسب با بزرگترين کليدهاي جديد گره هاي دستکاري شده تغيير دهيد.

اسلاید 201: 201 توزيع دوباره در هنگام درج ،راهي براي جلوگيري يا حداقل به تعويق انداختن ايجاد صفحات جديد است.

اسلاید 202: 202 به جاي تقسيم کردن يک صفحه پر و ايجاد دو صفحه نيمه پر، توزيع دوباره اين امکان را به ما مي دهد که تعدادي از کليدهاي سرريز شده را به صفحه ديگري انتقال دهيم. بنابراين استفاده از توزيع دوباره به جاي تقسيم کردن باعث مي شود که درخت B از فضاي حافظه جانبي به طور مؤثرتر استفاده کند.

اسلاید 203: 203 يک نوع جديد از درخت B را به عنوان درخت B* تعريف مي کنيم که خواص آن به اين ترتيب است : ۱) هر صفحه حداکثر m فرزند دارد. ۲) هر صفحه به جزريشه حداقل فرزند دارد. ۳) ريشه حداقل دو فرزند دارد. ۴) تمام برگ ها در يک سطح قرار دارند.

اسلاید 204: 204 فرايند دستيابي به ديسک براي خواندن صفحه اي که در بافر وجود ندارد، نقص صفحه اي (page fault) ناميده مي شود.

اسلاید 205: 205دو علت براي نقص صفحه وجود دارد : ۱) هيچگاه تا کنون از آن صفحه استفاده نکرده ايم. ۲) آن صفحه قبلاً در بافر بوده است اما صفحه جديدي جايگزين آن شده است.

اسلاید 206: 206 يک راه براي مورد دوم صفحه قبل اين است که صفحه اي را که زودتر از همه مورد استفاده قرار گرفته است جايگزين کنيم ،اين روش جايگزيني ،LRU (List Recently Used) ناميده مي شود.

اسلاید 207: 207 استفاده از رکوردهاي با طول متغير باعث صرفه جويي در فضا و در نتيجه کاهش ارتفاع درخت B مي شود.

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

اسلاید 209: 209دستيابي به فايل هاي ترتيبي شاخص دار و درخت هاي

اسلاید 210: 210 ساختارهاي فايل ترتيبي انديس دار ،امکان انتخاب از ميان دو ديدگاه متفاوت نسبت به فايل را فراهم مي آورند : ۱) شاخص دار : فايل را مي توان به عنوان مجموعه اي از کليدها در نظر گرفت که توسط کليد ،شاخص بندي شده اند. ۲) ترتيبي : به فايل مي توان دستيابي ترتيبي داشت و رکوردها را به ترتيب توسط کليد بازگرداند.

اسلاید 211: 211 مجموعه اي از رکوردها که به طور فيزيکي توسط کليدها مرتب شده اند و رکوردهايي به آن اضافه و يا از آن حذف مي شوند. چنين مجموعه اي از رکوردها را مجموعه ترتيبي مي ناميم.

اسلاید 212: 212هنگاميکه رکوردها را بلوک بندي مي کنيم ، بلوک واحد اصلي ورودي و خروجي مي شود.

اسلاید 213: 213 همانند درخت هاي B ،درج رکوردهاي جديد در يک بلوک مي تواند باعث سرريز شدن بلوک شود.

اسلاید 214: 214 مشکل سرريز شدن را مي توان توسط يک فرايند شکستن بلوک ها کنترل کرد که شبيه فرايند شکستن بلوک ها در درخت هاي B است ،ولي نه دقيقاً همان فرايند.

اسلاید 215: 215 ته ريز شدن در درخت B مي تواند منجر به يکي از دو راه حل زير شود : ۱) اگر يک گره مجاور نيز نيمه پر باشد ،مي توان دو گره را در هم ادغام کرد و يکي از آنها را براي استفاده دوباره آزاد ساخت. ۲) اگر گره هاي مجاور بيش از نيمه پر باشند ،مي توان رکوردها را دوباره ميان گره ها توزيع کرد تا توزيع تقريباً متعادل گردد.

اسلاید 216: 216 مسئله اندازه بلوک به تعيين حدود (limits) اندازه بلوک تبديل مي شود.

اسلاید 217: 217 دو شرطي که در رابطه با حد بالايي اندازه بلوک در نظر مي گيريم عبارت است از : ۱) اندازه بلوک بايد چنان باشد که بتوانيم چندين رکورد را به يکباره در حافظه نگه داريم. ۲) خواندن يا نوشتن يک بلوک نبايد زمان زيادي را صرف کند.

اسلاید 218: 218 ساختار مختلط يک شاخص B بعلاوه يک مجموعه ترتيبي که رکوردها را نگه مي دارد درخت را تشکيل مي دهد.

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

اسلاید 220: 220 محتويات شاخص فقط تا آن حد مورد علاقه ما هستند که بتوانند ما را در رسيدن به بلوک درست در مجموعه ترتيبي رهنمون باشند.

اسلاید 221: 221 با در نظر گرفتن مجموعه شاخص به عنوان يک نقشه راهنما مي توانيم اين گام بسيار مهم را برداريم که : لازم نيست کليدها در شاخص نگهداري شوند. آنچه که واقعاً نياز داريم ،جداکننده ها هستند.

اسلاید 222: 222 شاخص درخت B را مجموعه شاخص مي نامند. اين شاخص به همراه مجموعه ترتيبي ،ساختار فايلي را تشکيل مي دهد که درخت پيشوندي ساده نام دارد.

اسلاید 223: 223 عبارت پيشوندي ساده (simple prefix) نشانگر آن است که مجموعه شاخص حاوي کوتاهترين جداکننده ها يا پيشوندهاي کليدها است نه يک کپي از روي خود کليدهاي واقعي.

اسلاید 224: 224 اگر حذف رکوردها از مجموعه ترتيبي و اضافه کردن رکوردها به آن ،تعداد رکوردها را در مجموعه ترتيبي تغيير دهد ،چه پيش مي آيد؟ واضح است که اگر تعداد بلوک هاي بيشتري داشته باشيم ، به تعداد جداکننده هاي کمتري نياز خواهيم داشت. تغيير دادن تعداد جداکننده ها قطعاً بر مجموعه شاخص تأثير خواهد داشت ، زيرا جداکننده ها در آنجا نگهداري مي شوند.

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

اسلاید 226: 226 درج و حذف رکوردها همواره در مجموعه ترتيبي رخ مي دهد ،زيرا رکوردها در آنجا قرار دارند.

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

اسلاید 228: 228 پس از کامل شدن عمليات مربوط به رکورد در مجموعه ترتيبي تغييرات مورد نياز در مجموعه شاخص را اعمال کنيد : ۱) اگر بلوک ها در مجموعه ترتيبي شکافته شوند ،يک خط جداکننده جديد بايد در مجموعه شاخص درج گردد. ۲) اگر بلوک ها در مجموعه ترتيبي ادغام شوند ،يک جداکننده بايد از مجموعه شاخص حذف گردند. ۳) اگر رکوردها بين بلوک ها در مجموعه ترتيبي دوباره توزيع شوند ،مقدار يک جداکننده در مجموعه شاخص بايد تغيير يابد.

اسلاید 229: 229 چند دليل براي استفاده از ا ندازه بلوک مشترک ميان مجموعه هاي ترتيبي و انديسي وجود دارد : ۱) معمولا از آن رو براي مجموعه شاخص از اندازه بلوک مجموعه ترتيبي استفاده مي شود که تطابق خوبي ميان اندازه بلوک ،ويژگيهاي ديسک گردان ،ومقدار حافظه در دسترس وجود دارد. ۲) با اندازه بلوک مشترک پياده سازي يک الگوي بافردهي براي ايجاد درخت پيشوندي ساده مجازي ،مشابه درختهاي B مجازي آسان تر مي گردد. ۳) بلوک هاي مجموعه ترتيبي و بلوک هاي مجموعه شاخص غالباً در يک فايل قرار داده مي شوند تا از جستجو ميان دو فايل جداگانه در هنگام دستيابي به درخت پيشوندي ساده پرهيز شود.

اسلاید 230: 230 علاوه بر بردار جداکننده ها ،شاخص اين جداکننده ها و ليست شماره هاي بلوک مربوط ،ساختار بلوک مجموعه شاخص شامل موارد زير مي شود : ۱) تعداد جداکننده ها ۲) طول کل جداکننده ها

اسلاید 231: 231فرايند بارگذاري بسيار سريع پيش مي رود زيرا : ۱) خروجي را مي توان به طور ترتيبي نوشت. ۲) بجاي چندين بار گذر مربوط به عمليات درج ،فقط يک بار از داده ها گذر مي کنيم. ۳) با پيشرفت کار نيازي به سازماندهي دوباره بلوک ها نيست.

اسلاید 232: 232 تفاوت ميان درخت پيشوندي ساده و درخت آن است که از پيشوندهايي به عنوان جداکننده استفاده نمي کند. در عوض جداکننده ها در مجموعه انديس ،صرفاً يک کپي از کليدهاي واقعي اند.

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

اسلاید 234: 234 دو عامل وجود دارد که ممکن است وضعيت را به نفع درخت که در آن ،کپي کاملي از کليدها به عنوان جدا کننده بکار گرفته مي شود ،تغيير دهد : ۱) دليل استفاده از کوتاهترين جداکننده ها ،فشرده سازي هرچه بيشتر آنها در يک بلوک از مجموعه شاخص است. ۲) برخي مجموعه هاي کليدي ،هنگام استفاده از روش پيشوندي ساده براي ايجاد جداکننده ها ،فشرده سازي چنداني از خود نشان نمي دهند.

اسلاید 235: 235درخت B ، درخت پيشوندي ساده و درخت در خصوصيات زير مشترکند : ۱) همگي ساختارهاي شاخص صفحه اي هستند ،يعني کل اطلاعات موجود در بلوک را يکباره به حافظه منتقل مي کنند. ۲) در هر سه روش ، درختهايي نگهداري مي شود که ارتفاع آنها وازنه است. ۳) در همه موارد ،درختها از پايين به بالا رشد مي کنند و موازنه از طريق شکستن بلوک ،ادغام و توزيع دوباره حفظ مي شود. ۴) با هر سه ساختار مي توان از طريق استفاده از شکافتگي دو به سه و در صورت امکان ،توزيع دوباره به جاي شکستن بلوک ،بازدهي را بالا برد. ۵) هر سه روش را مي توان به عنوان ساختارهاي درختي مجازي پياده سازي کرد که در آن ،آخرين بلوک هاي استفاده شده ،در حافظه نگهداري مي شوند. ۶) هر يک از اين سه روش را مي توان با استفاده از ساختارهاي موجود در بلوک با رکوردهاي طول متغير به کار برد.

اسلاید 236: 236ساختار درخت سه مزيت مهم ير درخت B دارد: ۱) مجموعه ترتيبي را مي توان به شيوه اي واقعاً خطي و ترتيبي پردازش کرد و در نتيجه به ترتيب کليدها به رکوردها دستيابي مؤثري داشت. ۲) شاخص با يک کليد منفرد يا جداکننده به ازاي هر بلوک از رکوردهاي داده ها به جاي يک کليد (به ازاي هر رکورد از داده ها) ساخته مي شود.

اسلاید 237: 237درهم سازي

اسلاید 238: 238 دستيابي O(1) به فايل به اين معنا است که مهم نيست فايل تا چه اندازه بزرگ مي شود ،بلکه دستيابي به يک رکورد هميشه به تعداد کم و ثابتي پيگرد نياز دارد. در مقابل اين نوع دستيابي ، دستيابي O(N) قرار دارد که از جستجوهاي ترتيبي حاصل مي شود و هرچه اندازه فايل بزرگتر شود تعداد پيگردها نيز بيشتر مي شود.

اسلاید 239: 239 تابع درهم سازي مانند يک جعبه سياه است که هرگاه کليدي در داخل آن انداخته مي شود ،يک آدرس ارئه مي دهد. به بيان رسمي تر ،درهم سازي ،تابع h(K) است که کليد k را به يک آدرس انتقال مي دهد.

اسلاید 240: 240درهم سازي را تصادفي کردن نيز مي گويند. درهم سازي ،از اين نظر که يک کليد به يک آدرس وابسته مي شود ،شبيه انديس سازي است.

اسلاید 241: 241درهم سازي و انديس سازي از دو جهت با هم تفاوت دارند : ۱) آدرس هايي که از درهم سازي به دست مي آيند به صورت تصادفي اند. ۲) با درهم سازي ،دو کليد مختلف ممکن است به يک آدرس انتقال داده شوند.

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

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

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

اسلاید 245: 245 چندين راه مختلف براي کاهش تعداد برخوردها وجود دارد که بعضي از آنها عبارتند از : ۱) پراکنده کردن رکوردها ۲) استفاده از حافظه اضافي ۳) قرار دادن بيش از يک رکورد در يک آدرس

اسلاید 246: 246 به آدرس هايي که مي توانند چندين رکورد را نگهداري کنند باکت مي گويند.

اسلاید 247: 247 در اين فصل يک الگوريتم درهم سازي ساده نوشته تا انواع اعمالي را که در الگوريتم درهم سازي انجام مي شوند نشان دهد که اين الگوريم سه مرحله دارد که عبارتند از : ۱) نمايش کليد به شکل عددي ۲) تا کردن و اضافه کردن ۳) تقسيم کردن بر يک عدد اول و استفاده از باقيمانده به عنوان آدرس

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

اسلاید 249: 249

اسلاید 250: 250 بعضي از روشهايي که به صورت بالقوه بهتر از درهم سازي هستند نام مي بريم: ۱) جستجو در کليدها براي يافتن يک الگو ۲) تا کردن قسمتهايي از کليد ۳) تقسيم يک کليد بر يک عدد ۴) مجذور کردن کليد و گرفتن عدد مياني ۵) تبديل مبنا

اسلاید 251: 251 توزيع پوآسون ابزاري رياضي را براي بررسي اثرات توزيع تصادفي ارائه مي کند. از توابع پوآسون مي توان براي پيش بيني تعداد آدرس هايي که ممکن است به رکوردهاي 0 و1 و2 وغيره نسبت داده شوند استفاده کرد.

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

اسلاید 253: 253 اگر جستجو براي يافتن رکورد آغاز شود اما رکورد در فايل ذخيره نشده باشد چه اتفاقي مي افتد؟جستجو از آدرس خانگي رکورد آغاز مي شود و اين جستجو در آدرس هاي بعدي نيز ادامه پيدا مي کند. دو اتفاق ممکن است رخ دهد :۱) اگر با يک فضاي خالي مواجه شود ،جستجوگر ممکن است فرض کند که فضاي خالي به اين معنا است که رکورد در فايل موجود نيست.۲) اگر فايل پر باشد ،جستجو ادامه پيدا مي کند تا به جايي مي رسد که جستجو ،از آنجا شروع شده بود و مشخص مي شود که رکورد در فايل موجود نيست.

اسلاید 254: 254 منظور از طول جستجو ،تعداد دستيابي هاي لازم براي بازيابي يک رکورد از حافظه ثانويه است.

اسلاید 255: 255

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

اسلاید 257: 257 براي محاسبه دانسيته فشردگي فايل بايد هم به تعداد آدرس ها (باکت ها) و هم به تعداد رکوردهايي که مي توان در هر آدرس قرار داد توجه کرد(اندازه باکت).

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

اسلاید 259: 259 به عنوان يک اصل معمولاً استفاده از باکت هاي بزرگتر از شيار ،ايده خوبي نيست(مگر در مواردي که رکوردها خيلي بزرگ باشند).

اسلاید 260: 260 فايلهاي درهم سازي به دو روش با فايلهايي که تا کنون مورد بررسي قرار گرفته ان متفاوتند : ۱) چوت تابع درهم سازي ،بر اساس تعداد ثابتي از آدرس هاي موجود بنا نهاده شده است ،اندازه منطقي فايل درهم سازي شده بايد از قبل مشخص باشد و همچنين ،وقتي اين تابع بر روي فايل عمل مي کند ،طول فايل ثابت باقي بماند. ۲) چون شماره رکورد نسبي (RRN) خانگي هر رکورد در فايل درهم سازي شده ،نسبت به کليدش منحصر به فرد است ،هر روالي که يک رکورد را اضافه يا حذف کند و يا تغيير دهد ،بايد طوري عمل کند که پيوند بين رکورد و آدرس خانگي آن را از بين نبرد.

اسلاید 261: 261 تنها تفاوت بين فايل هايي که باکت دارند و فايل هايي که تنها مي توانند يک رکورد را در خود جاي دهند اين است که در فايل هاي باکت دار ، هر آدرس ،فضاي کافي براي ذخيره سازي بيش از يک رکورد منطقي را دارد.

اسلاید 262: 262 به دو دليل حذف کردن يک رکورد از فايل درهم سازي شده پيچيده تر از اضافه کردن رکورد است : ۱) محلي از فايل که در اثر حذف کردن آزاد شده است ،نبايد مانع جستجوهاي بعدي شود. ۲) بايد امکان استفاده مجدد از فضاهاي آزاد شده ،در اضافه کردن هاي بعدي وجود داشته باشد.

اسلاید 263: 263 خوبي علائم ويژه اين است که ،دو مشکلي را که درقبل آن اشاره شد حل مي کند : ۱) فضاي آزاد شده مانع جستجوي متوالي رکورد نمي شود. ۲) مسلماً مي توان از اين فضاي آزاد شده براي ذخيره رکوردهاي بعدي استفاده کرد.

اسلاید 264: 264 چون رکوردهاي سرريز ،تأثير بسزايي در کارايي دارند تکنيک هاي زيادي براي جلوگيري از برخوردها پيشنهاد شده اند: ۱) درهم سازي دوگانه ۲) سرريز فزاينده زنجيره اي ۳) پيوند با ناحيه سرريز ديگر ۴) جدول هاي پراکندگي

اسلاید 265: 265درهم سازي قابل توسعه

اسلاید 266: 266 ويژگي مهم در درخت AVL و درخت B آن است که اين ساختارها خود تنظيم هستند و شامل مکانيسم هايي اند که خود را نگهداري مي کنند.

اسلاید 267: 267 ايده کليدي در فرايند درهم سازي قابل توسعه ،ترکيب کردن درهم سازي معمولي با يک روش بازيابي ديگر موسوم به تراي trie)) است. تراي ها را جستجوي مبنا نيز مي نامند زيرا ضريب انشعاب درخت جستجو برابر با تعداد نماهاي مختلف است که ممکن است در هر موقعيت از کليد ظاهر شوند.

اسلاید 268: 268 اگر رکوردي اضافه کنيم وجايي براي آن در باکت وجود نداشته باشد ،باکت را مي شکافيم.

اسلاید 269: 269 هدف از سيستم درهم سازي قابل توسعه ،يافتن راهي براي افزايش فضاي آدرس ،در پاسخ به سرريز شدن است نه پاسخ دهي با ايجاد رشته اي بلند از رکوردهاي سرريز و باکت هايي که بايد به طور خطي جستجو شوند.

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

اسلاید 271: 271 حذف ،عکس فرايند اضافه کردن است ،با ذکر اين نکته که فقط در صورتي مي توان رکوردهاي دو باکت را با هم ترکيب کرد که دو باکت با هم دوست باشند يعني اين دو باکت از شکافتن يک باکت نتيجه شده باشند.

اسلاید 272: 272 عمل تنزل شامل تخصيص فضا به آرايه جديدي از آدرس هاي باکت است که اندازه آن نصف اندازه اوليه است و سپس آدرس هاي باکت مشترک در هر جفت سلول را به يک سلول واحد در فهرست راهنماي جديد کپي مي کند.

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

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