الگوریتمی جدید برای بهینه کردن ذخیره سازی در R-tree

امروزه پایگاه داده های چندبعدی در حال گسترش هستند وبه طور وسیعی در سالهای اخیر مورد استفاده قرار گرفته اند. در این پایگاه داده ها اشیا هندسی نظیر نقاط،مربع، دایره و ... مطرح میشوندکه به شی های فیزیکی در جهان واقعی مانند شهرها، رودخانه ها، کوهها و ... اشاره دارند. این مجموعه از شیهای هندسی جهت مرتب سازی باید افراز گردند تا جوابگو پرس وجوهای خاص همانند پیدا کردن اشیا درمساحت موردنظر باشند. در این زمینه متدهای زیادی معرفی شده اند ودر این بین R-tree به عنوان یکی از متدهای شاخص گذاری معتبر و پایه مطرح است. با این همه جهت بهبود ساختار شاخصگذاری محققان به دنبال ساختارهای بهتر و موثرتر در این زمینه هستند. در این مقاله یک تغییر از R-tree به نام OSR-tree را معرفی می کنیم که هدف آن کاهش تجزیه گره ها و بهره گیری از فضای کامل ذخیرهسازی است.نتایج این تحقیق نشان میدهد که استفاده از فضای حافظه ٣٠ % وارتفاع درخت ٤٠ % و زمان جستجو در حدود ١٠ % نسبت به R-tree بهبود یافته است.

Keywords:

پایگاه داده چندبعدی , متدهای دسترسی چند بعدی , ساختارهای داده ای , شاخص