دانلود تحقیق ساختار ایندکس

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

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

در جستجوی دودویی لازم است امکان پرش به وسط فایل را داشته باشیم.
راه دیگر برای مرتب سازی ، ایجاد شاخص برای فایل است.
ساختار شیء شاخص بسیار ساده است.

این ساختار لیستی است که هر عنصر آن دو فیلد دارد:
یک فیلد کلید و یک فیلد برای آفست بایت.
عملیاتی که برای یافتن داده های مورد نظر ،از طریق شاخص لازمند عبارتند از :
۱) ایجاد فایل داده ها و شاخص خالی اولیه
۲) باز کزدن فایل شاخص در حافظه ،قبل از به کارگیری آن
۳) نوشتن فایل شاخص بر روی دیسک ،پس از به کارگیری آن
۴) افزودن رکوردهایی به فایل و داده ها
۵) حذف رکوردها از فایل داده ها
۶) بهنگام کردن رکوردها در فایل داده ها
۷) بهنگام کردن شاخص برای انعکاس تغییرات به عمل آمده در فایل داده ها.
مزیت بزرگی که روش شیء گرا دارد آن است که برای اجرای این عملیات به هرچه نیاز داشته باشیم می توانیم در متدهای کلاس خود بیابیم.
در ایجاد فایل ها باید دو فایل ایجاد شوند :
۱) فایل داده ها برای نگهداری اشیای داده ای
۲) فایل شاخص برای نگهداری شاخص کلید اولیه
بهنگام سازی رکوردها به دو صورت انجام می شود :
۱) بهنگام سازی ،تعداد فیلد و کلید را تغییر می دهد.
۲) بهنگام سازی ،در فیلد و کلید تأثیر نمی گذارد.
آشکارترین بهینه سازی ،استفاده از جستجوی دودویی در متد 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) نامیده می شود.

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

۲) آن صفحه قبلاً در بافر بوده است اما صفحه جدیدی جایگزین آن شده است.

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

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

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

۲) ترتیبی : به فایل می توان دستیابی ترتیبی داشت و رکوردها را به ترتیب توسط کلید بازگرداند.

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

چنین مجموعه ای از رکوردها را مجموعه ترتیبی می نامیم.

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

مشکل سرریز شدن را می توان توسط یک فرایند شکستن بلوک ها کنترل کرد که شبیه