ساختار ایندکس

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

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