بخشی از مقاله
ساختار ایندکس
همه شاخص ها بر اساس يک مفهوم اصلي واحد عمل مي کنند: کليدها و آدرس فيلدها.
انواع شاخص هايي که در اين فصل بررسي مي کنيم شاخص ساده ناميده مي شوند زيرا با استفاده از آرايه هاي ساده اي از ساختمان ها نشان داده مي شوند ،که حاوي کليدها و آدرس فيلدها هستند.
چون شاخص ها به طور غير مستقيم عمل مي کنند ، بدون دستکاري محتويات فايل ،به فايل نظم و ترتيب مي بخشند.
کاتالوگ کارتي در واقع مجموعه اي از سه شاخص است که هر کدام از يک فيلد کليد متفاوت استفاده مي کنند و همه انها از يک شماره کاتالوگ يکسان به عنوان فيلد آدرس بهره مي گيرند.
بنابراين کاربرد ديگر شاخص بندي اين است که مي توان از طريق مسيرهاي گوناگوني به فايل دست يافت.
در جستجوي دودويي لازم است امکان پرش به وسط فايل را داشته باشيم.
راه ديگر براي مرتب سازي ، ايجاد شاخص براي فايل است.
ساختار شيء شاخص بسيار ساده است.
اين ساختار ليستي است که هر عنصر آن دو فيلد دارد:
يک فيلد کليد و يک فيلد براي آفست بايت.
عملياتي که براي يافتن داده هاي مورد نظر ،از طريق شاخص لازمند عبارتند از :
۱) ايجاد فايل داده ها و شاخص خالي اوليه
۲) باز کزدن فايل شاخص در حافظه ،قبل از به کارگيري آن
۳) نوشتن فايل شاخص بر روي ديسک ،پس از به کارگيري آن
۴) افزودن رکوردهايي به فايل و داده ها
۵) حذف رکوردها از فايل داده ها
۶) بهنگام کردن رکوردها در فايل داده ها
۷) بهنگام کردن شاخص براي انعکاس تغييرات به عمل آمده در فايل داده ها.
مزيت بزرگي که روش شيء گرا دارد آن است که براي اجراي اين عمليات به هرچه نياز داشته باشيم مي توانيم در متدهاي کلاس خود بيابيم.
در ايجاد فايل ها بايد دو فايل ايجاد شوند :
۱) فايل داده ها براي نگهداري اشياي داده اي
۲) فايل شاخص براي نگهداري شاخص کليد اوليه
بهنگام سازي رکوردها به دو صورت انجام مي شود :
۱) بهنگام سازي ،تعداد فيلد و کليد را تغيير مي دهد.
۲) بهنگام سازي ،در فيلد و کليد تأثير نمي گذارد.
آشکارترين بهينه سازي ،استفاده از جستجوي دودويي در متد find است که توسط :
insert , search و remove به کار گرفته مي شود.
منبع ديگر بهينه سازي ،چنانچه رکورد شاخص تغيير نکرده باشد ، نوشتن درباره رکورد شاخص در فايل شاخص است.
دستيابي به شاخص روي ديسک داراي معايب زير است :
۱) جستجوي دودويي شاخص به جاي آنکه با سرعت حافظه صورت پذيرد ،نياز به چندين پيگرد دارد.
۲) ترتيب مجدد شاخص که از حذف يا افزودن رکورد ناشي مي شود نياز به جابه جا کردن يا مرتب سازي رکوردها در حافظه ثانويه دارد که اين کار ميليونها بار گران تر از اجراي اين عمليات در حافظه است.
هرگاه يک شاخص ساده در حافظه جا نشود بايد از موارد زير استفاده کرد :
۱) در صورتي که سرعت دستيابي در اولويت قرار داشته باشد ،از سازماندهي درهمسازي استفاده شود.
۲) در صورتي که به هر دو نوع دستيابي کليدي و ترتيبي نياز داشته باشيد ،از يک شاخص چند سطحي با ساختار درختي نظير درخت B استفاده شود.
شاخص هاي ساده نسبت به استفاده از فايل داده اي که بر حسب کليد مرتب شده اند مزاياي چشمگيري دارد :
۱) شاخص ساده استفاده از جستجوي دودويي را براي دستيابي کليدي به يک رکورد در فايلي که طول رکوردهاي آن متغير است امکان پذير مي سازد.
۲) اگر ورودي هاي شاخص بسيار کوچکتر از رکوردهاي فايل داده ها باشد ،مرتب سازي و نگهداري شاخص نسبت به مرتب سازي و نگهداري فايل داده ها زمان کمتري مي برد.
۳) اگر در فايل داده ها رکوردهايي وجود دارند که در جاي خود مستقر هستند ،با استفاده از شاخص مي توان ترتيب کليدها را بدون جابجايي رکوردهاي داده ها عوض کرد.
هنگاميکه شاخص ثانويه اي موجود باشد ،افزودن يک رکورد به فايل به معناي افزوده يک ورودي شاخص ثانويه است. زمان لازم برا انجام اين کار بسيار مشابه زمان لازم براي افزودن ورود يي به شاخص اوليه است.
يک اختلاف مهم شاخص ثانويه و شاخص اوليه آن است که شاخص ثانويه مي تواند حاوي کليدهاي دوگانه باشد.
حذف يک رکورد معمولاً به معناي حذف تمامي آدرس هاي آن رکورد در سيستم فايل است.
بنابراين حذف رکوردي از فايل داده ها نه تنها به معناي حذف ورودي مربوط در شاخص اوليه بلکه به معناي حذف همه ورودي هاي موجود در همه شاخص هاي ثانويه اي است که به اين ورودي از شاخص اوليه رجوع مي کنند.
مشکل اين است که شاخص هاي ثانويه همانند شاخص اوليه به ترتيب کليدها نگهداري مي شوند. در نتيجه حذف يک ورودي شامل ترتيب مجدد ورودي هاي موجود ،به منظور بستن فضاي باقيمانده از حذف است.
بهنگام سا زي فايل داده ها فقط هنگامي شاخص ثانويه را تحت تأثير قرار مي دهد که کليد اوليه يا ثانويه تغيير يابند. که سه وضعيت ممکن است پيش بيايد :
۱) بهنگام سازي باعث تغيير کليد ثانويه مي شود.
۲) بهنگام سازي باعث تغيير کليد اوليه مي شود.
۳) بهنگام سازي محدود به فيلدهاي ديگر
ساختارهاي شاخص ثانويه اي که تا کنون ارائه کرديم دو مشکل دارند :
۱) هربارکه رکورد جديدي به فايل افزوده مي شود ،بايد فايل شاخص را دوباره مرتب کنيم ،حتي اگر رکورد جديد به يک کليد ثانويه موجود مربوط باشد.
۲) اگر کليدهاي ثانويه وجود داشته باشد ،فيلد کليد ثانويه براي هر ورودي تکرار مي شود. اين کار باعث هدر رفتن فضا مي شود.
درسيستم فايلي که طي اين فصل طراحي کرديم ، انقياد کليدهاي اوليه به آدرس در زمان ايجاد شدن فايل ها رخ مي دهد ولي کليدهاي ثانويه در زمان استفاده ،به آدرس خود پيوند مي يابند.
شاخص بندي چند سطحي و درختهاي B
مشکل اصلي نگهداشتن شاخص در حافظه جانبي اين است که دستيابي به حافظه جانبي کند است.
اين مشکل مي تواند به دو مشکل ويژه تقسيم شود :
۱) جستجو بر حسب شاخص بايد سريعتر از جستجوي دودويي باشد.
۲) درج وحذف بايد با سرعت جستجو کردن انجام شود.
درخت جستجوي دودويي چه اشکالي دارد؟
۱) براي شاخص بندي روي ديسک سرعت لازم را ندارد.
۲) يک راهبرد مؤثر براي موازنه کردن درخت وجود ندارد.
تلاشهايي براي حل مشکلات درخت جستجوي دودويي انجام گرفت که دو تا از آنها عبارتند از :
۱) درخت هاي AVL
۲) درخت هاي دودويي صفحه صفحه
درخت AVL درختي با ارتفاع موازنه شده است.
يعني اينکه ،اختلاف مجاز ميان هر دو زيردرخت که ريشه مشترکي دارند محدوديت دارد و حداکثر تفاوت مجاز ۱ است.
دو مزيت که درخت هاي AVL را با اهميت مي کنند عبارتند از :
۱) با تعيين کردن حداکثر تفاوت مجاز در ارتفاع هر دو زيردرخت ،درخت هاي AVL حداقل کارايي را در جستجو تضمين مي کنند.
۲) براي اينکه هنگام درج در درخت AVL ،ويژگي خود را حفظ کند ،مستلزم چهار نوع چرخش است.
درخت دودويي صفحه اي ،سعي مي کند با قرار دادن چندين گره دودويي در يک صفحه ديسک ،مشکل را حل کند.
واضح است که تقسيم کردن درخت به چندين صفحه امکان جستجوي سريعتر در حافظه جانبي را فراهم مي کند وبه دست آوردن اطلاعات را سريعتر از هر روش ديگر دستيابي با استفاده از کليد امکان پذير مي کند.
مشکل اصلي درخت هاي صفحه اي هنوز هم استفاده از ديسک است.
درخت هاي B شاخص هاي چند سطحي هستندکه مشکل هزينه خطي درج و حذف کردن را حل مي کنند.
اين ويژگي باعث جذابيت درخت B مي شود ،زيرا اکنون درخت هاي B روش استاندارد شاخص سازي هستند و از پايين به بالا ساخته مي شوند و عملياتي نظي درج و حذف ،در حافظه روي گره هاي درخت B اعمال مي شود.
جستجو در درخت B :
۱) به صورت تکراري عمل مي کنند.
۲) در دو مرحله عمل مي کنند :
الف) به صورت يک درميان روي کل صفحات
ب) در داخل صفحات
در مورد فرايند درج کردن ،تقسيم کردن و ارتقاء ملاحظات زير را در نظر مي گيريم :
۱) با جستجويي که تا سطح برگ پيش مي رود شروع مي شود.
۲) بعد از پيدا کردن محل درج در سطح برگ ،کار درج ،تشخيص سر ريز و تقسيم کردن از پايين به سمت بالا پيش مي رود.
از مرتبه درخت B به عنوان حداقل تعداد کليدهايي که مي تواند در يک صفحه درخت وجود داشته باشد تعريف مي شود.
پايين ترين سطح کليدها در درخت B را برگ مي نامند.
با استفاده از تعاريف ارائه شده از مرتبه و برگ ،مي توانيم خواص يک درخت B از مرتبه m را دقيقاً بيان کنيم :
۱) هر صفحه حد اکثر m فرزند دارد.
۲) هر صفحه ،به جز ريشه و برگ ها ،حداقل] [ فرزند دارد.
۳) ريشه حداقل دو فرزند دارد.
۴) تمام برگ ها در يک سطح قرار دارد.
۵) سطح برگ ها ،يک شاخص کامل و مرتب شده از فايل داده هاي مربوط به درخت را ايجاد مي کند.
تضمين اين که درخت پهن و کم عمق باشد ،نه باريک و عميق ،مربوط به اين قوانين است :
۱) هر صفحه به جز ريشه و برگ ها حداقل ] [ فرزند دارد.
۲) هر صفحه حاوي حداقل] [ و حداکثر m کليد است.
قوانين حذف کليد k از گره n در يک درخت B به اين ترتيبند :
۱) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در nنيست ،کافي است k را از n حذف کنيد.
۲) اگر تعداد کليدهاي n بيشتر از حد اقل کليدهاي مجاز است و k بزرگترين کليد در nاست ،k را حذف کنيد و شاخص هاس سطح بالاتر را متناسب با بزرگترين کليد جديد در n تغيير دهيد.
۳) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي n به اندازه کافي خالي است n را در برابرش ادغام کنيد و يک کليد را از گره مادر حذف کنيد.
۴) اگر تعداد کليدهاي n دقيقاً برابر حداقل کليدهاي مجاز است و يکي از برادرهاي n کليدهاي زيادي دارد ،با انتقال دادن بعضي از کليدها از يک برادر به n ،کليدها را دوباره توزيع کنيد و شاخص هاي سطح بالاتر را متناسب با بزرگترين کليدهاي جديد گره هاي دستکاري شده تغيير دهيد.
توزيع دوباره در هنگام درج ،راهي براي جلوگيري يا حداقل به تعويق انداختن ايجاد صفحات جديد است.
به جاي تقسيم کردن يک صفحه پر و ايجاد دو صفحه نيمه پر، توزيع دوباره اين امکان را به ما مي دهد که تعدادي از کليدهاي سرريز شده را به صفحه ديگري انتقال دهيم.
بنابراين استفاده از توزيع دوباره به جاي تقسيم کردن باعث مي شود که درخت B از فضاي حافظه جانبي به طور مؤثرتر استفاده کند.
يک نوع جديد از درخت B را به عنوان درخت B* تعريف مي کنيم که خواص آن به اين ترتيب است :
۱) هر صفحه حداکثر m فرزند دارد.
۲) هر صفحه به جزريشه حداقل فرزند دارد.
۳) ريشه حداقل دو فرزند دارد.
۴) تمام برگ ها در يک سطح قرار دارند.
فرايند دستيابي به ديسک براي خواندن صفحه اي که در بافر وجود ندارد، نقص صفحه اي (page fault) ناميده مي شود.
