PH-tree
पी. एच.-ट्री एक वृक्ष डेटा संरचना है जिसका उपयोग बहु-आयामी डेटा (कुंजी) जैसे भौगोलिक निर्देशांक, बिंदु, विशेषता वैक्टर, आयत या सीमा बक्से के स्थानिक अनुक्रमण के लिए किया जाता है। पी. एच.-ट्री एक क्वाडट्री या ऑक्ट्री के समान संरचना के साथ अंतरिक्ष विभाजन सूचकांक है। हालांकि, क्वाडट्री के विपरीत, यह ट्राइ के आधार पर एक विभाजन नीति का उपयोग करता है और क्रिट बिट ट्री के समान है जो कुंजी के बिट-प्रतिनिधित्व पर आधारित है। बिट-आधारित विभाजन नीति, जब नोड्स के लिए विभिन्न आंतरिक प्रतिनिधित्वों के उपयोग के साथ संयुक्त होती है, तो उच्च-आयामी डेटा के साथ मापनीयता प्रदान करती है। बिट-प्रतिनिधित्व विभाजन नीति भी अधिकतम गहराई लागू करती है, इस प्रकार अपक्षित पेड़ों और पुनर्संतुलन की आवश्यकता से बचा जाता है। मूल पी. एच.-ट्री एक स्थानिक सूचकांक है जो कुंजी, जो पूर्णांक के साथ-आयामी वैक्टर हैं, को उपयोगकर्ता परिभाषित मूल्यों के लिए मानचित्रित करता है। पी. एच.-ट्री एक क्रिट बिट ट्री का एक बहु-आयामी सामान्यीकरण है इस अर्थ में कि एक क्रिट बिट ट्री-आयामी कुंजी के साथ एक पी. एच.-ट्री के बराबर है। क्रिट बिट ट्री की तरह, और अधिकांश अन्य स्थानिक सूचकांकों के विपरीत, पी. एच.-ट्री एक बहु-मानचित्र के बजाय एक मानचित्र है। ए-डायमेंशनल पीएच-ट्री नोड्स का एक वृक्ष है जहां प्रत्येक नोड विभाजन इसे चतुर्थांश में उपविभाजित करके स्थान देता है (नीचे देखें कि उच्च आयामी डेटा के साथ संभावित रूप से बड़े नोड्स कैसे मापते हैं)। प्रत्येक चतुर्थांश में अधिक से अधिक एक प्रविष्टि होती है, या तो एक कुंजी-मूल्य जोड़ी (पत्ती चतुर्थांश) या एक कुंजी-उप-नोड जोड़ी। एक कुंजी-उपनोद जोड़ी के लिए, कुंजी उपनोद के केंद्र का प्रतिनिधित्व करती है। कुंजी सबनोड और उसके चाइल्ड सबनोड में सभी कुंजियों का सामान्य उपसर्ग (बिट-प्रतिनिधित्व) भी है। प्रत्येक नोड में कम से कम दो प्रविष्टियाँ होती हैं, अन्यथा इसे मूल नोड के साथ मिला दिया जाता है। पी. एच.-पेड़ों के कुछ अन्य संरचनात्मक गुण हैंः वे-एरी पेड़ हैं। वे स्वाभाविक रूप से असंतुलित हैं लेकिन उनकी गहराई कुंजी की बिट चौड़ाई तक सीमित होने के कारण असंतुलन सीमित है, उदाहरण के लिए। 32 बिट पूर्णांक के साथ एक आयामी कुंजी के लिए 32 तक। सम्मिलन या हटाने के संचालन के कारण ठीक एक नोड को संशोधित किया जाता है और संभावित रूप से एक दूसरा नोड जोड़ा या हटाया जा सकता है। यह समवर्ती कार्यान्वयन के लिए उपयोगी हो सकता है। इसका मतलब यह भी है कि संशोधन लागत में थोड़ा अंतर है। उनकी संरचना सम्मिलन/हटाने के क्रम से स्वतंत्र है। विभाजन रणनीति अधिकांश क्वाडट्री के समान, पी. एच.-ट्री नोड्स का एक पदानुक्रम है जहाँ प्रत्येक नोड सभी आयामों में स्थान को विभाजित करता है। इस प्रकार, एक नोड में उपनोड तक हो सकते हैं, प्रत्येक चतुर्थांश के लिए एक। क्वाड्रेंट नंबरिंग पी. एच.-ट्री वृक्ष में अपनी स्थिति निर्धारित करने के लिए बहु-आयामी कुंजी के बिट्स का उपयोग करता है। जिन सभी चाबियों में एक ही प्रमुख बिट होते हैं, उन्हें पेड़ की एक ही शाखा में संग्रहीत किया जाता है। उदाहरण के लिए, स्तर पर एक नोड में, उस चतुर्थांश को निर्धारित करने के लिए जहां एक कुंजी डाली जानी चाहिए (या हटा दी जानी चाहिए या ऊपर देखी जानी चाहिए), यह कुंजी के प्रत्येक आयाम के एस बिट को देखता है। 8 चतुर्थांश वाले 3डी नोड के लिए (एक घन बनाते हुए) कुंजी के पहले आयाम का एस बिट यह निर्धारित करता है कि लक्ष्य चतुर्थांश घन के बाईं या दाईं ओर है या नहीं, दूसरे आयाम का एस बिट यह निर्धारित करता है कि यह आगे या पीछे है या नहीं, और तीसरे आयाम का एस बिट नीचे बनाम ऊपर निर्धारित करता है, चित्र देखें। 1डी उदाहरण 8 बिट मानों के साथ तीन 1डी कुंजियों के साथ उदाहरण हैः, और। एक खाली पेड़ में जोड़ने और जोड़ने का परिणाम एक एकल नोड में होता है। दोनों कुंजी पहले अपने छठे बिट में भिन्न होती हैं इसलिए नोड का एक स्तर होता है (0 से शुरू होता है)। नोड में एक 5 बिट उपसर्ग होता है जो दोनों कुंजी के सामान्य 5 बिट का प्रतिनिधित्व करता है। नोड में दो चतुर्थांश होते हैं, प्रत्येक कुंजी एक चतुर्थांश में संग्रहीत होती है। तीसरी कुंजी को जोड़ने से एक अतिरिक्त नोड में एक चतुर्थांश में मूल नोड को सबनोड के रूप में और दूसरे चतुर्थांश में नई कुंजी होती है। 2डी उदाहरण 2डी कुंजियों के साथ प्रत्येक नोड में चतुर्थांश होते हैं। चतुर्थांश की स्थिति जहां एक कुंजी संग्रहीत की जाती है, कुंजी के संबंधित बिट्स से निकाली जाती है, प्रत्येक आयाम से एक बिट। नोड के चार चतुर्थांश एक 2डी हाइपरक्यूब बनाते हैं (चतुर्थांश खाली हो सकते हैं)। कुंजी से निकाले गए बिट हाइपरक्यूब पता बनाते हैं, के लिए और के लिए। प्रभावी रूप से नोड के हाइपरक्यूब में चतुर्थांश की स्थिति है। नोड संरचना एक नोड में प्रविष्टियों का क्रम हमेशा जेड-क्रम का अनुसरण करता है। उदाहरण के लिए, एक नोड में प्रविष्टियों को आकार की निश्चित आकार सरणियों में संग्रहीत किया जा सकता है। फिर प्रभावी रूप से एक चतुर्थांश का सरणी सूचकांक है। यह देखने, डालने और हटाने की अनुमति देता है और इसे संग्रहीत करने की कोई आवश्यकता नहीं है। अंतरिक्ष जटिलता हालांकि प्रति नोड है, इसलिए यह उच्च आयामी डेटा के लिए कम उपयुक्त है। एक अन्य समाधान एक क्रमबद्ध संग्रह में प्रविष्टियों को संग्रहीत करना है, जैसे कि गतिशील सरणी और/या बी-ट्री। यह खोज कार्यों को धीमा कर देता है लेकिन स्मृति की खपत को कम कर देता है। मूल कार्यान्वयन का उद्देश्य निश्चित और गतिशील सरणी प्रतिनिधित्व के बीच स्विच करके न्यूनतम स्मृति खपत करना है जो कम स्मृति का उपयोग करता है। अन्य कार्यान्वयन गतिशील रूप से स्विच नहीं करते हैं, लेकिन उच्च आयामी डेटा के लिए निश्चित सरणी, गतिशील सरणी और बी-ट्री का उपयोग करते हैं। ऑपरेशन लुकअप, इंसर्शन और रिमूवल ऑपरेशन सभी बहुत समान काम करते हैंः सही नोड ढूंढें, फिर नोड पर ऑपरेशन करें। विंडो प्रश्न और-निकटतम-पड़ोसी खोज अधिक जटिल हैं। लुकअप द लुकअप ऑपरेशन यह निर्धारित करता है कि पेड़ में कोई चाबी मौजूद है या नहीं। यह पेड़ के नीचे चलता है और प्रत्येक नोड की जांच करता है कि क्या इसमें एक उम्मीदवार उप-नोड है या एक उपयोगकर्ता मूल्य है जो कुंजी से मेल खाता है। फ़ंक्शन लुकअप (कुंजी) प्रविष्टि है-गेट _ रूट _ एंट्री ()// यदि ट्री खाली नहीं है तो रूट प्रविष्टि में एक रूट नोड होता है जबकि प्रविष्टि! = एन. आई. एल. और & entry.is_subnode () नोड करें-entry.get_node () प्रविष्टि-node.get_entry (कुंजी) रिपीट रिटर्न प्रविष्टि// प्रविष्टि-एन. आई. एल. फ़ंक्शन हो सकती है-गेट _ एंट्री (कुंजी) नोड है-वर्तमान नोड एच.-एक्सट्रैक्ट _ बिट्स _ एट _ डेप्थ (कुंजी, node.get_depth ()) प्रविष्टि-node.get_entry_at (एच.) वापसी प्रविष्टि// प्रविष्टि हो सकती है-एन. आई. एल. सम्मिलित करें जब तक कि वे कुंजी पहले से मौजूद न हो। ऑपरेशन लुकअप फंक्शन की तरह ट्री को पार करता है और फिर कुंजी को नोड में डालता है। विचार करने के लिए कई मामले हैंः चतुर्थांश खाली है और हम केवल चतुर्थांश में एक नई प्रविष्टि डाल सकते हैं और वापस आ सकते हैं। चतुर्थांश में एक कुंजी के साथ एक उपयोगकर्ता प्रविष्टि होती है जो नई प्रविष्टि के समान होती है। इस तरह की टक्कर से निपटने का एक तरीका एक ध्वज को वापस करना है जो विफल सम्मिलन का संकेत देता है। यदि ट्री को नोड की प्रविष्टि के रूप में एक संग्रह के साथ बहु-मानचित्र के रूप में लागू किया जाता है, तो उस संग्रह में नया मूल्य जोड़ा जाता है। चतुर्थांश में एक अलग कुंजी के साथ एक प्रविष्टि (उपयोगकर्ता प्रविष्टि या उप-नोड प्रविष्टि) होती है। इस मामले में मौजूदा प्रविष्टि को एक नए सबनोड के साथ बदलने की आवश्यकता होती है जिसमें पुरानी और नई प्रविष्टि होती है। फंक्शन इन्सर्ट (नोड, की, वैल्यू) लेवल-0 node.get_level ()// लेवल रूट के लिए 0 है, h _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ टक्कर, पहले से ही एक प्रविष्टि रिटर्न है-फेल्ड _ इंसर्शन एल्स// केस 3. लेवल _ डिफेनस-गेट _ लेवल _ ऑफ _ डिफरेंस (कुंजी, entry.get_key ()) एंट्री _ न्यू-मौजूदा प्रविष्टि और नई प्रविष्टि सबनोड _ न्यू-क्रिएट _ नोड (लेवल _ डिफेनस, प्रविष्टि, प्रविष्टि _ न्यू) node.set_entry (एच, सबनोड _ न्यू) के साथ नया सबनोड अगर रिटर्न रिमूव रिमूवल इंसर्शन के विपरीत काम करता है, तो अतिरिक्त बाधा के साथ कि दो से कम प्रविष्टियां रहने पर किसी भी सबनोड को हटाना पड़ता है। शेष प्रविष्टि को मूल नोड में ले जाया जाता है। विंडो प्रश्न विंडोज प्रश्न वे प्रश्न हैं जो आयताकार अक्ष-संरेखित हाइपरबॉक्स के अंदर स्थित सभी कुंजियों को वापस करते हैं। उन्हें द्वि-आयामी बिंदुओं के रूप में परिभाषित किया जा सकता है और जो क्वेरी बॉक्स के "निचले बाएँ" और "ऊपरी दाएँ" कोनों का प्रतिनिधित्व करते हैं। एक तुच्छ कार्यान्वयन एक नोड में सभी प्रविष्टियों को पार करता है (रूट नोड से शुरू होता है) और यदि कोई प्रविष्टि मेल खाती है तो या तो इसे परिणाम सूची में जोड़ता है (यदि यह एक उपयोगकर्ता प्रविष्टि है) या इसे पुनरावर्ती रूप से पार करता है (यदि यह एक सबनोड है)। फ़ंक्शन क्वेरी (नोड, न्यूनतम, अधिकतम, परिणाम _ सूची) फोरैक प्रविष्टि है यदि entry.is_subnode () तो करें यदि entry.get_prefix ()> = न्यूनतम और entry.get_prefix () <= अधिकतम तो क्वेरी (entry.get_subnode (), न्यूनतम, अधिकतम, परिणाम _ सूची) समाप्त हो जाती है यदि अन्यथा यदि entry.get_key ()> = न्यूनतम और entry.get_key () <= अधिकतम तो result_list.add (प्रविष्टि) समाप्त हो जाती है यदि अंत हो जाता है यदि दोहराया जाता है। एक नोड में सभी प्रविष्टियों को पार करने और उनकी तुलना करने में समय की जटिलता होती है क्योंकि-आयामी कुंजी की प्रत्येक तुलना में समय लगता है। चूँकि नोड्स में प्रविष्टियाँ हो सकती हैं, इसलिए यह बढ़ती आयामीता के साथ अच्छी तरह से माप नहीं करता है। हाइपरक्यूब पते का उपयोग करके इस दृष्टिकोण में सुधार करने के कई तरीके हैं। न्यूनतम और अधिकतम विचार चतुर्थांश के पतों के लिए न्यूनतम और अधिकतम मूल्यों को खोजना है ताकि खोज कुछ चतुर्थांशों से बच सके जो क्वेरी बॉक्स के साथ ओवरलैप नहीं करते हैं। मान लीजिए कि यह एक नोड का केंद्र है (यह नोड के उपसर्ग के बराबर है) और प्रत्येक बिट के साथ दो बिट स्ट्रिंग हो। इसके अलावा, और के 's बिट और और' th आयाम को इंगित करने के साथ सदस्यता दें। चलो और। फिर प्रत्येक आयाम के लिए एक "है जहां नोड का" निचला "आधा और इसमें सभी चतुर्थांश क्वेरी बॉक्स के साथ ओवरलैप नहीं करते हैं। इसी तरह, प्रत्येक आयाम के लिए एक "है जहां" ऊपरी "आधा क्वेरी बॉक्स के साथ ओवरलैप नहीं होता है। और फिर एक नोड में सबसे कम और उच्चतम प्रस्तुत करें जिसे पार करने की आवश्यकता है। क्वैरेन्ट्स क्वैरी बॉक्स के साथ प्रतिच्छेद करते हैं या नहीं करते हैं। एक प्रमाण उपलब्ध है। इसके साथ, उपरोक्त क्वैरी फ़ंक्शन में सुधार किया जा सकता हैः फ़ंक्शन क्वैरी (नोड, न्यूनतम, अधिकतम, परिणाम _ सूची) एच _ मिनट है एच _ मिनट एच _ मैक्स की गणना करें प्रत्येक प्रविष्टि के लिए एच _ मैक्स की गणना करें node.get_entries_range (एच _ मिनट, एच _ मैक्स) करें [.] रिपीट रिटर्न गणना और है। एक नोड में कब्जे वाले चतुर्थांश के वितरण के आधार पर यह दृष्टिकोण लगभग सभी प्रमुख तुलनाओं से बचने की अनुमति देगा। इससे औसत यात्रा समय कम हो जाता है लेकिन परिणामी जटिलता अभी भी बनी हुई है। क्वेरी बॉक्स के साथ ओवरलैप के लिए चतुर्थांश की जाँच करें बीच और अभी भी ऐसे चतुर्थांश हो सकते हैं जो क्वेरी बॉक्स के साथ ओवरलैप नहीं करते हैं। विचारः और प्रत्येक में प्रत्येक आयाम के लिए एक बिट होता है जो इंगित करता है कि क्या क्वेरी बॉक्स उस आयाम में नोड के निचले/ऊपरी आधे हिस्से के साथ ओवरलैप करता है। इसका उपयोग यह जल्दी से जांचने के लिए किया जा सकता है कि क्या एक चतुर्थांश-आयामी कुंजी की तुलना किए बिना क्वेरी बॉक्स के साथ ओवरलैप करता हैः एक चतुर्थांश क्वेरी बॉक्स के साथ ओवरलैप करता है यदि प्रत्येक बिट के लिए एक संबंधित बिट है और प्रत्येक बिट के लिए एक संबंधित बिट है। 64 बिट रजिस्टर्स वाले सीपीयू पर इस प्रकार-आयामी कुंजी तक के ओवरलैप की जांच करना संभव है। फलन है _ ओवरलैप (एच, एच _ मिनट, एच _ मैक्स) वापसी है (एच। एच _ मिनट) और एच _ मैक्स = = एच// का मूल्यांकन 'सही' करने के लिए किया जाता है यदि चतुर्थांश और क्वेरी ओवरलैप होते हैं। फ़ंक्शन क्वेरी (नोड, न्यूनतम, अधिकतम, परिणाम _ सूची) h _ min है की गणना करें h _ min h _ गरिष्ठ की गणना करें प्रत्येक प्रविष्टि के लिए h _ अधिकतम की गणना करें node.get_entries_range (h _ मिनट, h _ अधिकतम) h entry.get_h () करें; यदि (h। h _ मिनट) & h _ अधिकतम = = h तो// 'सही' का मूल्यांकन करता है यदि चतुर्थांश और क्वेरी ओवरलैप होती है। [.] अंत अगर दोहराया जाता है तो परिणामी समय जटिलता की तुलना पूर्ण पुनरावृत्ति से की जाती है। ट्रैवर्स क्वाड्रेंट्स जो क्वेरी बॉक्स के साथ ओवरलैप करते हैं बड़े नोड्स के साथ उच्च आयामों के लिए सभी के माध्यम से पुनरावृत्ति से बचना भी संभव है और इसके बजाय सीधे क्वेरी बॉक्स के साथ ओवरलैप होने वाले अगले उच्च की गणना करें। पहला कदम उन सभी चतुर्थांशों के लिए दिए गए "-बिट्स" को रखता है जिनका क्वेरी बॉक्स के साथ कोई ओवरलैप नहीं होता है। दूसरा चरण अनुकूलित और जोड़े गए बिट्स को बढ़ाता है जो एक अतिप्रवाह को ट्रिगर करता है ताकि गैर-अतिव्यापी चतुर्थांश को छोड़ दिया जाए। अंतिम चरण अतिप्रवाह को ट्रिगर करने के लिए उपयोग किए जाने वाले सभी अवांछनीय बिट्स को हटा देता है। तर्क का विस्तार से वर्णन किया गया है। गणना इस प्रकार काम करती हैः फ़ंक्शन वृद्धि _ एच (एच _ इनपुट, एच _ मिनट, एच _ मैक्स) एच _ आउट = एच _ इनपुट। (~ एच _ मैक्स)// पूर्व-मास्क एच _ आउट + = 1// वृद्धि एच _ आउट = (एच _ आउट और एच _ मैक्स)। एच _ मिनट// पोस्ट-मास्क रिटर्न एच _ आउट फिर से, इसके लिए अधिकांश सीपीयू पर किया जा सकता है। एक नोड को पार करने के लिए परिणामी समय जटिलता है। यह सबसे अच्छा काम करता है यदि क्वेरी बॉक्स के साथ ओवरलैप होने वाले अधिकांश चतुर्थांश एक प्रविष्टि के साथ भरे हुए हैं। - निकटतम पड़ोसी निकटतम पड़ोसी खोजों को मानक एल्गोरिदम का उपयोग करके लागू किया जा सकता है। फ़्लोटिंग पॉइंट कीज़ पी. एच.-ट्री केवल पूर्णांक मानों को संग्रहीत कर सकता है। फ्लोटिंग पॉइंट मानों को मामूली रूप से पूर्णांक के रूप में संग्रहीत किया जा सकता है जो उन्हें एक पूर्णांक देते हैं। हालांकि, के लेखक भी सटीकता के नुकसान के बिना एक दृष्टिकोण का प्रस्ताव करते हैं। हानि-रहित रूपांतरण बिना हानि के एक फ्लोटिंग बिंदु मूल्य को एक पूर्णांक मूल्य (और पीछे) में परिवर्तन करना यदि परिशुद्धता केवल फ्लोटिंग बिंदु मूल्य के 32 या 64 बिट्स को एक पूर्णांक (32 या 64 बिट्स के साथ) के रूप में व्याख्या करके प्राप्त की जा सकती है। जिस तरह से आई. ई. ई. ई. 754 फ्लोटिंग पॉइंट मानों को कूटबद्ध करता है, उसके परिणामस्वरूप पूर्णांक मानों में मूल फ्लोटिंग पॉइंट मानों के समान क्रम होता है, कम से कम सकारात्मक मानों के लिए। नकारात्मक मूल्यों के लिए आदेश गैर-हस्ताक्षर बिट्स को उलटकर प्राप्त किया जा सकता है। जावा में उदाहरण कार्यान्वयनः लंबा एनकोड (दोहरा मूल्य) {लंबा r = Double.doubleToRawLongBits (मूल्य); वापसी (r> = 0)? r: r ^ 0x7FffffffffffffffFLFFL;} C + +: std:: int64 _ t एनकोड (दोहरा मान) {std:: int64 _ t r; memcpy (& r, & मान, साइज़ऑफ़ (r)); रिटर्न r> = 0 में उदाहरण कार्यान्वयन? r: r ^ 0x7fffffffffffffffffffffl;} एन्कोडिंग (और व्युत्क्रम डिकोडिंग) सभी फ्लोटिंग पॉइंट मानों के लिए दोषरहित है। आदेश व्यवहार में अच्छी तरह से काम करता है, जिसमें और शामिल है। हालाँकि, पूर्णांक प्रतिनिधित्व भी एक सामान्य तुलनीय मूल्य (अनंत से छोटा) में बदल जाता है, अनंतताएँ एक दूसरे के साथ तुलनीय होती हैं और उससे बड़ी होती हैं। इसका मतलब है कि, उदाहरण के लिए, एक क्वेरी रेंज के मान से मेल नहीं खाएगी। पूछताछ सीमा से मेल खाने के लिए होना आवश्यक है। हाइपरबॉक्स कुंजी मात्रा (अक्ष-संरेखित हाइपर-बॉक्स) को कुंजी के रूप में संग्रहीत करने के लिए, कार्यान्वयन आमतौर पर कोने के प्रतिनिधित्व का उपयोग करते हैं जो एक बॉक्स के दो-आयामी न्यूनतम और अधिकतम कोनों को आयामों के साथ एक ही कुंजी में परिवर्तित करता है, उदाहरण के लिए उन्हें आपस में जोड़करः यह खोज करने, डालने और हटाने के कार्यों के लिए मामूली रूप से काम करता है। विंडो प्रश्नों को-आयामी वैक्टर से-आयामी वैक्टर में परिवर्तित करने की आवश्यकता है। उदाहरण के लिए, एक विंडो क्वैरी के लिए जो क्वैरी बॉक्स के अंदर पूरी तरह से सभी बक्से से मेल खाती है, क्वैरी कुंजी हैंः एक विंडो क्वैरी ऑपरेशन के लिए जो एक क्वैरी बॉक्स के साथ प्रतिच्छेदन करने वाले सभी बक्से से मेल खाती है, क्वैरी कुंजी हैंः मापनीयता प्रविष्टियों से कम के साथ उच्च आयामों में, एक पी. एच.-ट्री में केवल एक ही नोड हो सकता है, जो प्रभावी रूप से जेड-ऑर्डर वक्र के साथ बी-ट्री में "विकृत" हो सकता है। ऐड/रिमूव/लुकअप ऑपरेशन बने रहते हैं और विंडो क्वेरी क्वाड्रेंट फिल्टर का उपयोग कर सकते हैं। हालाँकि, यह आयामीता के अभिशाप से बच नहीं सकता है, क्योंकि उच्च आयामी डेटा के साथ या एक पी. एच.-ट्री पूर्ण स्कैन की तुलना में केवल मामूली रूप से बेहतर है। उपयोग अनुसंधान ने बड़े और तेजी से बदलते डेटासेट के साथ तेजी से जोड़ने/हटाने/सटीक-मिलान संचालन की सूचना दी है। विंडो क्वेरीज़ को विशेष रूप से छोटी खिड़कियों या बड़े डेटासेट के लिए अच्छी तरह से काम करने के लिए दिखाया गया है पी. एच.-ट्री मुख्य रूप से इन-मेमोरी उपयोग के लिए उपयुक्त है। नोड्स का आकार (प्रविष्टियों की संख्या) तय किया जाता है जबकि निरंतर भंडारण डिस्क पर पृष्ठ आकार के साथ नोड आकार को संरेखित करने के लिए विन्यास योग्य नोड आकार के साथ अनुक्रमणिकाओं से लाभान्वित होता है। आर-ट्री जैसे अन्य स्थानिक सूचकांकों के साथ यह आसान है। कार्यान्वयन जावाः मूल आविष्कारक सी + + द्वारा गिटहब रिपॉजिटरीः मूल आविष्कारक सी + + द्वारा गिटहब रिपॉजिटरीः गिटहब रिपॉजिटरी सी + +: गिटहब रिपॉजिटरी भी देखें द्विआधारी स्थान विभाजन द्विआधारी टाइलिंग के-डी ट्री ऑक्ट्री क्वाडट्री आर-ट्री यूबी-ट्री स्थानिक डेटाबेस बाहरी लिंक विस्तृत विवरण, उदाहरण और प्रदर्शन तुलना के साथ पीएच-ट्री वेबसाइट संदर्भ पेड़ (डेटा संरचना) डेटाबेस सूचकांक तकनीक ज्यामितीय डेटा संरचनाएँ