PH-tree
பி. எச்-மரம் என்பது புவியியல் ஆயத்தொலைவுகள், புள்ளிகள், அம்ச திசையன்கள், செவ்வகங்கள் அல்லது எல்லை பெட்டிகள் போன்ற பல பரிமாண தரவுகளின் (விசைகள்) இடஞ்சார்ந்த குறியீட்டிற்கு பயன்படுத்தப்படும் ஒரு மர தரவு அமைப்பு ஆகும். பி. எச்-மரம் என்பது ஒரு குவாட்ர்ரீ அல்லது ஆக்ட்ரீ போன்ற கட்டமைப்பைக் கொண்ட விண்வெளி பகிர்வு குறியீடாகும். இருப்பினும், நாற்கரங்களைப் போலல்லாமல், இது முயற்சிகளின் அடிப்படையில் ஒரு பிரிப்புக் கொள்கையைப் பயன்படுத்துகிறது மற்றும் கிரிட் பிட் மரங்களைப் போன்றது, இது விசைகளின் பிட்-பிரதிநிதித்துவத்தை அடிப்படையாகக் கொண்டது. பிட் அடிப்படையிலான பிரிப்புக் கொள்கை, முனைகளுக்கான வெவ்வேறு உள் பிரதிநிதித்துவங்களைப் பயன்படுத்தும்போது, உயர் பரிமாண தரவுகளுடன் அளவிடுதலை வழங்குகிறது. பிட்-பிரதிநிதித்துவ பிரிப்புக் கொள்கையும் அதிகபட்ச ஆழத்தை விதிக்கிறது, இதனால் சீரழிந்த மரங்கள் மற்றும் மறு சமநிலைப்படுத்தலின் தேவையைத் தவிர்க்கிறது. கண்ணோட்டம் அடிப்படை PH-மரம் என்பது ஒரு இடஞ்சார்ந்த குறியீடாகும், இது விசைகளை வரைபடமாக்குகிறது, அவை முழு எண்களுடன்-பரிமாண திசையன்கள், பயனர் வரையறுக்கப்பட்ட மதிப்புகளுக்கு. PH-மரம் என்பது ஒரு கிரிட் பிட் மரத்தின் பல பரிமாண பொதுமைப்படுத்தலாகும், அதாவது ஒரு கிரிட் பிட் மரம்-பரிமாண விசைகளைக் கொண்ட ஒரு PH-மரத்திற்கு சமம். கிரிட் பிட் மரத்தைப் போலவே, மற்ற இடஞ்சார்ந்த குறியீடுகளைப் போலல்லாமல், பி. எச்-மரம் ஒரு மல்டிமேப்பை விட ஒரு வரைபடமாகும். ஒரு பரிமாண பி. எச்-மரம் என்பது முனைகளின் மரமாகும், அங்கு ஒவ்வொரு முனை பகிர்வுகளும் இடத்தை நாற்கரங்களாகப் பிரிக்கின்றன (உயர் பரிமாண தரவுகளுடன் பெரிய முனைகள் எவ்வளவு அளவிடப்படுகின்றன என்பதைக் கீழே காண்க). ஒவ்வொரு நாற்கரத்திலும் அதிகபட்சம் ஒரு நுழைவு உள்ளது, ஒன்று விசை-மதிப்பு ஜோடி (இலை நாற்கர) அல்லது ஒரு விசை-துணை முனை ஜோடி. ஒரு விசை-துணை முனை ஜோடிக்கு, விசை துணை முனையின் மையத்தைக் குறிக்கிறது. சப்னோட் மற்றும் அதன் சைல்ட் சப்னோட்களில் உள்ள அனைத்து விசைகளின் பொதுவான முன்னொட்டு (பிட்-பிரதிநிதித்துவம்) கூட முக்கியமாகும். ஒவ்வொரு முனையிலும் குறைந்தது இரண்டு உள்ளீடுகள் உள்ளன, இல்லையெனில் அது தாய் முனையுடன் இணைக்கப்படுகிறது. PH-மரங்களின் வேறு சில கட்டமைப்பு பண்புகள் பின்வருமாறுஃ அவை-ஆரி மரங்கள். அவை இயல்பாகவே சமநிலையற்றவை, ஆனால் அவற்றின் ஆழம் விசைகளின் பிட் அகலத்திற்கு மட்டுப்படுத்தப்பட்டிருப்பதால் சமநிலையின்மை குறைவாக உள்ளது, எ. கா. 32 பிட் முழு எண்களைக் கொண்ட ஒரு பரிமாண விசைக்கு 32. செருகுதல் அல்லது அகற்றுதல் செயல்பாடுகள் சரியாக ஒரு முனை மாற்றியமைக்கப்படுவதற்கும், இரண்டாவது முனை சேர்க்கப்படுவதற்கும் அல்லது அகற்றப்படுவதற்கும் காரணமாகின்றன. இது ஒரே நேரத்தில் செயல்படுத்துவதற்கு பயனுள்ளதாக இருக்கும். இது மாற்றும் செலவில் சிறிய மாறுபாட்டைக் குறிக்கிறது. அவற்றின் அமைப்பு செருகுதல்/அகற்றுதல் வரிசையில் இருந்து சுயாதீனமாக உள்ளது. பிளவு உத்தி பெரும்பாலான நாற்கரங்களைப் போலவே, PH-மரம் என்பது முனைகளின் படிநிலையாகும், அங்கு ஒவ்வொரு முனையும் அனைத்து பரிமாணங்களிலும் இடத்தை பிரிக்கிறது. எனவே, ஒரு முனை ஒவ்வொரு நாற்கரத்திற்கும் ஒரு துணை முனைகள் வரை இருக்கலாம். நாற்கர எண் PH-மரம் மரத்தில் அவற்றின் நிலையை தீர்மானிக்க பல பரிமாண விசைகளின் பிட்களைப் பயன்படுத்துகிறது. ஒரே முன்னணி பிட்களைக் கொண்ட அனைத்து விசைகளும் மரத்தின் ஒரே கிளையில் சேமிக்கப்படுகின்றன. எடுத்துக்காட்டாக, மட்டத்தில் உள்ள ஒரு முனையில், ஒரு விசையை எங்கு செருக வேண்டும் (அல்லது அகற்ற வேண்டும் அல்லது மேலே பார்க்க வேண்டும்) என்பதைத் தீர்மானிக்க, அது விசையின் ஒவ்வொரு பரிமாணத்தின் s பிட்டையும் பார்க்கிறது. 8 நாற்கரங்களைக் கொண்ட ஒரு 3டி முனையைப் பொறுத்தவரை (ஒரு கனசதுரத்தை உருவாக்குகிறது) விசையின் முதல் பரிமாணத்தின் 's பிட் இலக்கு நாற்கரமானது கனசதுரத்தின் இடது அல்லது வலதுபுறத்தில் உள்ளதா என்பதை தீர்மானிக்கிறது, இரண்டாவது பரிமாணத்தின்' s பிட் அது முன் அல்லது பின்புறத்தில் உள்ளதா என்பதை தீர்மானிக்கிறது, மூன்றாவது பரிமாணத்தின் 's பிட் கீழே மற்றும் மேலே தீர்மானிக்கிறது, படத்தைப் பார்க்கவும். 1டி எடுத்துக்காட்டு 8 பிட் மதிப்புகளுடன் மூன்று 1டி விசைகளுடன் எடுத்துக்காட்டுஃ, மற்றும். ஒரு வெற்று மரத்துடன் சேர்ப்பது ஒரு ஒற்றை முனையை விளைவிக்கிறது. இரண்டு விசைகளும் முதலில் அவற்றின் 6 வது பிட்டில் வேறுபடுகின்றன, எனவே முனைக்கு ஒரு நிலை உள்ளது (0 இல் தொடங்கி). முனை இரண்டு விசைகளின் பொதுவான 5 பிட்களைக் குறிக்கும் 5 பிட் முன்னொட்டு உள்ளது. முனை இரண்டு நாற்கரங்களைக் கொண்டுள்ளது, ஒவ்வொரு விசையும் ஒரு நாற்கரத்தில் சேமிக்கப்படுகிறது. மூன்றாவது விசையை ஒரு கூடுதல் முனையில் சேர்ப்பதன் மூலம், ஒரு நாற்கரத்தில் அசல் முனை துணை முனையாகவும், மற்றொரு நாற்கரத்தில் புதிய விசையும் உள்ளது. 2டி எடுத்துக்காட்டு 2டி விசைகளுடன் ஒவ்வொரு முனையிலும் நாற்கரங்கள் உள்ளன. ஒரு விசை சேமிக்கப்படும் நாற்கரத்தின் நிலை விசைகளின் அந்தந்த பிட்களிலிருந்து பிரித்தெடுக்கப்படுகிறது, ஒவ்வொரு பரிமாணத்திலிருந்தும் ஒரு பிட். முனையின் நான்கு நாற்கரங்கள் ஒரு 2டி ஹைபர்கியூபை உருவாக்குகின்றன (நாற்கரங்கள் காலியாக இருக்கலாம்). விசைகளிலிருந்து பிரித்தெடுக்கப்படும் பிட்கள் ஹைபர்கியூப் முகவரியை உருவாக்குகின்றன, for மற்றும் for. முனையின் ஹைபர்கியூபில் உள்ள நாற்கரத்தின் நிலை திறம்பட உள்ளது. முனை அமைப்பு ஒரு முனையில் உள்ள உள்ளீடுகளின் வரிசைமுறை எப்போதும் இசட்-வரிசையைப் பின்பற்றுகிறது. எடுத்துக்காட்டாக, ஒரு முனையில் உள்ள உள்ளீடுகள் நிலையான அளவு வரிசைகளில் சேமிக்கப்படலாம். பின்னர் திறம்பட ஒரு நாற்கரத்தின் வரிசை குறியீடாகும். இது தேட, செருக மற்றும் அகற்ற அனுமதிக்கிறது மற்றும் சேமிக்க வேண்டிய அவசியமில்லை. இருப்பினும், விண்வெளி சிக்கலானது ஒரு முனையில் உள்ளது, எனவே இது உயர் பரிமாண தரவுகளுக்கு குறைவாகவே பொருத்தமானது. மற்றொரு தீர்வு, மாறும் வரிசைகள் மற்றும்/அல்லது பி-மரங்கள் போன்ற வரிசைப்படுத்தப்பட்ட சேகரிப்பில் உள்ளீடுகளை சேமிப்பதாகும். இது தேடுதல் செயல்பாடுகளை மெதுவாக்குகிறது, ஆனால் நினைவக நுகர்வு மெதுவாக்குகிறது. குறைந்த நினைவகத்தைப் பயன்படுத்துவதைப் பொறுத்து நிலையான மற்றும் மாறும் வரிசை பிரதிநிதித்துவத்திற்கு இடையில் மாறுவதன் மூலம் குறைந்தபட்ச நினைவக நுகர்வை நோக்கமாகக் கொண்ட அசல் செயல்படுத்தல். மற்ற செயல்பாடுகள் மாறும் வகையில் மாறுவதில்லை, ஆனால் உயர் பரிமாண தரவுகளுக்கு நிலையான வரிசைகள், மாறும் வரிசைகள் மற்றும் பி-மரங்களைப் பயன்படுத்துகின்றன. செயல்பாடுகள் தேடல், செருகுதல் மற்றும் அகற்றுதல் செயல்பாடுகள் அனைத்தும் மிகவும் ஒத்ததாக செயல்படுகின்றனஃ சரியான முனையைக் கண்டுபிடித்து, பின்னர் முனையில் செயல்பாட்டைச் செய்யுங்கள். சாளர வினவல்கள் மற்றும் அருகிலுள்ள அண்டை தேடல்கள் மிகவும் சிக்கலானவை. தேடல் செயல்பாடு மரத்தில் ஒரு விசை இருக்கிறதா என்பதை தீர்மானிக்கிறது. இது மரத்தின் கீழே நடந்து சென்று ஒவ்வொரு முனையிலும் ஒரு கேண்டிடேட் சப்நோட் உள்ளதா அல்லது விசையுடன் பொருந்தக்கூடிய பயனர் மதிப்பு உள்ளதா என்பதை சரிபார்க்கிறது. செயல்பாடு தேடல் (விசை) என்பது உள்ளீடு, மரம் காலியாக இல்லாவிட்டால், ரூட் உள்ளீட்டில் ஒரு ரூட் முனை இருக்கும் போது உள்ளீடு! = NIL & & & entry.is_subnode () முனை செய்யுங்கள், முனையம், entry.get_node (விசை), மீண்டும் திரும்ப உள்ளீடு,// உள்ளீடு, NIL செயல்பாடாக இருக்கலாம், பெறுதல், (விசை) முனை, தற்போதைய முனை, h, பிரித்தெடுத்தல், பிட்ஸ், ஆழம், (விசை, node.get_depth ()), உள்ளீடு, node.get_entry_at (h), திரும்ப உள்ளீடு,// உள்ளீடு, NIL செருகல் செயல்பாடு, மரத்தில் ஒரு புதிய விசை-மதிப்பு ஜோடியை அவை விசை ஏற்கனவே இல்லாவிட்டால் செருகுகிறது. செயல்பாடு தேடல் செயல்பாட்டைப் போல மரத்தை கடந்து செல்கிறது, பின்னர் விசையை முனையில் செருகுகிறது. கருத்தில் கொள்ள வேண்டிய பல நிகழ்வுகள் உள்ளனஃ நாற்கரமானது காலியாக உள்ளது, மேலும் நாற்கரத்திற்குள் ஒரு புதிய உள்ளீட்டைச் செருகலாம் மற்றும் திரும்பலாம். நான்கில் புதிய உள்ளீட்டைப் போன்ற ஒரு விசையுடன் ஒரு பயனர் உள்ளீடு உள்ளது. அத்தகைய மோதலைச் சமாளிப்பதற்கான ஒரு வழி, தோல்வியுற்ற செருகலைக் குறிக்கும் ஒரு கொடியைத் திருப்பித் தருவதாகும். மரமானது முனையின் உள்ளீடாக ஒரு சேகரிப்புடன் பல வரைபடமாக செயல்படுத்தப்பட்டால், புதிய மதிப்பு அந்த சேகரிப்பில் சேர்க்கப்படும். நாற்கரத்தில் வேறு விசையுடன் ஒரு உள்ளீடு (பயனர் உள்ளீடு அல்லது துணை முனை உள்ளீடு) உள்ளது. இந்த வழக்கில் பழைய மற்றும் புதிய உள்ளீட்டை வைத்திருக்கும் புதிய துணை முனையுடன் ஏற்கனவே உள்ள உள்ளீட்டை மாற்ற வேண்டும். செயல்பாட்டு செருகல் (முனை, விசை, மதிப்பு) நிலை node.get_level ()// நிலை என்பது மூலத்திற்கு 0 ஆகும் h → பிரித்தெடுக்கும் _ பிட்கள் _ அட் _ நிலை (விசை, நிலை) நுழைவு node.get_entry (h) உள்ளீடு = = நிலையாக இருந்தால்// வழக்கு 1. உள்ளீடு _ புதியது _ உருவாக்க _ நுழைவு (விசை, மதிப்பு) node.set_entry (h, நுழைவு _ புதியது) இல்லையென்றால்! entry.is_subnode () & & entry.get_key () = = விசை பின்னர்// வழக்கு 2. மோதல், ஏற்கனவே ஒரு நுழைவு ரிட்டர்ன் உள்ளது-தோல்வியுற்ற _ செருகல் மற்ற// வழக்கு 3. நிலை _ வேறுபாடு-பெற _ நிலை _ வேறுபாடு (விசை, entry.get_key ()) உள்ளீடு-புதிய-உருவாக்கு _ நுழைவு (விசை, மதிப்பு)// புதிய துணை முனை ஏற்கனவே உள்ள நுழைவு மற்றும் புதிய நுழைவு சப்நோட்-புதிய-உருவாக்கு _ முனை (நிலை _ வேறுபாடு, நுழைவு, நுழைவு _ புதிய) node.set_entry (h, சப்நோட் _ புதிய) முடிவு-திரும்ப நீக்குதல்-நீக்குதல்-செருகுவதற்கு நேர்மாறாக வேலை செய்தால், இரண்டு உள்ளீடுகளுக்கு குறைவாக இருந்தால் எந்த துணை முனையையும் அகற்ற வேண்டும் என்ற கூடுதல் தடையுடன். மீதமுள்ள உள்ளீடு பெற்றோர் முனைக்கு நகர்த்தப்படுகிறது. விண்டோஸ் வினவல்கள் என்பது செவ்வக அச்சு-சீரமைக்கப்பட்ட ஹைப்பர் பாக்ஸுக்குள் இருக்கும் அனைத்து விசைகளையும் திருப்பித் தரும் வினவல்கள் ஆகும். அவை இரு பரிமாண புள்ளிகளாக வரையறுக்கப்படலாம் மற்றும் அவை வினவல் பெட்டியின் "கீழ் இடது" மற்றும் "மேல் வலது" மூலைகளைக் குறிக்கின்றன. ஒரு அற்பமான செயல்படுத்தல் ஒரு முனையில் உள்ள அனைத்து உள்ளீடுகளையும் கடந்து செல்கிறது (ரூட் முனையில் தொடங்கி) மற்றும் ஒரு உள்ளீடு பொருந்தினால் அதை முடிவு பட்டியலில் சேர்க்கிறது (இது ஒரு பயனர் உள்ளீடாக இருந்தால்) அல்லது அதை மீண்டும் மீண்டும் கடந்து செல்கிறது (இது ஒரு துணை முனையாக இருந்தால்). செயல்பாட்டு வினவல் (முனை, குறைந்தபட்சம், அதிகபட்சம், முடிவு _ பட்டியல்) என்பது முன்கூட்டிய உள்ளீடு node.get_entries () என்றால் entry.is_subnode () செய்தால், பின்னர் entry.get_prefix ()> = குறைந்தபட்சம் மற்றும் entry.get_prefix () <= அதிகபட்சம் என்றால் வினவல் (entry.get_subnode (), குறைந்தபட்சம், அதிகபட்சம், முடிவு _ பட்டியல்) முடிவடைகிறது, இல்லையெனில் entry.get_key ()> = குறைந்தபட்சம் மற்றும் entry.get_key () <= அதிகபட்சம் என்றால், result_list.add (நுழைவு) முடிவடைந்தால் முடிவடையும் வினவல் நேர சிக்கலை துல்லியமாக மதிப்பிடுவதற்கு பகுப்பாய்வு பரிமாணத்தை சேர்க்க வேண்டும். ஒரு முனையில் உள்ள அனைத்து உள்ளீடுகளையும் கடந்து சென்று ஒப்பிடுவது நேர சிக்கலைக் கொண்டுள்ளது, ஏனெனில்-பரிமாண விசையின் ஒவ்வொரு ஒப்பீடும் நேரம் எடுக்கும். முனைகள் வரை உள்ளீடுகளைக் கொண்டிருக்கலாம் என்பதால், இது அதிகரிக்கும் பரிமாணத்துடன் சரியாக அளவிடப்படுவதில்லை. ஹைபர்கியூப் முகவரியைப் பயன்படுத்துவதன் மூலம் இந்த அணுகுமுறையை எவ்வாறு மேம்படுத்தலாம் என்பதற்கு பல்வேறு வழிகள் உள்ளன. குறைந்தபட்சம் & அதிகபட்சம் தேடல் வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இல்லாத சில நாற்கரங்களைத் தவிர்க்கக்கூடிய வகையில் நாற்கரத்தின் முகவரிகளுக்கான குறைந்தபட்ச மற்றும் அதிகபட்ச மதிப்புகளைக் கண்டுபிடிப்பதே யோசனை. ஒரு முனையின் மையமாக இருக்கட்டும் (இது முனையின் முன்னொட்டுக்கு சமம்) மற்றும் ஒவ்வொரு பிட்களுடன் இரண்டு பிட் சரங்களாக இருக்கட்டும். மேலும், சப்ஸ்கிரிப்ட் 's பிட் மற்றும் மற்றும்' th பரிமாணத்தை குறிக்கட்டும். மற்றும் விடுங்கள். பின்னர் ஒவ்வொரு பரிமாணத்திற்கும் ஒரு "உள்ளது, அங்கு முனையின்" கீழ் "பாதி மற்றும் அதில் உள்ள அனைத்து நாற்கரங்களும் வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இல்லை. இதேபோல், "மேல்" பாதி வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இல்லாத ஒவ்வொரு பரிமாணத்திற்கும் ஒரு "உள்ளது. பின்னர் கடந்து செல்ல வேண்டிய ஒரு முனையில் மிகக் குறைந்த மற்றும் மிக உயர்ந்ததை வழங்கவும். வினவல் பெட்டியில் உள்ள அல்லது இல்லாத நாற்கரங்கள் குறுக்கிடுகின்றன. இதற்கு ஒரு சான்று உள்ளது. இதன் மூலம், மேலே உள்ள வினவல் செயல்பாட்டை பின்வருவனவாக மேம்படுத்தலாம்ஃ செயல்பாட்டு வினவல் (முனை, குறைந்தபட்சம், அதிகபட்சம், முடிவு _ பட்டியல்) என்பது h _ min ஆகும். ஒரு முனையில் ஆக்கிரமிக்கப்பட்ட நாற்கரங்களின் விநியோகத்தைப் பொறுத்து இந்த அணுகுமுறை இல்லை முதல் கிட்டத்தட்ட அனைத்து முக்கிய ஒப்பீடுகளையும் தவிர்க்க அனுமதிக்கும். இது சராசரி பயண நேரத்தைக் குறைக்கிறது, ஆனால் இதன் விளைவாக ஏற்படும் சிக்கலானது இன்னும் உள்ளது. வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இணைவதற்கான நாற்கரங்களை சரிபார்க்கவும் மற்றும் வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இணைக்காத நாற்கரங்கள் இன்னும் இருக்கலாம். யோசனைஃ ஒவ்வொரு பரிமாணத்திற்கும் ஒரு பிட் உள்ளது, இது வினவல் பெட்டி அந்த பரிமாணத்தில் ஒரு முனையின் கீழ்/மேல் பாதியுடன் ஒன்றுடன் ஒன்று இணைகிறதா என்பதைக் குறிக்கிறது. பரிமாண விசைகளை ஒப்பிடாமல் வினவல் பெட்டியில் ஒரு குவாட்ரன்ட் ஒன்றுடன் ஒன்று பொருந்துகிறதா என்பதை விரைவாக சரிபார்க்க இதைப் பயன்படுத்தலாம்ஃ ஒவ்வொரு பிட்டுக்கும் ஒரு தொடர்புடைய பிட் இருந்தால் ஒரு குவாட்ரன்ட் வினவல் பெட்டியில் ஒன்றுடன் ஒன்று இணைகிறது மற்றும் ஒவ்வொரு பிட்டுக்கும் ஒரு தொடர்புடைய பிட் உள்ளது. 64 பிட் பதிவேடுகளைக் கொண்ட ஒரு CPU இல், பரிமாண விசைகள் வரை ஒன்றுடன் ஒன்று இருப்பதை சரிபார்க்க முடியும். செயல்பாடு _ ஓவர்லாப் (எச், எச் _ மின், எச் _ மேக்ஸ்) என்பது ரிட்டர்ன் (எச் | எச் _ மின்) & எச் _ மேக்ஸ் = = எச்// என்பது நாற்கர மற்றும் வினவல் ஒன்றுடன் ஒன்று இருந்தால் 'உண்மை' என்று மதிப்பிடப்படுகிறது. செயல்பாட்டு வினவல் (முனை, குறைந்தபட்சம், அதிகபட்சம், முடிவு _ பட்டியல்) என்பது h _ min-h _ mx-ஐக் கணக்கிடுவது-ஒவ்வொரு உள்ளீட்டிற்கும் h _ mx-ஐக் கணக்கிடுவது-node.get_entries_range (h _ min, h _ mx)-h-entry.get_h (); (h | h _ min) & h _ mx = = h என்றால்// நான்கு மடங்கு மற்றும் வினவல் ஒன்றுடன் ஒன்று இருந்தால் 'உண்மை' என்று மதிப்பிடப்படுகிறது. [.] முடிவு என்றால் மீண்டும் திரும்பும் இதன் விளைவாக வரும் நேர சிக்கலானது முழு மறு செய்கையுடன் ஒப்பிடப்படுகிறது. பெரிய முனைகளுடன் கூடிய உயர் பரிமாணங்களுக்கு, அனைத்தின் வழியாகவும் மீண்டும் மீண்டும் செய்வதைத் தவிர்க்கவும், அதற்கு பதிலாக வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று அடுத்த உயர் அளவை நேரடியாகக் கணக்கிடவும் முடியும். முதல் படி வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இல்லாத அனைத்து நாற்கரங்களுக்கும் கொடுக்கப்பட்ட-பிட்களை வைக்கிறது. இரண்டாவது படி மாற்றியமைக்கப்பட்ட மற்றும் சேர்க்கப்பட்ட "-பிட்களை அதிகரிக்கிறது, இதனால் ஓவர்ஃப்ளோவைத் தூண்டுகிறது, இதனால் ஓவர்லாப்பிங் அல்லாத நாற்கரங்கள் தவிர்க்கப்படுகின்றன. கடைசி படி நிரம்பி வழிவதைத் தூண்டுவதற்கு பயன்படுத்தப்படும் அனைத்து விரும்பத்தகாத பிட்களையும் நீக்குகிறது. தர்க்கம் விரிவாக விவரிக்கப்பட்டுள்ளது. கணக்கீடு பின்வருமாறு செயல்படுகிறதுஃ செயல்பாட்டு அதிகரிப்பு _ எச் (எச் _ உள்ளீடு, எச் _ மின், எச் _ மேக்ஸ்) என்பது எச் _ அவுட் = எச் _ உள்ளீடு | (~ எச் _ மேக்ஸ்)// முன்-முகமூடி எச் _ அவுட் + = 1// அதிகரிப்பு எச் _ அவுட் = (எச் _ அவுட் & எச் _ மேக்ஸ்) | எச் _ மின்// போஸ்ட்-முகமூடி ரிட்டர்ன் எச் _ அவுட் மீண்டும், இதற்காக பெரும்பாலான சிபியுக்களில் இதைச் செய்யலாம். ஒரு முனையைக் கடந்து செல்வதற்கான நேர சிக்கலானது. வினவல் பெட்டியுடன் ஒன்றுடன் ஒன்று இருக்கும் பெரும்பாலான நாற்கரங்கள் ஒரு உள்ளீட்டை ஆக்கிரமித்திருந்தால் இது சிறப்பாக செயல்படும். - அருகிலுள்ள அண்டை பக்கத் தேடல்களை நிலையான வழிமுறைகளைப் பயன்படுத்தி செயல்படுத்தலாம். மிதக்கும் புள்ளி விசைகள் PH-மரம் மட்டுமே முழு எண் மதிப்புகளை சேமிக்க முடியும். மிதக்கும் புள்ளி மதிப்புகள் அவற்றை ஒரு முழு எண்ணாக இடும் முழு எண்களாக அற்பமாக சேமிக்கப்படலாம். இருப்பினும், அதன் ஆசிரியர்கள் துல்லியத்தை இழக்காமல் ஒரு அணுகுமுறையை முன்மொழிகின்றனர். இழப்பற்ற மாற்றம் இழப்பற்ற ஒரு மிதக்கும் புள்ளி மதிப்பை இழப்பு இல்லாமல் ஒரு முழு எண் மதிப்பாக (மற்றும் பின்னோக்கி) மாற்றுவது, மிதக்கும் புள்ளி மதிப்பின் 32 அல்லது 64 பிட்களை ஒரு முழு எண்ணாக (32 அல்லது 64 பிட்களுடன்) வெறுமனே விளக்கினால் துல்லியத்தை அடைய முடியும். IEEE 754 மிதக்கும் புள்ளி மதிப்புகளைக் குறியாக்கம் செய்யும் விதத்தின் காரணமாக, இதன் விளைவாக வரும் முழு எண் மதிப்புகள் குறைந்தபட்சம் நேர்மறை மதிப்புகளுக்கு, அசல் மிதக்கும் புள்ளி மதிப்புகளின் அதே வரிசையைக் கொண்டுள்ளன. சைன் அல்லாத பிட்களை தலைகீழாக மாற்றுவதன் மூலம் எதிர்மறை மதிப்புகளுக்கான ஆர்டரை அடைய முடியும். ஜாவாவில் எடுத்துக்காட்டு செயல்படுத்தல்கள்ஃ நீண்ட குறியீடு (இரட்டை மதிப்பு) {நீண்ட r = Double.doubleToRawLongBits (மதிப்பு); திரும்ப (r> = 0)? r: r ^ 0x7FffffffffffffFLFFL;} C + + இல் எடுத்துக்காட்டு செயல்படுத்தல்கள்ஃ std:: int64 _ t குறியாக்கம் (இரட்டை மதிப்பு) {std:: int64 _ t r; memcpy (& r, & மதிப்பு, அளவை (r)); திரும்ப r> = 0? r: r ^ 0x7எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எஃப்எல்;} குறியாக்கம் (மற்றும் தலைகீழ் டிகோடிங்) அனைத்து மிதக்கும் புள்ளி மதிப்புகளுக்கும் இழப்பற்றது. ஆர்டர் செய்வது நடைமுறையில் நன்றாக வேலை செய்கிறது, மற்றும் உட்பட. இருப்பினும், முழு எண் பிரதிநிதித்துவம் ஒரு சாதாரண ஒப்பிடக்கூடிய மதிப்பாக மாறுகிறது (முடிவிலியை விட சிறியது), முடிவிலிகள் ஒருவருக்கொருவர் ஒப்பிடத்தக்கவை மற்றும் அதை விட பெரியவை. அதாவது, எடுத்துக்காட்டாக, ஒரு வினவல் வரம்பு ஒரு மதிப்புடன் பொருந்தாது. வினவல் வரம்புடன் பொருந்துவதற்கு இருக்க வேண்டும். ஹைப்பர்பாக்ஸ் விசைகள் தொகுதிகளை (அச்சு-சீரமைக்கப்பட்ட ஹைப்பர்-பாக்ஸ்கள்) விசைகளாக சேமிக்க, செயல்படுத்தல்கள் பொதுவாக மூலையில் பிரதிநிதித்துவத்தைப் பயன்படுத்துகின்றன, இது ஒரு பெட்டியின் இரு பரிமாண குறைந்தபட்ச மற்றும் அதிகபட்ச மூலைகளை பரிமாணங்களுடன் ஒற்றை விசையாக மாற்றுகிறது, எடுத்துக்காட்டாக அவற்றை ஒன்றோடொன்று இணைப்பதன் மூலம்ஃ தேடுதல், செருகுதல் மற்றும் அகற்றுதல் செயல்பாடுகளுக்கு இது அற்பமாக வேலை செய்கிறது. சாளர வினவல்களை-பரிமாண திசையன்களிலிருந்து-பரிமாண திசையன்களாக மாற்ற வேண்டும். எடுத்துக்காட்டாக, வினவல் பெட்டிக்குள் உள்ள அனைத்து பெட்டிகளுடனும் பொருந்தக்கூடிய ஒரு சாளர வினவலுக்கு, வினவல் விசைகள் பின்வருமாறுஃ வினவல் பெட்டியுடன் சந்திக்கும் அனைத்து பெட்டிகளுடன் பொருந்தக்கூடிய ஒரு சாளர வினவல் செயல்பாட்டிற்கு, வினவல் விசைகள் பின்வருமாறுஃ அளவிடுதல் உள்ளீடுகளை விட குறைவான உயர் பரிமாணங்களில், ஒரு PH-மரம் ஒரே ஒரு முனையைக் கொண்டிருக்கலாம், இது Z-வரிசை வளைவுடன் ஒரு B-மரமாக திறம்பட "சீரழிகிறது". சேர்/அகற்ற/தேடல் செயல்பாடுகள் உள்ளன மற்றும் சாளர வினவல்கள் நாற்கர வடிப்பான்களைப் பயன்படுத்தலாம். இருப்பினும், இது பரிமாணத்தின் சாபத்தைத் தவிர்க்க முடியாது, ஏனெனில் உயர் பரிமாண தரவு அல்லது ஒரு PH-மரம் ஒரு முழு ஸ்கேன் விட ஓரளவு மட்டுமே சிறந்தது. பெரிய மற்றும் வேகமாக மாறிவரும் தரவுத்தொகுப்புகளுடன் விரைவான சேர்ப்பு/நீக்கம்/துல்லியமான-பொருத்தம் செயல்பாடுகளை பயன்பாட்டு ஆராய்ச்சி தெரிவித்துள்ளது. சாளர வினவல்கள் குறிப்பாக சிறிய சாளரங்கள் அல்லது பெரிய தரவுத்தொகுப்புக்கு நன்றாக வேலை செய்வதாக காட்டப்பட்டுள்ளது. பி. எச்-மரம் முக்கியமாக நினைவக பயன்பாட்டிற்கு பொருத்தமானது. முனைகளின் அளவு (உள்ளீடுகளின் எண்ணிக்கை) சரிசெய்யப்பட்டுள்ளது, அதே நேரத்தில் தொடர்ச்சியான சேமிப்பு வட்டில் உள்ள பக்க அளவுடன் முனை அளவை சீரமைக்க உள்ளமைக்கக்கூடிய முனை அளவைக் கொண்ட குறியீடுகளிலிருந்து பயனடைகிறது. ஆர்-மரங்கள் போன்ற பிற இடஞ்சார்ந்த குறியீடுகளுடன் இது எளிதானது. செயல்பாடுகள் ஜாவாஃ அசல் கண்டுபிடிப்பாளர் சி + + இன் கிட்ஹப் களஞ்சியம்ஃ அசல் கண்டுபிடிப்பாளர் சி + + இன் கிட்ஹப் களஞ்சியம்ஃ கிட்ஹப் களஞ்சியம் சி + +: கிட்ஹப் களஞ்சியம் மேலும் காண்க பைனரி ஸ்பேஸ் பகிர்வு பைனரி டைலிங் கே-டி ட்ரீ ஆக்ட்ரீ குவாட்ர்ரீ ஆர்-ட்ரீ யு. பி-ட்ரீ இடஞ்சார்ந்த தரவுத்தளம் வெளிப்புற இணைப்புகள் பி. எச்-ட்ரீ வலைத்தளத்துடன் விரிவான விளக்கம், எடுத்துக்காட்டுகள் மற்றும் செயல்திறன் ஒப்பீடு குறிப்புகள் மரங்கள் (தரவு கட்டமைப்புகள்) தரவுத்தள குறியீட்டு நுட்பங்கள் வடிவியல் தரவு கட்டமைப்புகள்