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