हिल्बर्ट आर-ट्री, एक आर-ट्री संस्करण, को बहुआयामी वस्तुओं जैसे लाइनों, क्षेत्रों, 3-डी वस्तुओं, या उच्च-आयामी सुविधा-आधारित पैरामीट्रिक वस्तुओं के लिए एक सूचकांक के रूप में परिभाषित किया गया है। इसकी कल्पना बहुआयामी वस्तुओं के लिए B+-ट्री के विस्तार के रूप में की जा सकती है।
आर-पेड़ का प्रदर्शन एल्गोरिथम की गुणवत्ता पर निर्भर करता है जो एक नोड पर डेटा आयतों को क्लस्टर करता है। डेटा आयतों पर एक रेखीय क्रम लगाने के लिए हिल्बर्ट आर-पेड़ अंतरिक्ष-भरने वाले वक्रों और विशेष रूप से हिल्बर्ट वक्र को लागू करते हैं।
हिल्बर्ट आर-पेड़ दो प्रकार के होते हैं:एक स्थिर डेटाबेस के लिए, और दूसरा गतिशील डेटाबेस के लिए। दोनों ही मामलों में नोड में बहुआयामी वस्तुओं के बेहतर क्रम को प्राप्त करने के लिए हिल्बर्ट स्पेस-फिलिंग कर्व्स को लागू किया जाता है। इस आदेश को 'अच्छा' माना जाना चाहिए, इस अर्थ में कि इसे 'समान' डेटा आयतों को एक साथ समूहित करना चाहिए, ताकि परिणामी न्यूनतम बाउंडिंग आयतों (एमबीआर) के क्षेत्र और परिधि को कम किया जा सके। पैक्ड हिल्बर्ट आर-पेड़ स्थिर डेटाबेस के लिए उपयोगी होते हैं जिनमें अद्यतन बहुत दुर्लभ होते हैं या जिनमें कोई अद्यतन नहीं होते हैं।
मूल विचार
यद्यपि निम्नलिखित उदाहरण एक स्थिर वातावरण के लिए है, यह अच्छे आर-ट्री डिज़ाइन के लिए सहज सिद्धांतों पर चर्चा करता है। ये सिद्धांत स्थिर और गतिशील डेटाबेस दोनों के लिए कानूनी हैं।
रूसोपोलोस और लीफकर ने एक पैक्ड आर-पेड़ के निर्माण के लिए एक तकनीक का प्रस्ताव रखा जो लगभग 100% अंतरिक्ष उपयोग प्राप्त करता है।
आयतों के किसी एक कोने के x या y निर्देशांक पर डेटा को सॉर्ट करने के लिए विचार विकसित किया गया है। चार निर्देशांकों में से किसी एक को छाँटने से समान परिणाम मिलते हैं। इस चर्चा में या तो बिंदुओं या आयतों को आयत के निचले बाएँ कोने के x निर्देशांक पर क्रमबद्ध किया जाता है, जिसे "लोएक्स पैक्ड आर-ट्री" के रूप में दर्शाया जाता है। आयतों की क्रमबद्ध सूची स्कैन की जाती है; लगातार आयतों को समान आर-ट्री लीफ नोड को तब तक असाइन किया जाता है जब तक कि वह नोड भरा न हो; फिर एक नया लीफ नोड बनाया जाता है, और सॉर्ट की गई सूची की स्कैनिंग जारी रहती है। इस प्रकार, परिणामी आर-पेड़ का नोड पूरी तरह से पैक किया जाएगा, प्रत्येक स्तर पर अंतिम नोड के संभावित अपवाद के साथ। यह घटना की ओर जाता है ताकि अंतरिक्ष उपयोग 100% हो। पेड़ के ऊंचे स्तर इसी तरह बनाए जाते हैं।
एल्गोरिदम हिल्बर्ट-पैक
(आयतों को आर-पेड़ में पैक करना)
चरण 1. प्रत्येक डेटा आयत के लिए हिल्बर्ट मान की गणना की जाती है।
चरण 2. आरोही हिल्बर्ट मानों पर डेटा आयतों को क्रमबद्ध किया जाता है।
चरण 3. /* लीफ नोड्स बनाना (स्तर l=0) */
- जबकि (अधिक आयत हैं)
- एक नया आर-ट्री नोड उत्पन्न होता है
- इस नोड के लिए अगला C आयत असाइन किया गया है
चरण 4. /* उच्च स्तर पर नोड्स बनाना (l + 1) */
- जबकि (लेवल 1 पर> 1 नोड हैं)
- लेवल l 0 पर आरोही निर्माण समय पर नोड्स को सॉर्ट किया जाता है
- चरण 3 दोहराया जाता है
यहां धारणा यह है कि या तो डेटा स्थिर है या संशोधन की आवृत्ति कम है। यह एक आर-पेड़ बनाने के लिए एक सरल अनुमानी है जिसमें ~100% अंतरिक्ष उपयोग होता है, साथ ही साथ एक अच्छा प्रतिक्रिया समय भी होगा।