Bx-tree
कंप्यूटर विज्ञान में, बीएक्स ट्री एक प्रश्न है जिसका उपयोग गतिशील वस्तुओं के लिए कुशल बी + ट्री-आधारित सूचकांक संरचनाओं को अद्यतन करने के लिए किया जाता है। सूचकांक संरचना बीएक्स-ट्री की आधार संरचना एक बी + ट्री है जिसमें आंतरिक नोड्स एक निर्देशिका के रूप में कार्य करते हैं, जिनमें से प्रत्येक में अपने दाहिने भाई-बहन के लिए एक सूचक होता है। बीएक्स-ट्री के पहले के संस्करण में, लीफ नोड्स में अनुक्रमित किए जा रहे गतिशील-वस्तु स्थान और संबंधित सूचकांक समय शामिल थे। अनुकूलित संस्करण में, प्रत्येक पत्ती नोड प्रविष्टि में आईडी, वेग, एकल-आयामी मानचित्रण मूल्य और वस्तु का नवीनतम अद्यतन समय होता है। गतिशील वस्तुओं के स्थानों को संग्रहीत नहीं करके फैनआउट को बढ़ाया जाता है, क्योंकि इन्हें मानचित्रण मूल्यों से प्राप्त किया जा सकता है। गतिशील वस्तुओं के लिए बी + वृक्ष का उपयोग करना कई अन्य गतिशील वस्तुओं के अनुक्रमणिकाओं के लिए, एक द्वि-आयामी गतिशील वस्तु को ओ = (x, y), (vx, vy), टी) के रूप में एक रैखिक फलन के रूप में मॉडल किया जाता है, जहां (x, y) और (vx, vy) किसी दिए गए समय उदाहरण टी पर वस्तु का स्थान और वेग हैं, यानी अंतिम अद्यतन का समय। बी + ट्री एकल-आयामी डेटा को अनुक्रमित करने के लिए एक संरचना है। बी + ट्री को एक गतिशील वस्तु सूचकांक के रूप में अपनाने के लिए, बीएक्स-ट्री एक रैखिक तकनीक का उपयोग करता है जो समय टी पर वस्तुओं के स्थान को एकल आयामी मूल्य में एकीकृत करने में मदद करता है। विशेष रूप से, वस्तुओं को पहले उनके अद्यतन समय के अनुसार विभाजित किया जाता है। एक ही विभाजन के भीतर वस्तुओं के लिए, बीएक्स-ट्री एक दिए गए समय पर अपने स्थानों को संग्रहीत करता है जो रैखिक प्रक्षेप द्वारा अनुमानित होते हैं। ऐसा करके, बीएक्स-ट्री प्रत्येक वस्तु के अद्यतन समय को संग्रहीत किए बिना एक ही विभाजन के भीतर सभी वस्तुओं का एक सुसंगत दृश्य रखता है। दूसरा, स्थान को एक ग्रिड द्वारा विभाजित किया जाता है और एक वस्तु का स्थान एक स्थान-भरने वाले वक्र के अनुसार विभाजन के भीतर रैखिक होता है, जैसे, पीनो या हिल्बर्ट वक्र। अंत में, विभाजन संख्या (समय की जानकारी) और रैखिक क्रम (स्थान की जानकारी) के संयोजन के साथ, एक वस्तु को बीएक्स-ट्री में एक आयामी सूचकांक कुंजी बीएक्स-वैल्यू के साथ अनुक्रमित किया जाता हैः यहाँ सूचकांक-विभाजन एक सूचकांक विभाजन है जो अद्यतन समय द्वारा निर्धारित किया जाता है और एक्सआरपी अनुक्रमित समय पर वस्तु की स्थिति का स्थान-भरने वाला वक्र मूल्य है, जो एक्स के द्विआधारी मूल्य को दर्शाता है, और "+" का अर्थ है संयोजन। किसी वस्तु O ((7,2), (-0.1,0.05), 10), tmu = 120 को देखते हुए, O के लिए Bx मान की गणना निम्नानुसार की जा सकती है। O को विभाजन 0 में अनुक्रमित किया गया है जैसा कि उल्लेख किया गया है। इसलिए, सूचकांक विभाजन = (00) 2। विभाजन 0 के लेबल टाइमस्टैम्प पर ओ की स्थिति (1,5) है। क्रम = 3 के साथ जेड-वक्र का उपयोग करते हुए, ओ का जेड-मान, यानी एक्स. आर. ई. पी. (090011) 2 है। अनुक्रमणिका विभाजन और एक्स. आर. पी. को जोड़ते हुए, बी. एक्स. वैल्यू (00010011) 2 = 19। उदाहरण O ((0,6), (0.2,-0.3), 10) और tmu = 120 तो विभाजन के लेबल टाइमस्टैम्प पर O की स्थितिः? ??? प्रविष्टि, अद्यतन और विलोपन एक नई वस्तु को देखते हुए, इसकी सूचकांक कुंजी की गणना की जाती है और फिर वस्तु को बीएक्स-ट्री में डाला जाता है जैसा कि बी + ट्री में होता है। एक अद्यतन में एक विलोपन के बाद एक प्रविष्टि होती है। प्रत्येक सूचकांक की नवीनतम कुंजी रखने के लिए एक सहायक संरचना का उपयोग किया जाता है ताकि कुंजी की खोज करके किसी वस्तु को हटाया जा सके। वृक्ष को प्रभावित करने से पहले अनुक्रमण कुंजी की गणना की जाती है। इस तरह, बीएक्स-ट्री सीधे बी + ट्री के अच्छे गुणों को विरासत में प्राप्त करता है, और कुशल अद्यतन प्रदर्शन प्राप्त करता है। प्रश्न सीमा प्रश्न एक सीमा प्रश्न उन सभी वस्तुओं को पुनर्प्राप्त करता है जिनका स्थान वर्तमान समय से पहले के समय पर आयताकार सीमा के भीतर आता है। बीएक्स-ट्री प्रश्नों का उत्तर देने के लिए क्वेरी-विंडो एनलार्जमेंट तकनीक का उपयोग करता है। चूँकि बीएक्स-ट्री किसी वस्तु के स्थान को उसके अद्यतन समय के कुछ समय बाद संग्रहीत करता है, इसलिए विस्तार में दो मामले शामिल होते हैंः एक स्थान को या तो पहले के समय पर वापस लाया जाना चाहिए या बाद के समय पर आगे बढ़ाया जाना चाहिए। मुख्य विचार क्वेरी विंडो को बड़ा करना है ताकि यह उन सभी वस्तुओं को संलग्न कर सके जिनकी स्थिति अपने लेबल टाइमस्टैम्प पर क्वेरी विंडो के भीतर नहीं है, लेकिन क्वेरी टाइमस्टैम्प पर क्वेरी विंडो में प्रवेश करेगी। विस्तार के बाद, विस्तारित क्वेरी विंडो में आने वाली वस्तुओं को खोजने के लिए बीएक्स-ट्री के विभाजन को पार करने की आवश्यकता होती है। प्रत्येक विभाजन में, एक स्थान-भरने वाले वक्र के उपयोग का अर्थ है कि मूल, द्वि-आयामी स्थान में एक सीमा प्रश्न परिवर्तित, एक-आयामी स्थान में सीमा प्रश्नों का एक समूह बन जाता है। तिरछे डेटासेट में विस्तार के बाद अत्यधिक बड़े क्वेरी क्षेत्र से बचने के लिए, क्वेरी एल्गोरिदम का एक अनुकूलन मौजूद है, जो अनावश्यक क्वेरी विस्तार से बचकर क्वेरी दक्षता में सुधार करता है। के निकटतम पड़ोसी प्रश्न के निकटतम पड़ोसी प्रश्न की गणना के उत्तर प्राप्त होने तक वृद्धिशील रूप से बढ़े हुए खोज क्षेत्र के साथ बार-बार रेंज प्रश्न करके की जाती है। एक अन्य संभावना यह है कि आईडिस्टेंस तकनीक में इसी तरह के पूछताछ विचारों को नियोजित किया जाए। अन्य प्रश्न रेंज क्वैरी और के नियर नेबर क्वैरी एल्गोरिदम को अंतराल प्रश्नों, निरंतर प्रश्नों आदि का समर्थन करने के लिए आसानी से बढ़ाया जा सकता है। चूंकि बीएक्स-ट्री बी + ट्री सूचकांक के शीर्ष पर निर्मित एक सूचकांक है, इसलिए बीएक्स-ट्री में सभी संचालन, जिसमें सम्मिलन, विलोपन और खोज शामिल हैं, बी + ट्री में समान हैं। इन कार्यों के कार्यान्वयन को बदलने की कोई आवश्यकता नहीं है। एकमात्र अंतर मौजूदा डी. बी. एम. एस. में संग्रहीत प्रक्रिया के रूप में अनुक्रमण कुंजी प्राप्त करने की प्रक्रिया को लागू करना है। इसलिए, बीएक्स-ट्री को कर्नेल को छुए बिना आसानी से मौजूदा डीबीएमएस में एकीकृत किया जा सकता है। स्पेड एक लोकप्रिय संबंधपरक डेटाबेस प्रणाली माईएसक्यूएल के शीर्ष पर निर्मित वस्तु प्रबंधन प्रणाली है, जो वस्तुओं को अनुक्रमित करने के लिए बीएक्स-ट्री का उपयोग करता है। कार्यान्वयन में, चलती वस्तु डेटा को सीधे माईएसक्यूएल पर परिवर्तित और संग्रहीत किया जाता है, और प्रश्नों को मानक एसक्यूएल कथनों में बदल दिया जाता है जिन्हें संबंधात्मक इंजन में कुशलता से संसाधित किया जाता है। सबसे महत्वपूर्ण बात यह है कि ये सभी माइएसक्यूएल कोर में घुसपैठ किए बिना बड़े करीने से और स्वतंत्र रूप से प्राप्त किए जाते हैं। डेटा स्क्यू के साथ प्रदर्शन ट्यूनिंग संभावित समस्या बीएक्स ट्री एक आयामी कुंजी में द्वि-आयामी स्थान का मानचित्रण करते हुए अंतरिक्ष विभाजन के लिए एक ग्रिड का उपयोग करता है। यह तिरछे डेटा से निपटने के दौरान पूछताछ और अद्यतन संचालन दोनों में प्रदर्शन में गिरावट ला सकता है। यदि ग्रिड सेल का आकार अधिक है, तो कई वस्तुएँ एक सेल में निहित होती हैं। चूँकि कोशिका में वस्तुएँ सूचकांक से अप्रभेद्य होती हैं, इसलिए अंतर्निहित बी + ट्री में कुछ अतिप्रवाह नोड्स होंगे। अतिप्रवाह पृष्ठों का अस्तित्व न केवल वृक्ष के संतुलन को नष्ट करता है बल्कि अद्यतन लागत को भी बढ़ाता है। जहाँ तक प्रश्नों की बात है, दिए गए प्रश्न क्षेत्र के लिए, बड़ी कोशिका अधिक गलत सकारात्मक होती है और प्रसंस्करण समय को बढ़ाती है। दूसरी ओर, यदि स्थान को महीन ग्रिड के साथ विभाजित किया जाता है, अर्थात। छोटी कोशिकाएँ, प्रत्येक कोशिका में कुछ वस्तुएँ होती हैं। शायद ही अतिप्रवाह पृष्ठ हैं ताकि अद्यतन लागत को कम किया जा सके। क्वेरी में कम गलत पॉजिटिव पाए जाते हैं। हालांकि, अधिक कोशिकाओं की खोज की आवश्यकता है। खोजे गए कक्षों की संख्या में वृद्धि भी एक प्रश्न का कार्यभार बढ़ाती है। सूचकांक ट्यूनिंग एसटी2बी-ट्री अंतरिक्ष में डेटा वक्र और समय के साथ डेटा परिवर्तन से निपटने के दौरान बीएक्स-ट्री के प्रदर्शन को ट्यूनिंग करने के लिए एक स्व-ट्यूनिंग ढांचा पेश करता है। अंतरिक्ष में डेटा वक्र से निपटने के लिए, एसटी2बी-ट्री संदर्भ बिंदुओं के एक समूह का उपयोग करके पूरे स्थान को विभिन्न वस्तु घनत्व वाले क्षेत्रों में विभाजित करता है। प्रत्येक क्षेत्र एक व्यक्तिगत ग्रिड का उपयोग करता है जिसका कोशिका आकार उसके अंदर की वस्तु के घनत्व से निर्धारित होता है। बीएक्स-ट्री में अलग-अलग समय अंतराल के संबंध में कई विभाजन होते हैं। जैसे-जैसे समय बीतता जाता है, प्रत्येक विभाजन बारी-बारी से बढ़ता और सिकुड़ता जाता है। एसटी2बी-ट्री समय के साथ डेटा परिवर्तनों को समायोजित करने के लिए स्थान विभाजन को समायोजित करने के लिए सूचकांक को ऑनलाइन ट्यून करने के लिए इस सुविधा का उपयोग करता है। विशेष रूप से, जैसे-जैसे एक विभाजन सिकुड़ता है और खाली होने लगता है और बढ़ने लगता है, यह नवीनतम डेटा घनत्व के अनुसार प्रत्येक संदर्भ बिंदु के लिए संदर्भ बिंदुओं और नए ग्रिड का एक नया सेट चुनता है। ट्यूनिंग एक निश्चित अवधि के दौरान एकत्र किए गए नवीनतम आंकड़ों पर आधारित है, ताकि स्थान विभाजन का तरीका नवीनतम डेटा वितरण के लिए सबसे उपयुक्त माना जाए। इसके माध्यम से, एसटी2बी-ट्री से अंतरिक्ष में डेटा तिरछेपन और समय के साथ डेटा परिवर्तन के कारण होने वाले प्रभाव को कम करने की उम्मीद है। बी + वृक्ष हिल्बर्ट वक्र जेड-क्रम (वक्र) संदर्भ बी-वृक्ष भी देखें।