مقالات و جزوه های درسی رشته کامپیوتر

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

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

 با استفاده از مرتب سازي هرمي براي ايجاد رانش هايي در مرحله مرتب سازي ،مي توان تضمين نمود که همه 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 اعمال مي شود.