Bx-tree
கணினி அறிவியலில், பிஎக்ஸ் மரம் என்பது நகரும் பொருட்களுக்கான திறமையான பி + மரம் அடிப்படையிலான குறியீட்டு கட்டமைப்புகளை புதுப்பிக்கப் பயன்படுத்தப்படும் ஒரு வினவலாகும். குறியீட்டு அமைப்பு Bx-மரத்தின் அடிப்படை அமைப்பு ஒரு B + மரமாகும், இதில் உள் முனைகள் ஒரு கோப்பகமாக செயல்படுகின்றன, ஒவ்வொன்றும் அதன் வலது உடன்பிறப்புக்கு ஒரு சுட்டியைக் கொண்டுள்ளன. Bx-மரத்தின் முந்தைய பதிப்பில், இலை முனைகளில் நகரும்-பொருள் இருப்பிடங்கள் குறியிடப்பட்டு அதனுடன் தொடர்புடைய குறியீட்டு நேரம் இருந்தது. உகந்த பதிப்பில், ஒவ்வொரு இலை முனை உள்ளீட்டிலும் ஐடி, வேகம், ஒற்றை பரிமாண மேப்பிங் மதிப்பு மற்றும் பொருளின் சமீபத்திய புதுப்பிப்பு நேரம் ஆகியவை உள்ளன. நகரும் பொருட்களின் இருப்பிடங்களை சேமிக்காமல் இருப்பதன் மூலம் ஃபேன்அவுட் அதிகரிக்கப்படுகிறது, ஏனெனில் இவை மேப்பிங் மதிப்புகளிலிருந்து பெறப்படலாம். நகரும் பொருள்களுக்கு B + மரத்தைப் பயன்படுத்துதல் பல நகரும் பொருள்களின் குறியீடுகளைப் பொறுத்தவரை, ஒரு இரு பரிமாண நகரும் பொருள் O = (x, y), (vx, vy), t) என ஒரு நேரியல் செயல்பாடாக வடிவமைக்கப்பட்டுள்ளது, இதில் (x, y) மற்றும் (vx, vy) ஒரு குறிப்பிட்ட நேரத்தில் பொருளின் இருப்பிடம் மற்றும் திசைவேகம் t, அதாவது கடைசி புதுப்பிப்பு நேரம். பி + மரம் என்பது ஒற்றை பரிமாண தரவை குறியிடுவதற்கான ஒரு கட்டமைப்பாகும். B + மரத்தை நகரும் பொருள் குறியீடாக ஏற்றுக்கொள்வதற்காக, Bx-மரம் ஒரு நேரியல் நுட்பத்தைப் பயன்படுத்துகிறது, இது t நேரத்தில் பொருட்களின் இருப்பிடத்தை ஒற்றை பரிமாண மதிப்புடன் ஒருங்கிணைக்க உதவுகிறது. குறிப்பாக, பொருள்கள் முதலில் அவற்றின் புதுப்பிப்பு நேரத்திற்கு ஏற்ப பிரிக்கப்படுகின்றன. அதே பகிர்வுக்குள் உள்ள பொருட்களுக்கு, Bx-மரம் ஒரு குறிப்பிட்ட நேரத்தில் அவற்றின் இருப்பிடங்களை சேமிக்கிறது, அவை நேரியல் இடைக்கணிப்பு மூலம் மதிப்பிடப்படுகின்றன. அவ்வாறு செய்வதன் மூலம், Bx-மரம் ஒவ்வொரு பொருளின் புதுப்பிப்பு நேரத்தையும் சேமிக்காமல் ஒரே பகிர்வுக்குள் உள்ள அனைத்து பொருட்களின் நிலையான பார்வையை வைத்திருக்கிறது. இரண்டாவதாக, இடைவெளி ஒரு கட்டத்தால் பிரிக்கப்படுகிறது மற்றும் ஒரு பொருளின் இருப்பிடம் இடைவெளி நிரப்புதல் வளைவின் படி பகிர்வுகளுக்குள் நேரியல் செய்யப்படுகிறது, எ. கா., பீனோ அல்லது ஹில்பர்ட் வளைவுகள். இறுதியாக, பகிர்வு எண் (நேரத் தகவல்) மற்றும் நேரியல் வரிசை (இருப்பிடத் தகவல்) ஆகியவற்றின் கலவையுடன், ஒரு பொருள் Bx-மரத்தில் ஒரு பரிமாண குறியீட்டு விசை Bx மதிப்புடன் குறியிடப்படுகிறதுஃ இங்கே குறியீட்டு-பகிர்வு என்பது புதுப்பிப்பு நேரத்தால் தீர்மானிக்கப்படும் ஒரு குறியீட்டு பகிர்வு மற்றும் xrep என்பது குறியீட்டு நேரத்தில் பொருளின் நிலையின் இடத்தை நிரப்பும் வளைவு மதிப்பு, x இன் பைனரி மதிப்பைக் குறிக்கிறது, மேலும் "+" என்பது ஒருங்கிணைப்பு என்று பொருள்படும். O ((7,2), (-0.1,0.05), 10), tmu = 120 என்ற ஒரு பொருளைப் பொறுத்தவரை, O க்கான Bx மதிப்பு பின்வருமாறு கணக்கிடப்படலாம். O என்பது குறிப்பிடப்பட்டபடி பகிர்வு 0 இல் குறியிடப்பட்டுள்ளது. எனவே, குறியீட்டு பகிர்வு = (00) 2. பகிர்வு 0 இன் லேபிள் நேர முத்திரையில் O இன் நிலை (1,5) ஆகும். வரிசை = 3 உடன் Z-வளைவைப் பயன்படுத்துவதன் மூலம், O இன் Z-மதிப்பு, அதாவது xrep என்பது (090011) 2 ஆகும். குறியீட்டு பகிர்வு மற்றும் xrep ஐ இணைத்தல், Bxvalue (00010011) 2 = 19. எடுத்துக்காட்டு O ((0,6), (0.2,-0.3), 10) மற்றும் tmu = 120 பின்னர் பகிர்வின் லேபிள் நேர முத்திரையில் O இன் நிலைஃ ??? செருகுதல், புதுப்பித்தல் மற்றும் நீக்குதல் ஒரு புதிய பொருளைப் பொறுத்தவரை, அதன் குறியீட்டு விசை கணக்கிடப்படுகிறது, பின்னர் பொருள் B + மரத்தில் உள்ளதைப் போல Bx-மரத்தில் செருகப்படுகிறது. ஒரு புதுப்பிப்பு ஒரு நீக்குதல் மற்றும் ஒரு செருகல் ஆகியவற்றைக் கொண்டுள்ளது. ஒவ்வொரு குறியீட்டின் சமீபத்திய விசையையும் வைத்திருக்க ஒரு துணை அமைப்பு பயன்படுத்தப்படுகிறது, இதனால் விசையைத் தேடுவதன் மூலம் ஒரு பொருளை நீக்க முடியும். மரத்தை பாதிக்கும் முன் குறியீட்டு விசை கணக்கிடப்படுகிறது. இந்த வழியில், Bx-மரம் நேரடியாக B + மரத்தின் நல்ல பண்புகளைப் பெறுகிறது, மேலும் திறமையான புதுப்பிப்பு செயல்திறனை அடைகிறது. கேள்விகள் வரம்பு வினவல் ஒரு வரம்பு வினவல் தற்போதைய நேரத்திற்கு முந்தைய நேரத்தில் செவ்வக வரம்பிற்குள் வரும் அனைத்து பொருட்களையும் மீட்டெடுக்கிறது. கேள்விகளுக்கு பதிலளிக்க Bx-மரம் வினவல்-சாளர விரிவாக்க நுட்பத்தைப் பயன்படுத்துகிறது. Bx-மரம் ஒரு பொருளின் இருப்பிடத்தை அதன் புதுப்பித்தல் நேரத்திற்குப் பிறகு சிறிது நேரம் சேமித்து வைப்பதால், விரிவாக்கம் இரண்டு நிகழ்வுகளை உள்ளடக்கியதுஃ ஒரு இருப்பிடம் முந்தைய நேரத்திற்கு மீண்டும் கொண்டு வரப்பட வேண்டும் அல்லது பிற்காலத்திற்கு முன்னோக்கி கொண்டு வரப்பட வேண்டும். வினவல் சாளரத்தை பெரிதாக்குவதே முக்கிய யோசனையாகும், இதனால் அதன் லேபிள் டைம்ஸ்டாம்பில் வினவல் சாளரத்திற்குள் இல்லாத அனைத்து பொருள்களையும் அது இணைக்கிறது, ஆனால் வினவல் டைம்ஸ்டாம்பில் வினவல் சாளரத்தில் நுழையும். விரிவாக்கத்திற்குப் பிறகு, விரிவாக்கப்பட்ட வினவல் சாளரத்தில் விழும் பொருள்களைக் கண்டறிய Bx-மரத்தின் பகிர்வுகள் கடந்து செல்ல வேண்டும். ஒவ்வொரு பகிர்விலும், ஒரு இடத்தை நிரப்புதல் வளைவின் பயன்பாடு என்பது சொந்த, இரு பரிமாண இடத்தில் ஒரு வரம்பு வினவல் மாற்றப்பட்ட, ஒரு பரிமாண இடத்தில் வரம்பு வினவல்களின் தொகுப்பாக மாறுகிறது. வளைந்த தரவுத்தொகுப்புகளின் விரிவாக்கத்திற்குப் பிறகு அதிகப்படியான பெரிய வினவல் பகுதியைத் தவிர்க்க, வினவல் வழிமுறையின் உகப்பாக்கம் உள்ளது, இது தேவையற்ற வினவல் விரிவாக்கத்தை தவிர்ப்பதன் மூலம் வினவல் செயல்திறனை மேம்படுத்துகிறது. K அருகிலுள்ள அண்டை வினவல் K அருகிலுள்ள அண்டை வினவல் k பதில்கள் கிடைக்கும் வரை அதிகரிக்கும் விரிவாக்கப்பட்ட தேடல் பகுதியுடன் வரம்பு வினவல்களை மீண்டும் மீண்டும் செய்வதன் மூலம் கணக்கிடப்படுகிறது. ஐ-டிஸ்டன்ஸ் டெக்னிக்கில் இதே போன்ற வினவல் யோசனைகளைப் பயன்படுத்துவது மற்றொரு சாத்தியமாகும். மற்ற வினவல்கள் இடைவெளி வினவல்கள், தொடர்ச்சியான வினவல்கள் போன்றவற்றை ஆதரிக்க ரேஞ்ச் வினவல் மற்றும் கே நியரெஸ்ட் நெய்பர் வினவல் வழிமுறைகளை எளிதாக நீட்டிக்க முடியும். Bx-மரம் என்பது B + மரம் குறியீட்டின் மேல் கட்டப்பட்ட ஒரு குறியீடாக இருப்பதால், Bx-மரத்தில் உள்ள அனைத்து செயல்பாடுகளும், செருகுதல், நீக்குதல் மற்றும் தேடல் உட்பட, B + மரத்தில் உள்ளதைப் போலவே இருக்கும். இந்த நடவடிக்கைகளின் அமலாக்கத்தை மாற்ற வேண்டிய அவசியமில்லை. ஒரே வித்தியாசம் என்னவென்றால், ஏற்கனவே உள்ள டி. பி. எம். எஸ்ஸில் சேமிக்கப்பட்ட நடைமுறையாக குறியீட்டு விசையைப் பெறுவதற்கான நடைமுறையை செயல்படுத்துவதாகும். எனவே, பிஎக்ஸ்-மரத்தை கர்னலைத் தொடாமல் தற்போதுள்ள டிபிஎம்எஸ் உடன் எளிதாக ஒருங்கிணைக்க முடியும். SPADE என்பது பிரபலமான தொடர்புடைய தரவுத்தள அமைப்பான MySQL இன் மேல் கட்டப்பட்ட நகரும் பொருள் மேலாண்மை அமைப்பாகும், இது பொருட்களை அட்டவணைப்படுத்த Bx-மரத்தைப் பயன்படுத்துகிறது. செயல்படுத்துவதில், நகரும் பொருள் தரவு மாற்றப்பட்டு நேரடியாக மைஎஸ்கியூஎல் இல் சேமிக்கப்படுகிறது, மேலும் வினவல்கள் நிலையான எஸ்கியூஎல் அறிக்கைகளாக மாற்றப்படுகின்றன, அவை தொடர்புடைய இயந்திரத்தில் திறம்பட செயலாக்கப்படுகின்றன. மிக முக்கியமாக, இவை அனைத்தும் மைஎஸ்கியூஎல் மையத்திற்குள் ஊடுருவாமல் நேர்த்தியாகவும் சுயாதீனமாகவும் அடையப்படுகின்றன. தரவு வளைவுடன் செயல்திறன் ட்யூனிங் சாத்தியமான சிக்கல் Bx மரம் இரு பரிமாண இருப்பிடத்தை ஒரு பரிமாண விசையாக வரைபடமாக்கும் போது இடப் பகிர்வுக்கு ஒரு கட்டத்தைப் பயன்படுத்துகிறது. இது வளைந்த தரவைக் கையாளும் போது வினவல் மற்றும் புதுப்பிப்பு செயல்பாடுகள் ஆகிய இரண்டிற்கும் செயல்திறன் சீரழிவை அறிமுகப்படுத்தலாம். கிரிட் செல் அளவுக்கு அதிகமாக இருந்தால், பல பொருள்கள் ஒரு செல்லில் உள்ளன. ஒரு செல்லில் உள்ள பொருள்கள் குறியீட்டிற்கு பிரித்தறிய முடியாதவை என்பதால், அடிப்படை பி + மரத்தில் சில நிரம்பி வழியும் முனைகள் இருக்கும். தற்போதுள்ள ஓவர்ஃப்ளோ பக்கங்கள் மரத்தின் சமநிலையை அழிப்பது மட்டுமல்லாமல் புதுப்பிப்பு செலவையும் அதிகரிக்கிறது. கேள்விகளைப் பொறுத்தவரை, கொடுக்கப்பட்ட வினவல் பகுதிக்கு, பெரிய செல் அதிக தவறான நேர்மறைகளை ஏற்படுத்துகிறது மற்றும் செயலாக்க நேரத்தை அதிகரிக்கிறது. மறுபுறம், இடத்தை சிறந்த கட்டத்துடன் பிரித்தால், அதாவது. சிறிய செல்கள், ஒவ்வொரு செல்லிலும் சில பொருள்கள் உள்ளன. புதுப்பித்தல் செலவைக் குறைக்க அதிகப்படியான பக்கங்கள் இல்லை. ஒரு வினவலில் குறைவான தவறான நேர்மறைகள் மீட்டெடுக்கப்படுகின்றன. இருப்பினும், மேலும் செல்கள் தேடப்பட வேண்டும். தேடப்படும் செல்களின் எண்ணிக்கையின் அதிகரிப்பு ஒரு வினவலின் பணிச்சுமையையும் அதிகரிக்கிறது. குறியீட்டு சரிசெய்தல் ST2B-மரம் பிஎக்ஸ்-மரத்தின் செயல்திறனை சரிசெய்வதற்கான சுய-சரிசெய்தல் கட்டமைப்பை அறிமுகப்படுத்துகிறது, அதே நேரத்தில் இடத்தில் தரவு வளைவு மற்றும் காலப்போக்கில் தரவு மாற்றத்தைக் கையாள்கிறது. விண்வெளியில் தரவு வளைவைக் கையாள்வதற்காக, ST2B-மரம் முழு இடத்தையும் வெவ்வேறு பொருள் அடர்த்தி கொண்ட பகுதிகளாகப் பிரிக்கிறது. ஒவ்வொரு பகுதியும் ஒரு தனிப்பட்ட கட்டத்தைப் பயன்படுத்துகிறது, அதன் செல் அளவு அதன் உள்ளே உள்ள பொருள் அடர்த்தியால் தீர்மானிக்கப்படுகிறது. Bx-மரம் வெவ்வேறு நேர இடைவெளிகளில் பல பகிர்வுகளைக் கொண்டுள்ளது. நேரம் செல்லச் செல்ல, ஒவ்வொரு பகிர்வும் மாறி மாறி வளர்ந்து சுருங்குகிறது. காலப்போக்கில் தரவு மாற்றங்களுக்கு ஏற்ப இடப் பகிர்வை சரிசெய்ய எஸ். டி 2 பி-மரம் இந்த அம்சத்தைப் பயன்படுத்தி குறியீட்டை ஆன்லைனில் டியூன் செய்கிறது. குறிப்பாக, ஒரு பகிர்வு காலியாக சுருங்கி வளர்ந்து வருவதால், அது சமீபத்திய தரவு அடர்த்தியின் படி ஒவ்வொரு குறிப்பு புள்ளிக்கும் ஒரு புதிய குறிப்பு புள்ளிகள் மற்றும் புதிய கட்டத்தைத் தேர்ந்தெடுக்கிறது. ட்யூனிங் ஒரு குறிப்பிட்ட காலகட்டத்தில் சேகரிக்கப்பட்ட சமீபத்திய புள்ளிவிவரங்களை அடிப்படையாகக் கொண்டது, இதனால் இடப் பகிர்வு வழி சமீபத்திய தரவு விநியோகத்திற்கு சிறப்பாக பொருந்தும். இதன் மூலம், எஸ். டி. 2. பி-மரம், இடத்திலுள்ள தரவு வளைவு மற்றும் காலப்போக்கில் தரவு மாற்றங்களால் ஏற்படும் விளைவைக் குறைக்கும் என்று எதிர்பார்க்கப்படுகிறது. மேலும் காண்கஃ B + மரம் ஹில்பர்ட் வளைவு Z-வரிசை (வளைவு) குறிப்புகள் B-மரம்