মৌলিক ধারণা
ডেটা প্রসেসিং-এ, R*-ট্রি হলো R-ট্রির একটি ভ্যারিয়েন্ট যা স্পেশিয়াল ইনফরমেশন ইনডেক্স করার জন্য বাস্তবায়িত হয়।
R*-ট্রির কনস্ট্রাকশন কস্ট স্ট্যান্ডার্ড R-ট্রির চেয়ে কিছুটা বেশি, কারণ ডেটা রি-ইনসার্ট করার প্রয়োজন হতে পারে; কিন্তু ফলাফলস্বরূপ ট্রি সাধারণত ভালো কোয়েরি পারফরমেন্স দেয়। স্ট্যান্ডার্ড R-ট্রির মতো, এটি পয়েন্ট এবং স্পেশিয়াল ডেটা দুটোই স্টোর করতে পারে। R*-ট্রি কনসেপ্ট ১৯৯০ সালে Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, এবং Bernhard Seeger দ্বারা প্রপোজ করা হয়েছিল।
R*-ট্রি এবং R-ট্রির পার্থক্য
R*-ট্রি রিপিটেড ইনসার্শন দিয়ে কনস্ট্রাক্ট করা হয়। এই ট্রিতে খুব কম (প্রায় শূন্য) ওভারল্যাপ থাকে, ফলে ভালো কোয়েরি পারফরমেন্স। কভারেজ এবং ওভারল্যাপ দুটোর মিনিমাইজেশন R-ট্রির পারফরমেন্সের জন্য খুব গুরুত্বপূর্ণ। ওভারল্যাপের অর্থ, ডেটা ইনসার্শন বা কোয়েরি সময়, ট্রির একাধিক ব্রাঞ্চ এক্সপ্যান্ড করতে হয় (কারণ ডেটা 리जनগুলোর মধ্যে ভাগ হয় যারা ওভারল্যাপ করতে পারে)। একটি মিনিমাইজড কভারেজ প্রুনিং পারফরমেন্স বাড়ায়, পূর্ণ পেজ সার্চ থেকে বাদ দিতে পারে প্রায়ই, বিশেষ করে নেগেটিভ রেঞ্জ কোয়েরির জন্য। R*-ট্রি উভয়ই কমানোর চেষ্টা করে একটি রিভাইজড নোড স্প্লিট অ্যালগরিদম এবং নোড ওভারফ্লোয়ে ফোর্সড রি-ইনসার্শন কনসেপ্ট বাস্তবায়ন করে। এই কনসেপ্ট ఆন্বেষণয় ভিত্তি করে যে R-ট্রি স্ট্রাকচার খুব সেন্সিটিভ তাদের এন্ট্রিগুলোর ইনসার্শন অর্ডারের ওপর, তাই একটি ইনসার্শন-বিল্ট (বাল্ক-লোডেড নহয়) স্ট্রাকচার সাব-অপ্টিমাল হয়ে যাওয়ার সম্ভাবনা। এন্ট্রিগুলো ডিলিট এবং রি-ইনসার্ট করা তাদেরকে "ফাইন্ড" করতে দেয় ট্রিতে এমন একটি জায়গা যা তাদের অ্যাকচুয়াল লোকেশন চেয়ে বেশি উপযুক্ত হতে পারে।
অ্যালগরিদম এবং কমপ্লেক্সিটি
- R*-ট্রি রेгуলার R-ট্রির মতো অ্যালগরিদম বাস্তবায়ন করে কোয়েরি এবং ডিলিট অপারেশনের জন্য।
- ইনসার্শন সময়, R*-ট্রি একটি কম্বাইনড Страটেজি বাস্তবায়ন করে। লিফ নোডের জন্য, ওভারল্যাপ মিনিমাইজ করা হয়, যখন ইনার নোডের জন্য, এনলার্জমেন্ট এবং এরিয়া মিনিমাইজ করা হয়।
- স্প্লিটিং সময়, R*-ট্রি একটি টপোলজিক্যাল স্প্লিট বাস্তবায়ন করে যা স্প্লিট অ্যাক্স পেরিমিটার বেসড সিলেক্ট করে, তারপর ওভারল্যাপ মিনিমাইজ করে।
- এনহ্যান্সড স্প্লিট স্ট্র্যাটেজির পাশাপাশি, R*-ট্রি স্প্লিট এড়ানোর চেষ্টা করে অবজেক্ট এবং সাবট্রি রি-ইনসার্ট করে ট্রিতে, B-ট্রি ব্যালেন্স করার কনসেপ্ট থেকে অনুপ্রাণিত।
ওয়ার্স্ট কেস কোয়েরি এবং ডিলিট কমপ্লেক্সিটি এইভাবে R-ট্রির মতোই। R*-ট্রির ইনসার্শন স্ট্র্যাটেজি O(M log M) বেশি কমপ্লেক্স রেন্ডার স্প্লিট স্ট্র্যাটেজি (O(M)) চেয়ে, কিন্তু কোয়াড্রাটিক স্প্লিট স্ট্র্যাটেজি (O(M2)) চেয়ে কম কমপ্লেক্স একটি পেজ সাইজ M অবজেক্টের জন্য এবং টোটাল কমপ্লেক্সিটির ওপর সামান্য প্রভাব ফেলে। টোটাল ইনসার্শন কমপ্লেক্সিটি এখনও R-ট্রির সাথে তুলনামূলক: রি-ইনসার্শনস বেশি से বেশি এক ব্রাঞ্চকে এফেক্ট করে এবং এইভাবে O(log n) রি-ইনসার্শনস, রেগুলার R-ট্রিতে একটি ডিভিশন করার সাথে তুলনামূলক। তাই সামগ্রিকভাবে, R*-ট্রির কমপ্লেক্সিটি রেগুলার R-ট্রির মতোই।
