यूबी-ट्री

UB-tree
Two dimensional Z-order
Type	tree
Invented by	Rudolf Bayer and Volker Markl
Time complexity in big O notation
Algorithm Average Worst case

रूडोल्फ बायर और वोल्कर मार्कल द्वारा प्रस्तावित यूबी-ट्री बहुआयामी डेटा को संग्रहीत करने और कुशलतापूर्वक पुनर्प्राप्त करने के लिए एक संतुलित ट्री है। यह मूल रूप से एक B+ पेड़ है (जानकारी केवल पत्तियों में) जिसमें रिकॉर्ड Z-ऑर्डर (वक्र) के अनुसार संग्रहीत होते हैं, जिन्हें मॉर्टन ऑर्डर भी कहा जाता है। Z-ऑर्डर की गणना केवल कुंजियों को बिटवाइज़ इंटरलेसिंग करके की जाती है।

सम्मिलन, विलोपन और बिंदु क्वेरी सामान्य B+ ट्री की तरह ही की जाती है। चूँकि बहुआयामी बिंदु डेटा में श्रेणी खोज करने के लिए डेटा बेस में सामने आए एक बिंदु से, अगले Z-मान की गणना करने के लिए एक एल्गोरिदम प्रदान किया जाना चाहिए जो बहुआयामी खोज सीमा में है।

इस मुख्य समस्या को हल करने के लिए मूल एल्गोरिदम आयामीता के साथ घातीय था और इसलिए वह संभव नहीं था ( गेटनेक्स्टज़-एड्रेस ). ज़ेड-एड्रेस बिट लंबाई के साथ यूबी-ट्री रेंज क्वेरी लीनियर के इस महत्वपूर्ण भाग का समाधान बाद में वर्णित किया गया है। इस विधि का वर्णन पहले ही एक पुराने पेपर में किया जा चुका है जहां खोज वृक्षों के साथ Z-ऑर्डर का उपयोग पहली बार प्रस्तावित किया गया है।