हिल्बर्ट R-ट्री, R-ट्री का एक संस्करण (Variant), बहुआयामी वस्तुओं जैसे रेखाएं, क्षेत्र, 3-D ऑब्जेक्ट्स, या उच्च-आयामी फीचर-आधारित पैरामीट्रिक ऑब्जेक्ट्स के लिए एक इंडेक्स के रूप में परिभाषित किया गया है। इसे बहुआयामी वस्तुओं के लिए B+-ट्री के विस्तार के रूप में कल्पना किया जा सकता है।
R-ट्री का प्रदर्शन उस एल्गोरिदम की गुणवत्ता पर निर्भर करता है जो नोड पर डेटा रेक्टेंगल्स (Data Rectangles) को क्लस्टर करता है। हिल्बर्ट R-ट्री स्पेस-फिलिंग कर्व्स (Space-Filling Curves), और विशेष रूप से हिल्बर्ट कर्व (Hilbert Curve), को डेटा रेक्टेंगल्स पर एक रैखिक क्रम (Linear Ordering) लागू करने के लिए लागू करते हैं।
हिल्बर्ट R-ट्री दो प्रकार के होते हैं: एक स्टैटिक डेटाबेस के लिए, और एक डायनामिक डेटाबेस के लिए। दोनों मामलों में हिल्बर्ट स्पेस-फिलिंग कर्व्स को नोड में बहुआयामी वस्तुओं के बेहतर क्रम के लिए लागू किया जाता है। इस क्रम को 'अच्छा' माना जाना चाहिए, इस अर्थ में कि इसे 'समान' (Similar) डेटा रेक्टेंगल्स को एक साथ समूहित करना चाहिए, ताकि परिणामी न्यूनतम बाउंडिंग रेक्टेंगल्स (MBRs) का क्षेत्रफल और परिमाप कम हो। पैक्ड हिल्बर्ट R-ट्री स्टैटिक डेटाबेस के लिए उपयोगी हैं जहां अपडेट बहुत दुर्लभ होते हैं या बिल्कुल नहीं होते।
मूल विचार (The Basic Idea)
हालांकि निम्न उदाहरण स्टैटिक वातावरण के लिए है, यह अच्छे R-ट्री डिजाइन के सहज सिद्धांतों पर चर्चा करता है। ये सिद्धांत स्टैटिक और डायनामिक दोनों डेटाबेस के लिए मान्य हैं।
रूसोपोलोस और लेफकर (Roussopoulos and Leifker) ने एक पैक्ड R-ट्री बनाने की तकनीक प्रस्तावित की जो लगभग 100% स्पेस यूटिलाइजेशन प्राप्त करती है।
विचार यह है कि रेक्टेंगल के कोनों में से एक के x या y निर्देशांकों पर डेटा को सॉर्ट किया जाए। चार निर्देशांकों में से किसी पर भी सॉर्ट करने से समान परिणाम मिलते हैं। इस चर्चा में या तो पॉइंट्स या रेक्टेंगल्स को रेक्टेंगल के निचले बाएं कोने के x निर्देशांक पर सॉर्ट किया जाता है, जिसे "lowx पैक्ड R-ट्री" कहा जाता है। रेक्टेंगल्स की सॉर्ट की गई सूची को स्कैन किया जाता है; क्रमिक रेक्टेंगल्स को उसी R-ट्री लीफ नोड को तब तक असाइन किया जाता है जब तक वह नोड भर न जाए; फिर एक नया लीफ नोड बनाया जाता है, और सॉर्ट की गई सूची का स्कैन जारी रहता है। इस प्रकार, परिणामी R-ट्री का नोड पूरी तरह से पैक्ड होगा, संभवतः प्रत्येक स्तर पर अंतिम नोड के अपवाद के साथ। इससे लगभग 100% स्पेस यूटिलाइजेशन होती है। ट्री के उच्च स्तरों को इसी तरह बनाया जाता है।
एल्गोरिदम Hilbert-Pack
(रेक्टेंगल्स को R-ट्री में पैक करना)
चरण 1. प्रत्येक डेटा रेक्टेंगल के लिए हिल्बर्ट मान (Hilbert Value) की गणना की जाती है।
चरण 2. डेटा रेक्टेंगल्स को आरोही हिल्बर्ट मानों पर सॉर्ट किया जाता है।
चरण 3. /* लीफ नोड्स बनाना (लेवल l=0) */
- जब तक (और रेक्टेंगल्स हैं)
- एक नया R-ट्री नोड उत्पन्न करें
- अगले C रेक्टेंगल्स को इस नोड को असाइन करें
चरण 4. /* उच्च स्तर पर नोड्स बनाना (l + 1) */
- जब तक (स्तर l पर > 1 नोड्स हैं)
- स्तर l ≥ 0 पर नोड्स को आरोही निर्माण समय पर सॉर्ट करें
- चरण 3 दोहराएं
यहां मान लिया गया है कि या तो डेटा स्टैटिक है या संशोधन की आवृत्ति कम है। यह ~100% स्पेस यूटिलाइजेशन के साथ R-ट्री बनाने के लिए एक सरल यूरिस्टिक (Heuristic) है जो साथ ही अच्छी प्रतिक्रिया समय भी देगा।
