मूल अवधारणा (Basic Concept)
डेटा प्रोसेसिंग के मामले में, R*-ट्री को R-ट्री के एक संस्करण के रूप में परिभाषित किया जाता है जिसे स्थानिक जानकारी (Spatial Information) को इंडेक्स करने के लिए लागू किया जाता है।
R*-ट्री का निर्माण लागत मानक R-ट्री से थोड़ा अधिक होता है, क्योंकि डेटा को पुनः सम्मिलित (Reinsert) करने की आवश्यकता हो सकती है; लेकिन परिणामी ट्री में आमतौर पर बेहतर क्वेरी प्रदर्शन होता है। मानक R-ट्री की तरह, यह पॉइंट और स्थानिक डेटा दोनों को स्टोर कर सकता है। R*-ट्री की अवधारणा 1990 में नॉर्बर्ट बेकमैन, हंस-पीटर क्रिगेल, राल्फ श्नाइडर और बर्नहार्ड सीगर द्वारा प्रस्तावित की गई थी।
R*-ट्री और R-ट्री के बीच अंतर (Difference between R*-trees and R-trees)
R*-ट्री का निर्माण बार-बार सम्मिलन (Repeated Insertion) द्वारा किया जाता है। इस ट्री में बहुत कम (यानी लगभग कोई नहीं) ओवरलैप (Overlap) होता है, जिसके परिणामस्वरूप अच्छा क्वेरी प्रदर्शन होता है। कवरेज (Coverage) और ओवरलैप दोनों का न्यूनतमकरण R-ट्री के प्रदर्शन के लिए बहुत महत्वपूर्ण है। ओवरलैप का अर्थ, डेटा सम्मिलन या क्वेरी पर, यह है कि ट्री की एक से अधिक शाखा का विस्तार करना आवश्यक है (क्योंकि डेटा को क्षेत्रों में विभाजित करने के तरीके के कारण जो ओवरलैप हो सकते हैं)। एक न्यूनतम कवरेज प्रूनिंग प्रदर्शन (Pruning Performance) को बढ़ाता है, जिससे अक्सर खोज से पूरे पेज को बाहर करना संभव होता है, विशेष रूप से नेगेटिव रेंज क्वेरीज़ (Negative Range Queries) के लिए। R*-ट्री एक संशोधित नोड स्प्लिट एल्गोरिदम (Revised Node Split Algorithm) के संग्रह और नोड ओवरफ्लो पर जबरन पुनः सम्मिलन (Forced Reinsertion) की अवधारणा को लागू करके दोनों को कम करने का प्रयास करता है। यह अवधारणा इस अवलोकन पर आधारित है कि R-ट्री संरचनाएं उनके एंट्रीज़ के सम्मिलन के क्रम के प्रति अत्यधिक संवेदनशील होती हैं, इसलिए एक सम्मिलन-निर्मित (Insertion-built) (बल्क-लोडेड के बजाय) संरचना उप-इष्टतम (Sub-optimal) होने की संभावना है। एंट्रीज़ का विलोपन और पुनः सम्मिलन उन्हें ट्री में एक ऐसी जगह "ढूंढने" की अनुमति देता है जो उनकी वास्तविक लोकेशन से अधिक उपयुक्त हो सकती है।
एल्गोरिदम और जटिलता (Algorithm and Complexity)
- R*-ट्री क्वेरी और डिलीट ऑपरेशन्स के लिए नियमित R-ट्री के समान एल्गोरिदम लागू करता है।
- सम्मिलन के समय, R*-ट्री एक संयुक्त रणनीति लागू करता है। लीफ नोड्स के लिए, ओवरलैप को न्यूनतम किया जाता है, जबकि आंतरिक नोड्स के लिए, विस्तार और क्षेत्र को न्यूनतम किया जाता है।
- स्प्लिटिंग के समय, R*-ट्री एक टोपोलॉजिकल स्प्लिट (Topological Split) लागू करता है जो परिमाप (Perimeter) के आधार पर स्प्लिट एक्सिस का चयन करता है, फिर ओवरलैप को न्यूनतम करता है।
- एक उन्नत स्प्लिट रणनीति के अलावा, R*-ट्री ऑब्जेक्ट्स और सबट्रीज़ को ट्री में पुनः सम्मिलित करके स्प्लिट्स को छोड़ने का भी प्रयास करता है, B-ट्री को संतुलित करने की अवधारणा से प्रेरित होकर।
सबसे खराब स्थिति में क्वेरी और डिलीट जटिलता इस प्रकार R-ट्री के समान हैं। R*-ट्री की सम्मिलन रणनीति O(M log M) है जो R-ट्री की लीनियर स्प्लिट रणनीति (O(M)) से अधिक जटिल है, लेकिन एक पेज साइज़ के M ऑब्जेक्ट्स के लिए क्वाड्रेटिक स्प्लिट रणनीति (O(M²)) से कम जटिल है और कुल जटिलता पर बहुत कम प्रभाव डालती है। कुल सम्मिलन जटिलता अभी भी R-ट्री के बराबर है: पुनः सम्मिलन ट्री की अधिकतम एक शाखा को प्रभावित करते हैं और इस प्रकार O(log n) पुनः सम्मिलन, नियमित R-ट्री पर डिवीजन करने के बराबर। इसलिए कुल मिलाकर, R*-ट्री की जटिलता नियमित R-ट्री के समान है।
