ذخیره و بازیابی اطلاعات جلسه چهارم
• ادامه مبحث سازماندهي فايلها براي
کارايي
• شاخص گذاري
براي
بازيابي سريعتر فضا به وارد زير نيازمنديم :
۱)
راهي که بلافاصله بدانيم که حفره هاي خالي در فايل وجود دارد يا نه
۲)
راهي که اگر چنين حفره اي وجود دارد مستقيماً به آن پرش کنيم.
استفاده
از ليست هاي پيوندي براي پيوند دادن تمام رکوردها هر دو نياز فوق را
برآورده مي کند.
آسان
ترين راه براي کار کردن با ليست استفاده از آن به صورت پشته است.
پشته ليستي است که در آن اضافه و حذف گره
ها از يک انتهاي ليست انجام مي شود.
براي
بازيابي رکوردها از طريق ليست پيوندي به موارد زير نياز داريم :
۱) راهي براي پيوند دادن رکوردهاي حذف شده و
تبديل آنها به يک ليست
۲) الگوريتمي براي اضافه کردن رکوردهاي حذف شده
به ليست
۳) الگوريتمي براي پيدا کردن و خارج کردن يک
رکورد از ليست هنگامي که مي خواهيم از آن رکورد استفاده کنيم.
براي مقابله با پراکندگي خارجي يک روش متراکم
کردن فايل است و دو راه ديگر به قرار زير است:
۱) اگر دو حفره رکورد در ليست به صورت فيزيکي کنار هم قرار
گيرند آنها را با هم يکي مي کنيم تا يک حفره رکورد بزرگتر ايجاد شود. به اين کار ادغام
حفره ها در فايل ميگوييم.
۲) سعي مي کنيم پراکندگي را به حداقل برسانيم.
به اين ترتيب که يک راهبرد انتخاب جا را در نظر مي گيريم که برنامه با استفاده از
آن يک حفره رکورد را از ليست انتخاب کند.
هنگامي که نياز داريم يک حفره رکورد را
از ليست خارج کنيم با شروع از ابتداي فايل عمل جستجو را انجام مي دهيم تا رکوردي
به اندازه کافي بزرگ پيدا کنيم يا به انتهاي ليست برسيم. اين راهبرد انتخاب جا به عنوان
راهبرد اولين جاي مناسب( first fit)
ناميده مي شود.
سه مشکل اساسي مربوط به مرتب سازي و جستجوي
دودويي عبارتند از :
۱) جستجوي دودويي نياز به بيش از يک يا دو
دسترسي به ديسک دارد.
۲) نگهداري يک فايل به صورت مرتب شده خيلي گران
تمام مي شود.
۳) مرتب سازي داخلي تنها در مورد فايل هاي کوچک
عملي است.
مرتب
سازي کليدي که گاهي به آن مرتب سازي با برچسب مي گويند بر اين ايده
استوار است که وقتي فايلي را در حافظه مرتب مي کنيم تنها چيزيکه واقعاً به آن نياز
داريم کليد رکوردها است.
عيب مرتب
سازي کليدي اين است که مرتب کردن فايلي با n
رکورد نياز به n دستيابي تصادفي به فايل اصلي دارد
که مي تواند بسيار بيشتر از خواندن ترتيبي همان تعداد رکورد وقت بگيرد.
شاخص گذاري
همه شاخص ها بر اساس يک مفهوم اصلي واحد عمل مي
کنند: کليدها و آدرس فيلدها.
انواع شاخص هايي که در اين فصل بررسي مي کنيم شاخص
ساده ناميده مي شوند زيرا با استفاده از آرايه هاي ساده اي از ساختمان ها نشان
داده مي شوند ،که حاوي کليدها و آدرس فيلدها هستند.
چون شاخص ها به طور غير مستقيم عمل مي کنند ،
بدون دستکاري محتويات فايل ،به فايل نظم و ترتيب مي بخشند.
کاتالوگ کارتي در واقع مجموعه اي از سه
شاخص است که هر کدام از يک فيلد کليد متفاوت استفاده مي کنند و همه انها از
يک شماره کاتالوگ يکسان به عنوان فيلد آدرس بهره مي گيرند.
بنابراين کاربرد ديگر شاخص بندي اين است که مي
توان از طريق مسيرهاي گوناگوني به فايل دست يافت.
در جستجوي دودويي لازم است امکان پرش به وسط فايل را داشته
باشيم.
راه
ديگر براي مرتب سازي ، ايجاد شاخص براي فايل است.
ساختار
شيء شاخص بسيار ساده است.
اين
ساختار ليستي است که هر عنصر آن دو فيلد دارد:
يک فيلد کليد و يک فيلد براي آفست بايت.
عملياتي
که براي يافتن داده هاي مورد نظر ،از طريق شاخص لازمند عبارتند از :
۱) ايجاد فايل داده ها و شاخص خالي اوليه
۲) باز کزدن فايل شاخص در حافظه ،قبل از به
کارگيري آن
۳) نوشتن فايل شاخص بر روي ديسک ،پس از به
کارگيري آن
۴) افزودن رکوردهايي به فايل و داده ها
۵) حذف رکوردها از فايل داده ها
۶) بهنگام کردن رکوردها در فايل داده ها
۷) بهنگام کردن شاخص براي انعکاس تغييرات به
عمل آمده در فايل داده ها.
مزيت بزرگي که روش شيء گرا دارد آن است
که براي اجراي اين عمليات به هرچه نياز داشته باشيم مي توانيم در متدهاي کلاس خود
بيابيم.
در
ايجاد فايل ها بايد دو فايل ايجاد شوند :
۱) فايل داده ها براي نگهداري اشياي داده اي
۲) فايل شاخص براي نگهداري شاخص کليد اوليه
بهنگام
سازي رکوردها به دو صورت انجام مي شود :
۱) بهنگام سازي ،تعداد فيلد و کليد را تغيير مي
دهد.
۲) بهنگام سازي ،در فيلد و کليد تأثير نمي
گذارد.
آشکارترين
بهينه سازي ،استفاده از جستجوي دودويي در متد find است که توسط :
insert , search و remove به کار گرفته مي شود.
منبع ديگر بهينه سازي ،چنانچه رکورد شاخص
تغيير نکرده باشد ، نوشتن درباره رکورد شاخص در فايل شاخص است.
دستيابي
به شاخص روي ديسک داراي معايب زير است :
۱) جستجوي دودويي شاخص به جاي آنکه با سرعت
حافظه صورت پذيرد ،نياز به چندين پيگرد دارد.
۲) ترتيب مجدد شاخص که از حذف يا افزودن رکورد
ناشي مي شود نياز به جابه جا کردن يا مرتب سازي رکوردها در حافظه ثانويه
دارد که اين کار ميليونها بار گران تر از اجراي اين عمليات در حافظه است.
هرگاه
يک شاخص ساده در حافظه جا نشود بايد از موارد زير استفاده کرد :
۱) در صورتي که سرعت دستيابي در اولويت قرار
داشته باشد ،از سازماندهي درهمسازي استفاده شود.
۲) در صورتي که به هر دو نوع دستيابي کليدي و
ترتيبي نياز داشته باشيد ،از يک شاخص چند سطحي با ساختار درختي نظير
درخت B استفاده شود.
شاخص هاي ساده نسبت به استفاده از فايل داده
اي که بر حسب کليد مرتب شده اند مزاياي چشمگيري دارد :
۱) شاخص ساده استفاده از جستجوي دودويي را براي
دستيابي کليدي به يک رکورد در فايلي که طول رکوردهاي آن متغير است امکان پذير مي
سازد.
۲) اگر ورودي هاي شاخص بسيار کوچکتر از
رکوردهاي فايل داده ها باشد ،مرتب سازي و نگهداري شاخص نسبت به مرتب سازي و
نگهداري فايل داده ها زمان کمتري مي برد.
۳) اگر در فايل داده ها رکوردهايي وجود دارند
که در جاي خود مستقر هستند ،با استفاده از شاخص مي توان ترتيب کليدها را بدون
جابجايي رکوردهاي داده ها عوض کرد.
هنگاميکه شاخص ثانويه اي موجود باشد
،افزودن يک رکورد به فايل به معناي افزودن يک ورودي شاخص ثانويه است. زمان لازم
برا انجام اين کار بسيار مشابه زمان لازم براي افزودن ورود يي به شاخص اوليه است.
يک اختلاف مهم شاخص ثانويه و شاخص اوليه آن
است که شاخص ثانويه مي تواند حاوي کليدهاي دوگانه باشد.
حذف يک رکورد معمولاً به معناي حذف تمامي آدرس
هاي آن رکورد در سيستم فايل است.
بنابراين حذف رکوردي از فايل داده ها نه تنها
به معناي حذف ورودي مربوط در شاخص اوليه بلکه به معناي حذف همه ورودي هاي
موجود در همه شاخص هاي ثانويه اي است که به اين ورودي از شاخص
اوليه رجوع مي کنند.
مشکل اين است که شاخص هاي ثانويه همانند شاخص
اوليه به ترتيب کليدها نگهداري مي شوند. در نتيجه حذف يک ورودي شامل ترتيب مجدد
ورودي هاي موجود ،به منظور بستن فضاي باقيمانده از حذف است.
بهنگام سا زي فايل داده ها فقط هنگامي شاخص
ثانويه را تحت تأثير قرار مي دهد که کليد اوليه يا ثانويه تغيير يابند. که سه
وضعيت ممکن است پيش بيايد :
۱) بهنگام سازي باعث تغيير کليد ثانويه مي شود.
۲) بهنگام سازي باعث تغيير کليد اوليه مي شود.
۳) بهنگام سازي محدود به فيلدهاي ديگر
ساختارهاي
شاخص ثانويه اي که تا کنون ارائه کرديم دو مشکل دارند :
۱)
هربارکه رکورد جديدي به فايل افزوده مي شود ،بايد فايل شاخص را دوباره مرتب کنيم
،حتي اگر رکورد جديد به يک کليد ثانويه موجود مربوط باشد.
۲) اگر
کليدهاي ثانويه وجود داشته باشد ،فيلد کليد ثانويه براي هر ورودي تکرار مي شود.
اين کار باعث هدر رفتن فضا مي شود.
درسيستم فايلي که طي اين فصل طراحي کرديم ، انقياد
کليدهاي اوليه به آدرس در زمان ايجاد شدن فايل ها رخ مي دهد ولي کليدهاي
ثانويه در زمان استفاده ،به آدرس خود پيوند مي يابند.
پردازش کمک ترتيبي و مرتب سازي فايل هاي بزرگ
عمليات کمک ترتيبي شامل پردازش هماهنگ دو يا
چند ليست ترتيبي براي ايجاد يک ليست خروجي است.
گاهي پردازش منجر به ادغام يا اتحاد
اقلام موجود در ليست هاي خروجي مي شود ،گاهي هدف ،تطابق يا جايگذاري اقلام در ليست
ها است ،گاهي نيز عمليات شامل ترکيبي از تطابق و ادغام مي شود.
اين نوع عمليات روي ليست هاي ترتيبي ،مبناي
بسياري از پردازش هاي فايل ها را تشکيل مي دهند.
گرچه روال همخواني بسيار ساده به نظر مي رسد
،براي آن که اين روال بهتر عمل کند به چند نکته بايد توجه داشت :
۱) آماده سازي
۲) دستيابي به عضو بعدي ليست
۳) همزمان سازي
۴) کنترل شرايط پايان فايل
۵) تشخيص خطاها
اگر قرار باشد تعداد زيادي از ليست ها با هم
ادغام شوند ،مي توان به جاي حلقه مقايسه ها از درخت انتخاب استفاده
کرد.
مرتب
سازي در حافظه شامل سه مرحله است :
۱) خواندن کل فايل از روي ديسک به حافظه
۲) مرتب سازي رکوردها با استفاده از يک روال
مرتب سازي استاندارد ،مثل مرتب سازي shell
۳) نوشتن دوباره فايل روي ديسک
آيا يک الگوريتم مرتب سازي داخلي وجود دارد که
به قدر کافي سريع باشد و بتواند مرتب سازي اعداد را بلافاصله پس از خوانده شدن
آنها آغاز کند و منتظر قرار گرفتن کل فايل در حافظه نشود؟
بله ،نام آن مرتب سازي هرمي (heapsort) است و مبتني بر همان اصل درخت انتخاب است.
هرم
درختي دودويي با ويژگي هاي زير است :
۱) هر
گره داراي کليدي است که آن کليد بزگتر يا مساوي کليد واقع در گره پدرش است.
۲) يک
درخت دودويي کامل است.
۳) به
خاطر ويژگيهاي ۱ و ۲ ،در نگهداري درخت مي توان آرايه اي اختصاص داد که در آن ،گره ريشه ،انديس ۱ و انديسهاي فرزندان چپ و راست
گره i ،به ترتيب برابر با
i۲ و ۱ + i۲ باشند.
الگوريتم مرتب سازي هرمي دو بخش دارد:
ابتدا هرم را ايجاد مي کنيم سپس کليدها را به
صورت مرتب شده در خروجي قرار مي دهيم.
بازيابي
ترتيبي کليدها به صورت زير انجام مي شود :
۱) تعيين مقدار کليد موجود در اولين موقعيت هرم
. اين مقدار کوچکترين مقدار هرم است.
۲) انتقال بزرگترين مقدار هرم به اولين محل آن
و کم کردن يک واحد از تعداد عناصر.
۳) ترتيب دوباره هرم. با اينکار بزرگترين عنصر با فرزند
کوچکش جابجا مي شود.
هر بار
که اين سه مرحله اجرا مي شود ،کوچکتري مقدار بازيابي شده از هرم حذف مي گردد.
مرتب
سازي کليدي دو نارسايي دارد :
۱) هنگاميکه کليدها مرتب سازيمي شوند ،بايد
زمان زيادي صرف اين موارد شود. پيگرد هر رکورد در رکوردهاي مرتب شده ،خواندن هر
رکورد به حافظه و نوشتن آن روي فايل مرتب شده جديد شود.
۲) در مرتب سازي کليدي ،اندازه فايلي که
قابل مرتب سازي است به تعداد جفت کليد/اشاره گري که در حافظه جا شود ،محدود مي
شود. در نتيجه هنوز نمي توانيم فايل هاي واقعاً بزرگ را مرتب سازي کنيم.
رانش
داراي ويژگي هاي زير است :
۱) واقعاً قادر به مرتب سازي فايل هاي بزرگ هست
و به فايل هايي به هر اندازه قابل بسط است.
۲) خواندن فايل ورودي در مرحله ايجاد
رانش ،ترتيبي است و لذا بسيار سرعتر از ورودي است ،زيرا ورودي به ازاي هر رکورد
نياز به پيگرد دارد.
۳) خواندن هر رانش طي مرحله ادغام و نوشتن رکوردهاي مرتب شده نيز ترتيبي
است.
۴) اگر براي بخشي از ادغام که در حافظه انجام
مي شود از مرتب سازي هرمي استفاده شود مي توانيم اين عمليات را با I/O همپوشاني کنيم تا زمان ادغام افزايش پيدا نکند.
۵) چون I/O
تا حد زيادي ترتيبي است ،در صورت نياز مي توان براي هر دو عمليات ورودي و خروجي از
نوار نيز استفاده کرد.
I/O چهار بار اجرا مي
گردد.
در
مرحله مرتب سازي :
۱) خواندن همه رکوردها به حافظه براي مرتب سازي و تشکيل
رانش ها
۲) نوشتن رانش هاي مرتب شده روي ديسک.
در
مرحله ادغام :
۱) خواندن رانش هاي مرتب شده به حافظه براي
ادغام
۲) نوشتن فايل مرتب شده روي ديسک