بررسی دسته بندی و مقایسه الگوریتم های ساخت درخت r با مجموعه درخت های *𝐑 و +𝐑

با توجه به رشد شبکه اینترنت و مطرح شدن کیفیت سرویس های متفاوتی که شبکه ها باید به کاربران ارائه دهند، طبقه بندی بسته ها به عنوان یکی از نیازمندی های مهم و حساس شبکه، هر روز اهمیت بیشتری به خود می گیرد. به گونه ای که می توان گفت برای اغلب سرویس هایی که شبکه ارائه می دهد، مسیریاب ها نیاز دارند که عمل طبقه بندی را با سرعت بالا و میزان حافظه مصرفی کم انجام دهند. طبقه بندی بسته ها، مسیریاب های شبکه را قادر به فراهم کردن خدمات پیشرفته شبکه می کند. عملیات طبقه بندی در درخت r به صورت هندسی صورت می گیرد. نظریه اصلی شاخص فضایی که مهم ترین نظریه اساسی پرس و جو می باشد، محاسبه نظریه ی نزدیکی است. معروف ترین ساختار شاخص، درخت r می باشد. استراتژی اصلی درخت r جمع آوری نودهای فضایی چند بعدی با مستطیل حداقل محدوده (mbr) می باشد که کوچک ترین نود فضایی داخلی مستطیل باشد. بعد از شاخص بندی، بهینه سازی بازیابی اطلاعات در پایگاه داده ی فضایی مهم است. از این رو جهت بررسی بیشتر موضوع، در این مقاله، شاخص فضایی جدید که متعلق به خانواده r⁺tree می باشد و مفهوم همپوشانی گره ها را حفظ می کند و r⁺⁺tree نام دارد، بررسی شده است. نتایج این مقاله نشان می دهد که r⁺⁺tree در دامنه ی پرس و جو، پرس و جو knn و پرس و جو top-k بسیار کارآمدتر از r^∗tree می باشد.