குவாட்ட்ரீகளுக்கு ஒரு ஊடாடும் அறிமுகம்

நீங்கள் நினைப்பதை விட குவாட்ட்ரீகள் ஏன் முக்கியம்

ஒவ்வொரு முறையும் நீங்கள் டிஜிட்டல் வரைபடத்தில் பிஞ்ச்-டு-ஜூம் செய்யும்போது, அருகிலுள்ள உணவகங்களை வினவும்போது அல்லது நிகழ்நேர ஃப்ளீட் டிராக்கரைப் பார்க்கும்போது, உங்கள் உலாவி நிறுத்தப்படாமல் டஜன் கணக்கான வாகன ஐகான்களைப் புதுப்பிப்பதைப் பார்க்கும்போதெல்லாம், திரைக்குப் பின்னால் ஒரு குவாட்ட்ரீ அதிக வேலைகளைச் செய்வதற்கு நல்ல வாய்ப்பு உள்ளது. Quadtrees என்பது பெரும்பாலான மக்கள் கேட்காத நேர்த்தியான தரவு கட்டமைப்புகளில் ஒன்றாகும், இருப்பினும் அவை நவீன மென்பொருளில் மிகவும் செயல்திறன்-முக்கியமான அமைப்புகளில் சிலவற்றை அமைதியாக இயக்குகின்றன - வீடியோ கேம் மோதலை கண்டறிதல் முதல் புவியியல் தகவல் அமைப்புகள் வரை வினாடிக்கு மில்லியன் கணக்கான இடஞ்சார்ந்த வினவல்களை செயலாக்குகின்றன. அவை எவ்வாறு செயல்படுகின்றன என்பதைப் புரிந்துகொள்வது உங்களை சிறந்த டெவலப்பராக மாற்றாது; இடஞ்சார்ந்த தரவு மூலம் ஒழுங்கமைத்தல் மற்றும் தேடுதல் பற்றி நீங்கள் எப்படி நினைக்கிறீர்கள் என்பதை இது அடிப்படையில் மாற்றுகிறது. நீங்கள் டெலிவரி லாஜிஸ்டிக்ஸ் பிளாட்ஃபார்ம், இருப்பிடம் சார்ந்த பகுப்பாய்வு டாஷ்போர்டை உருவாக்கினாலும் அல்லது உலாவியை செயலிழக்கச் செய்யாமல் கேன்வாஸில் 50,000 டேட்டா புள்ளிகளை ரெண்டர் செய்ய முயற்சித்தாலும், quadtrees உள்ளுணர்வு மற்றும் குறிப்பிடத்தக்க செயல்திறன் மிக்க தீர்வை வழங்குகிறது.

குவாட்ட்ரீ என்றால் என்ன?

ஒரு குவாட்ட்ரீ என்பது ஒரு மர தரவு அமைப்பாகும், அங்கு ஒவ்வொரு உள் முனையிலும் சரியாக நான்கு குழந்தைகள் இருக்கும், ஒவ்வொன்றும் இரு பரிமாண இடைவெளியின் ஒரு நால்வரைக் குறிக்கும். ஒரு சதுர பகுதியை எடுத்து அதை நான்கு சம சதுரங்களாகப் பிரிப்பதை கற்பனை செய்து பாருங்கள் - வடமேற்கு, வடகிழக்கு, தென்மேற்கு மற்றும் தென்கிழக்கு. அந்தச் சதுரங்கள் ஒவ்வொன்றையும் மேலும் நான்கு சதுரங்களாகப் பிரிக்கலாம், மேலும், நீங்கள் சில நிறுத்த நிலையை அடையும் வரை, மீண்டும் மீண்டும். அந்த நிறுத்த நிலை பொதுவாக அதிகபட்ச ஆழம் அல்லது ஒரு கணு பிரிக்கப்படுவதற்கு முன் எத்தனை தரவு புள்ளிகளை வைத்திருக்க முடியும் என்பதற்கான வரம்பு ஆகும்.

இந்த அணுகுமுறையின் அழகு அதன் தழுவல் தன்மையில் உள்ளது. தரவுப் புள்ளிகள் அடர்த்தியான பகுதிகள் நுண்ணிய மற்றும் நுண்ணிய செல்களாகப் பிரிக்கப்படுகின்றன, அதே சமயம் அரிதான பகுதிகள் பெரிய, பிரிக்கப்படாத பகுதிகளாகவே இருக்கும். ஒரு நாடு முழுவதும் 10,000 காபி ஷாப்களின் இருப்பிடங்களை சேமித்து வைக்கும் ஒரு குவாட்ட்ரீ, மன்ஹாட்டனில் ஆழமான, விரிவான உட்பிரிவுகளை உருவாக்கும் - சில சதுர கிலோமீட்டர்களுக்குள் 300 கடைகள் இருக்கலாம் - அதே நேரத்தில் கிராமப்புற வயோமிங்கின் பரந்த பகுதிகளை பூஜ்ஜியம் அல்லது ஒரு புள்ளி கொண்ட ஒற்றை, பிரிக்கப்படாத முனையாக வைத்திருக்கும். இந்த அடாப்டிவ் ரெசல்யூஷன் தான் பிளாட் கிரிட்டுடன் ஒப்பிடும்போது குவாட்ட்ரீகளை மிகவும் சக்தி வாய்ந்ததாக ஆக்குகிறது, இது காலி செல்களில் அதிக அளவு நினைவகத்தை வீணடிக்கும்.

இந்தக் கருத்தை முதன்முதலில் 1974 இல் Raphael Finkel மற்றும் J.L. பென்ட்லி விவரித்தார், அதன் பின்னர் அது பல வகைகளாகப் பிரிந்துள்ளது: பாயின்ட் quadtrees தனிப்பட்ட ஒருங்கிணைப்பு ஜோடிகளை சேமிக்கிறது, மண்டல quadtrees இடஞ்சார்ந்த பகுதிகளை பிரதிநிதித்துவப்படுத்துகிறது (reed lines ) மற்றும் வளைவுகள். ஒவ்வொரு மாறுபாடும் வெவ்வேறு பயன்பாட்டு நிகழ்வுகளுக்கு உகந்ததாக்குகிறது, ஆனால் மைய சுழல்நிலை உட்பிரிவு கொள்கை எல்லாவற்றிலும் ஒரே மாதிரியாக இருக்கும்.

செருகுதல் மற்றும் வினவல் எவ்வாறு வேலை செய்கிறது

குவாட்ரீயில் ஒரு புள்ளியைச் செருக, நீங்கள் ரூட் முனையில் தொடங்கி, நான்கு நாற்கரங்களில் எந்தப் புள்ளியில் விழுகிறது என்பதைத் தீர்மானிக்கவும். நீங்கள் அந்த நாற்கரத்தின் குழந்தை முனையில் மீண்டும் மீண்டும் செயல்முறையை மீண்டும் செய்யவும். அதன் திறனை மீறாத ஒரு இலை முனையை நீங்கள் அடைந்தால் (பொதுவாக 1 அல்லது 4 புள்ளிகளாக அமைக்கப்பட்டது), புள்ளியை அங்கே சேமித்து வைக்கவும். இலை ஏற்கனவே திறன் கொண்டதாக இருந்தால், அது நான்கு குழந்தைகளாகப் பிரிந்து, ஏற்கனவே உள்ள புள்ளிகளை அவர்களிடையே மறுபகிர்வு செய்து, புதிய புள்ளியை பொருத்தமான குழந்தைக்குச் செருகுகிறது. இந்தச் செயல்முறையானது பொதுவாக O(log n) நேரத்தில் ஒரு சீரான விநியோகத்திற்காக முடிவடைகிறது, இருப்பினும் மிக மோசமான தரவைக் கொண்ட மோசமான சூழ்நிலைகள் செயல்திறனைக் குறைக்கலாம்.

வரம்பு வினவல் - கொடுக்கப்பட்ட செவ்வகப் பகுதிக்குள் அனைத்து புள்ளிகளையும் கண்டறிதல் - நான்கு மரங்கள் உண்மையிலேயே பிரகாசிக்கின்றன. உங்கள் தரவுத்தொகுப்பில் (O(n) செயல்பாடு) ஒவ்வொரு புள்ளியையும் சரிபார்ப்பதற்குப் பதிலாக, நீங்கள் ரூட்டிலிருந்து தொடங்கி ஒவ்வொரு முனையிலும் ஒரு எளிய கேள்வியைக் கேட்கிறீர்கள்: இந்த முனையின் எல்லை எனது தேடல் செவ்வகத்துடன் வெட்டுகிறதா? இல்லையெனில், நீங்கள் முழு சப்ட்ரீயையும் கத்தரிக்கிறீர்கள் - ஒரே ஒப்பீட்டில் ஆயிரக்கணக்கான புள்ளிகளை கருத்தில் கொள்ளாமல் தவிர்க்கலாம். ஒரு குறுக்குவெட்டு இருந்தால், நீங்கள் தொடர்புடைய குழந்தைகளுக்குள் திரும்புவீர்கள். தேடல் செவ்வகத்திற்குள் வரும் இலை முனைகளில் காணப்படும் புள்ளிகள் முடிவு தொகுப்பில் சேர்க்கப்படும்.

ஒரு நடைமுறை உதாரணத்தைக் கவனியுங்கள்: உங்களிடம் 100,000 வாடிக்கையாளர் இருப்பிடங்களின் தரவுத்தொகுப்பு உள்ளது, மேலும் புதிய ஸ்டோர் திறப்பின் 5-கிலோமீட்டர் சுற்றளவில் அனைவரையும் கண்டறிய வேண்டும். ஒரு முரட்டுத்தனமான அணுகுமுறைக்கு 100,000 தூர கணக்கீடுகள் தேவை. நன்கு கட்டமைக்கப்பட்ட குவாட்ட்ரீ உங்கள் தேடல் பகுதியுடன் தெளிவாக ஒன்றுடன் ஒன்று சேராத முழு புவியியல் பகுதிகளையும் விரைவாக அகற்றுவதன் மூலம் அதை 200-500 காசோலைகளாக குறைக்கலாம். இது 200x அல்லது அதற்கு மேற்பட்ட செயல்திறன் மேம்பாடு - வினவல் 800 மில்லி விநாடிகள் மற்றும் 4 மில்லி விநாடிகள் எடுக்கும் வித்தியாசம்.

Quadtrees இல் இயங்கும் நிஜ-உலகப் பயன்பாடுகள்

குவாட்ட்ரீகளின் பயன்பாடுகள் கல்வியியல் கணினி அறிவியலுக்கு அப்பாற்பட்டது. பில்லியன் கணக்கான மக்கள் தினசரி பயன்படுத்தும் அமைப்புகளுக்கு அவை அடித்தளமாக உள்ளன, பெரும்பாலும் அதை உணராமல்.

• மேப்பிங் மற்றும் வழிசெலுத்தல்: Google Maps மற்றும் Mapbox போன்ற சேவைகள் வரைபடப் படங்களை வழங்க குவாட்ட்ரீ போன்ற ஓடு அமைப்புகளைப் பயன்படுத்துகின்றன. ஒவ்வொரு ஜூம் நிலையும் டைல்களை நான்கு குழந்தைகளாகப் பிரிக்கிறது, அதனால்தான் மேப் டைல் ஆயத்தொலைவுகள் z/x/y வடிவத்தைப் பின்பற்றுகின்றன, இது குவாட்ட்ரீ முகவரியைப் பிரதிபலிக்கிறது. நகரத் தொகுதியை நீங்கள் பெரிதாக்கும்போது, தொடர்புடைய உயர் தெளிவுத்திறன் கொண்ட ஓடுகள் மட்டுமே ஏற்றப்படும் - உலகின் பிற பகுதிகள் கரடுமுரடான தெளிவுத்திறனில் இருக்கும்.
• கேம்களில் மோதலை கண்டறிதல்: கேம் என்ஜின்கள், பொருள்கள் மோதும்போது திறமையாகக் கண்டறிய குவாட்ட்ரீகளை (மற்றும் அவற்றின் 3D இணை, ஆக்ட்ரீகள்) பயன்படுத்துகின்றன. ஒவ்வொரு ஜோடி பொருட்களையும் சோதிப்பதற்குப் பதிலாக - திரையில் 1,000 நிறுவனங்களைக் கொண்ட O(n²) கனவு - இயந்திரமானது ஒரே குவாட்ட்ரீ கலத்தைப் பகிர்ந்து கொள்ளும் பொருட்களை மட்டுமே சரிபார்க்கிறது, காசோலைகளை நிர்வகிக்கக்கூடிய எண்ணாகக் குறைக்கிறது.
• பட சுருக்கம்: ஒரே மாதிரியான வண்ணங்களைப் பெரிய தொகுதிகளாகப் பகிரும் அருகிலுள்ள பிக்சல்களை ஒன்றிணைப்பதன் மூலம் பிராந்திய குவாட்ட்ரீகள் படங்களை சுருக்கலாம். இது சில சுருக்க வழிமுறைகளின் அடிப்படையாகும்
• கப்பற்படை மேலாண்மை மற்றும் தளவாடங்கள்: டெலிவரி நிறுவனங்கள் நிகழ்நேரத்தில் அருகிலுள்ள ஆர்டர்களுடன் டிரைவர்களை பொருத்த இடஞ்சார்ந்த அட்டவணையைப் பயன்படுத்துகின்றன. "இந்த பிக்-அப் இடத்திற்கு மிக அருகில் இருக்கும் 5 டிரைவர்கள் எது?" என்ற கேள்விக்கு, ஒரு டிஸ்பாட்ச் சிஸ்டத்தை உடனடியாகப் பதிலளிக்க, குவாட்ட்ரீ உதவுகிறது. ஒவ்வொரு சில வினாடிகளிலும் ஆயிரக்கணக்கான வாகனங்கள் தங்கள் GPS நிலைகளைப் புதுப்பிக்கின்றன.
• Geospatial analytics: இருப்பிட அடிப்படையிலான வணிகத் தரவை ஒருங்கிணைக்கும் தளங்கள் — வாடிக்கையாளர் அடர்த்தி வரைபடங்கள், விற்பனைப் பகுதியை மேம்படுத்துதல், ஸ்டோர் பிளேஸ்மென்ட் பகுப்பாய்வு — இந்த வினவல்களைத் தொகுப்பாகச் செயலாக்காமல் ஊடாடச் செய்ய இடஞ்சார்ந்த தரவு கட்டமைப்புகளை நம்பியிருக்கிறது.

குவாட்ட்ரீஸின் முக்கிய நுண்ணறிவு என்னவென்றால், பெரும்பாலான இடஞ்சார்ந்த வினவல்கள் பெரும்பாலான தரவை ஆராய வேண்டியதில்லை. இடத்தை படிநிலையாக ஒழுங்கமைப்பதன் மூலம், முரட்டுத்தனமான தேடல்களை இலக்கிடப்பட்ட பயணங்களாக மாற்றுகிறீர்கள் - வினாடிகளை மில்லி விநாடிகளாக மாற்றுகிறீர்கள் மற்றும் பெரிய தரவுத்தொகுப்புகளுடன் கூட நிகழ்நேர ஊடாடுதலை சாத்தியமாக்குகிறீர்கள்.

புதிதாக ஒரு நாற்கரத்தை உருவாக்குதல்

இடைநிலை டெவலப்பர்கள் கூட, அடிப்படை குவாட்ட்ரீயை செயல்படுத்துவது வியக்கத்தக்க வகையில் அணுகக்கூடியது. மைய கட்டமைப்பிற்கு சில கூறுகள் தேவை: ஒரு எல்லை (நோட் உள்ளடக்கிய செவ்வக பகுதி), ஒரு திறன் (பிரிவதற்கு முன் அதிகபட்ச புள்ளிகள்), ஒரு புள்ளிகள் வரிசை மற்றும் நான்கு குழந்தை முனைகள் (ஆரம்பத்தில் பூஜ்யமானது). முழுச் செருகும் செயல்பாடும் பெரும்பாலான மொழிகளில் 30 வரிகளின் கீழ் எழுதப்படலாம்.

பிளவு செயல்பாடு நான்கு புதிய குழந்தை முனைகளை உருவாக்குகிறது, ஒவ்வொன்றும் பெற்றோரின் எல்லையின் ஒரு நாற்கரத்தை உள்ளடக்கியது. எல்லையைக் கொண்ட பெற்றோருக்கு (x, y, அகலம், உயரம்), வடகிழக்குக் குழந்தை (x + அகலம்/2, y, அகலம்/2, உயரம்/2), வடமேற்கு (x, y, அகலம்/2, உயரம்/2) மற்றும் பல. பிரித்த பிறகு, இருக்கும் புள்ளிகள் பொருத்தமான குழந்தைகளுக்கு மறுபகிர்வு செய்யப்படுகின்றன. மறுபகிர்வுக்குப் பிறகு பெற்றோரின் புள்ளிகள் வரிசையை அழிக்க மறந்துவிடுவது பொதுவான தவறு, இது வினவல்களின் போது நகல் முடிவுகளுக்கு வழிவகுக்கும்.

உற்பத்தி பயன்பாட்டிற்கு, பல மேம்படுத்தல்கள் முக்கியம். கணு திறனை 4-8 புள்ளிகளாக அமைப்பது பொதுவாக 1 திறனை விஞ்சிவிடும், ஏனெனில் இது மரத்தின் ஆழத்தையும் முனை பொருள்களின் மேல்நிலையையும் குறைக்கிறது. அதிகபட்ச ஆழ வரம்பு (பொதுவாக 8-12 நிலைகள்) சேர்ப்பது, எண்ணற்ற ஆழமான மரங்களை உருவாக்குவதிலிருந்து பல புள்ளிகள் ஒரே மாதிரியான ஆயங்களைப் பகிர்ந்து கொள்ளும் நோயியல் நிகழ்வுகளைத் தடுக்கிறது. மேலும் புள்ளிகள் நகரும் டைனமிக் தரவுத்தொகுப்புகளுக்கு - வாகன கண்காணிப்பு போன்ற - நீங்கள் ஒரு அகற்றும் பொறிமுறையை அல்லது மரத்தை அவ்வப்போது மீண்டும் உருவாக்குவதற்கான உத்தியை விரும்புவீர்கள், ஏனெனில் சிவப்பு-கருப்பு மரங்களைப் போல நான்கு மரங்கள் சுய-சமநிலைப்படுத்தாது.

வணிக தளங்கள் மற்றும் பகுப்பாய்வுகளில் குவாட்ட்ரீகள்

நவீன வணிகத் தளங்கள் வாடிக்கையாளர் இருப்பிடங்கள், விநியோக மண்டலங்கள், விற்பனைப் பகுதிகள் அல்லது சொத்துக் கண்காணிப்பு என இடஞ்சார்ந்த தரவுகளை அதிகளவில் கையாள்கின்றன. சவாலானது இந்தத் தரவைச் சேமித்து வைப்பது மட்டுமல்ல - இது நிகழ்நேரத்தில் அதை வினவக்கூடிய அளவில் செய்கிறது. 50 நகரங்களில் செயல்படும் வணிகமானது வாடிக்கையாளர் அடர்த்தி, வழி விநியோக இயக்கிகள் அல்லது பிராந்திய விற்பனை செயல்திறனைப் பகுப்பாய்வு செய்ய வேண்டும் எனில், டாஷ்போர்டு 200 மில்லி விநாடிகள் அல்லது 20 வினாடிகளில் ஏற்றப்படுமா என்பதை அடிப்படை இடஞ்சார்ந்த அட்டவணைப்படுத்தல் உத்தி தீர்மானிக்கிறது.

இது ஒரு காரணம் Mewayz போன்ற இயங்குதளங்கள் — இது CRM, இன்வாய்சிங், ஃப்ளீட் மேனேஜ்மென்ட், முன்பதிவு மற்றும் பகுப்பாய்வு ஆகியவற்றை ஒருங்கிணைக்கும் 207 மாட்யூல்களை ஒரு வணிக OS ஆக ஒருங்கிணைக்கிறது — இது திறமையான இடஞ்சார்ந்த தரவு கையாளுதலின் மூலம் பயனடைகிறது. ஒரு ஃப்ளீட் மேனேஜ்மென்ட் மாட்யூல் ஒரு வரைபடத்தில் 500 செயலில் உள்ள வாகனங்களைக் காட்ட வேண்டியிருக்கும் போது அல்லது ஒரு CRM தொகுதி 138,000+ பயனர் இருப்பிடங்களைக் காட்சிப்படுத்தும்போது, ​​அப்பட்டமான அணுகுமுறைகள் வெறுமனே அளவிடப்படாது. quadtrees (அல்லது PostGIS R-trees மற்றும் MySQL ஸ்பேஷியல் இன்டெக்ஸ்கள் போன்ற அவற்றின் தரவுத்தளச் சமமானவை) போன்ற இடஞ்சார்ந்த அட்டவணைப்படுத்தல் கட்டமைப்புகள் நிறுவன தர வன்பொருள் தேவையில்லாமல் இந்த அம்சங்களை வழங்குவதை சாத்தியமாக்குகிறது.

பிளாட்ஃபார்ம்களை மதிப்பிடும் வணிகங்களுக்கு, டேக்அவே நடைமுறைக்குரியது: இருப்பிடம் மற்றும் இடஞ்சார்ந்த தரவை நன்றாகக் கையாளும் கருவிகள், அதன் பொருட்டு ஆடம்பரமான அல்காரிதங்களைப் பயன்படுத்துவதில்லை. 10 கிலோமீட்டருக்குள் கிடைக்கக்கூடிய சேவை வழங்குநர்களை உடனடியாகக் காட்டக்கூடிய முன்பதிவு அமைப்புக்கும் அதே முடிவுகளை ஏற்றுவதற்கு 8 வினாடிகள் எடுக்கும் அமைப்புக்கும் இடையே வித்தியாசத்தை அவர்கள் உருவாக்குகிறார்கள். இந்த மட்டத்தில் செயல்திறன் நேரடியாக பயனர் அனுபவமாகவும், இறுதியில் வருவாயாகவும் மொழிபெயர்க்கப்படுகிறது.

Quadtrees vs. பிற இடஞ்சார்ந்த தரவு கட்டமைப்புகள்

குவாட்ட்ரீஸ் மட்டும் இடஞ்சார்ந்த அட்டவணைப்படுத்துதலுக்கான ஒரே வழி அல்ல, மேலும் மாற்றுகளைப் புரிந்துகொள்வது சரியான கருவியைத் தேர்வுசெய்ய உதவுகிறது. R-trees, PostGIS மற்றும் SQLite இன் R*Tree மாட்யூல் போன்ற தரவுத்தளங்களில் அதிகமாகப் பயன்படுத்தப்படுகிறது, தரவை குறைந்தபட்ச வரம்பு செவ்வகங்களாக ஒழுங்கமைத்து, வரம்பு வினவல்கள் மற்றும் அருகிலுள்ள தேடல்களைத் திறமையாகக் கையாளுகிறது. அவை பொதுவாக வட்டு அடிப்படையிலான சேமிப்பகத்திற்கான குவாட்ட்ரீகளை விட சிறப்பாக செயல்படுகின்றன, ஏனெனில் அவை I/O செயல்பாடுகளைக் குறைக்கின்றன, அதனால்தான் பெரும்பாலான இடஞ்சார்ந்த தரவுத்தளங்கள் குவாட்ட்ரீகளை விட உள்நாட்டில் R-tree மாறுபாடுகளைப் பயன்படுத்துகின்றன.

K-d மரங்கள் மாற்று அச்சு-சீரமைக்கப்பட்ட பிளவுகளைப் பயன்படுத்தி இடத்தைப் பிரிக்கவும் (முதலில் x, பின்னர் y, பின்னர் x மூலம்) மற்றும் மிதமான பரிமாணங்களில் அருகிலுள்ள அண்டை தேடலுக்கு சிறந்தது. பரிமாணம் குறைவாக இருக்கும் போது மற்றும் தரவுத்தொகுப்பு நிலையானதாக இருக்கும் போது அவை குவாட்ட்ரீகளை விட சிறப்பாக செயல்பட முனைகின்றன, ஆனால் அவை மாறும் வகையில் புதுப்பிக்க கடினமாக இருக்கும். Geohashes முற்றிலும் வேறுபட்ட அணுகுமுறையை எடுத்து, அட்சரேகை மற்றும் தீர்க்கரேகையை ஒரே சரத்தில் குறியாக்கம் செய்கின்றன, அங்கு பகிரப்பட்ட முன்னொட்டுகள் இடஞ்சார்ந்த அருகாமையைக் குறிக்கின்றன - அவை தரவுத்தள அட்டவணைப்படுத்தல் மற்றும் தேக்ககத்திற்கு ஏற்றதாக அமைகின்றன, ஆனால் தன்னிச்சையான வரம்பு வினவல்களுக்கு குறைந்த நெகிழ்வுத்தன்மை கொண்டவை.

குவாட்ட்ரீகள் அவற்றின் பலத்திற்கு ஏற்றவாறு செயல்படும் காட்சிகளில் தனித்து நிற்கின்றன: நினைவகத்தில் இடஞ்சார்ந்த அட்டவணைப்படுத்தல், அடிக்கடி செருகல்கள் மற்றும் நீக்குதல்கள் கொண்ட டைனமிக் தரவுத்தொகுப்புகள், படிநிலை கட்டம் அமைப்பு இயற்கையாகவே பெரிதாக்கும் நிலைகளை வரைபடமாக்கும் காட்சிப்படுத்தல் பயன்பாடுகள் மற்றும் செயல்படுத்தலின் எளிமை முக்கியமான சூழ்நிலைகள். பான் மற்றும் ஜூம் மூலம் கேன்வாஸில் 10,000 டேட்டா புள்ளிகளை ரெண்டரிங் செய்யும் முன்-இறுதி பயன்பாட்டிற்கு, ஜாவாஸ்கிரிப்ட்டின் 100 வரிகளில் செயல்படுத்தப்பட்ட குவாட்ட்ரீ, நெட்வொர்க் தாமதத்தை நீக்குவதன் மூலம் எந்த தரவுத்தள ஆதரவு தீர்வையும் விஞ்சும்.

தொடங்குதல்: நடைமுறை அடுத்த படிகள்

நான்கு மரங்களைப் பற்றி படிப்பதைத் தாண்டி அவற்றைப் பற்றிய உங்கள் புரிதலை ஆழப்படுத்த விரும்பினால், பார்வைக்கு ஒன்றை உருவாக்குவதே மிகவும் பயனுள்ள அணுகுமுறையாகும். கிளிக் செய்வதன் மூலம் புள்ளிகளைச் சேர்க்கும் எளிய கேன்வாஸ் பயன்பாட்டை உருவாக்கவும், நிகழ்நேரத்தில் மரத்தின் உட்பிரிவைக் காணவும். வரம்பு-வினவல் செவ்வகத்தைச் சேர்க்கவும், அதை நீங்கள் இழுத்துச் சென்று அது கண்டறிந்த புள்ளிகளை முன்னிலைப்படுத்தலாம். இந்த நேரடியான ஊடாடல், எந்த வாசிப்பும் பொருந்தாத உள்ளுணர்வை உருவாக்குகிறது - கொத்தாக தரவு ஏன் ஆழமான மரங்களை உருவாக்குகிறது மற்றும் வினவல்களின் போது கத்தரித்தல் நடத்தை எவ்வாறு பெரிய இடங்களை நீக்குகிறது என்பதை நீங்கள் உடனடியாகக் காண்பீர்கள்.

உற்பத்தி பயன்பாடுகளுக்கு, இந்த வழிகாட்டுதல்களைக் கவனியுங்கள்: உங்கள் தரவு தரவுத்தளத்தில் இருந்தால், பயன்பாட்டுக் குறியீட்டில் quadtrees ஐச் செயல்படுத்துவதை விட, உங்கள் தரவுத்தளத்தில் (PostGIS, MySQL Spatial, MongoDB 2dsphere இன்டெக்ஸ்கள்) இடஞ்சார்ந்த அட்டவணையைப் பயன்படுத்தவும். நீங்கள் கிளையன்ட் பக்க காட்சிப்படுத்தல் அல்லது நினைவகத்தில் செயலாக்கம் செய்கிறீர்கள் எனில், JavaScript க்கான d3-quadtree அல்லது Python க்கான pyquadtree போன்ற நூலகங்கள் போர்-சோதனை செய்யப்பட்ட செயலாக்கங்களை உங்களுக்கு வழங்குகின்றன. நீங்கள் எந்த வகையான இருப்பிடத் தரவையும் கையாளும் தளத்தை உருவாக்குகிறீர்கள் என்றால் - வாடிக்கையாளர் முகவரிகள் முதல் டெலிவரி ரூட்டிங் வரை டெலிவரி மேனேஜ்மென்ட் வரை - இடஞ்சார்ந்த அட்டவணைப்படுத்தலைப் புரிந்துகொள்வதற்கு நேரத்தைச் செலவிடுங்கள், ஏனெனில் இது உங்கள் பயன்பாடு என்ன செய்ய முடியும் என்பதை அடிப்படையில் வடிவமைக்கும்.

Quadtrees கணினி அறிவியலில் ஒரு பரந்த கொள்கையை பிரதிநிதித்துவப்படுத்துகிறது: உங்கள் தரவுக்காக நீங்கள் தேர்ந்தெடுக்கும் கட்டமைப்பு நீங்கள் திறமையாக பதிலளிக்கக்கூடிய கேள்விகளை தீர்மானிக்கிறது. ஆயத்தொலைவுகளின் ஒரு பிளாட் லிஸ்ட் "எனக்கு எல்லா புள்ளிகளையும் கொடு" என்று பதிலளிக்கலாம், ஆனால் ஒரு குவாட்ட்ரீ "அருகில் உள்ள எல்லா புள்ளிகளையும் எனக்கு இங்கே கொடு" என்று பதிலளிக்க முடியும் - மேலும் அது உடனடியாக உணரும் அளவுக்கு வேகமாகச் செய்யும். தொழில்துறை மதிப்பீட்டின்படி 73% வணிகத் தரவுகள் இடஞ்சார்ந்த கூறுகளைக் கொண்டிருக்கும் உலகில், அந்த திறன் கல்வி சார்ந்தது மட்டுமல்ல. இது ஒரு போட்டி நன்மை.

அடிக்கடி கேட்கப்படும் கேள்விகள்

குவாட்ட்ரீ என்றால் என்ன, அது எப்படி வேலை செய்கிறது?

ஒரு குவாட்ட்ரீ என்பது ஒரு மர அடிப்படையிலான தரவுக் கட்டமைப்பாகும், இது இரு பரிமாண இடைவெளியை நான்கு சமமான நாற்கரங்களாகப் பிரிக்கிறது. ஒவ்வொரு முனையும் நான்கு சைல்டு நோட்களாகப் பிரிக்கும் முன் குறிப்பிட்ட எண்ணிக்கையிலான தரவுப் புள்ளிகளை வைத்திருக்க முடியும். இந்த படிநிலைப் பகிர்வு இடஞ்சார்ந்த வினவல்களை உருவாக்குகிறது - கொடுக்கப்பட்ட பகுதியில் உள்ள அனைத்து புள்ளிகளையும் கண்டறிவது போன்றது - மிக வேகமாக, பெரும்பாலான நடைமுறை சூழ்நிலைகளில் நேரியல் முதல் மடக்கை வரை தேடல் நேரத்தை குறைக்கிறது.

நிஜ உலகப் பயன்பாடுகளில் பொதுவாக நான்கு மரங்கள் எங்கே பயன்படுத்தப்படுகின்றன?

பிஞ்ச்-டு-ஜூம் செயல்பாட்டுடன் கூடிய டிஜிட்டல் வரைபடங்கள், நிகழ்நேர கடற்படை கண்காணிப்பு டாஷ்போர்டுகள், வீடியோ கேம் மோதல் கண்டறிதல் இயந்திரங்கள் மற்றும் வினாடிக்கு மில்லியன் கணக்கான இடஞ்சார்ந்த வினவல்களைச் செயலாக்கும் புவியியல் தகவல் அமைப்புகள் உட்பட பல்வேறு வகையான அமைப்புகளுக்கு குவாட்ட்ரீகள் சக்தி அளிக்கின்றன. இரு பரிமாண இடைவெளியில் விநியோகிக்கப்படும் பொருட்களைத் திறமையாகத் தேட, செருக அல்லது நிர்வகிக்க வேண்டிய எந்தவொரு பயன்பாடும் குவாட்ட்ரீ இன்டெக்ஸிங்கிலிருந்து பயனடையலாம்.

குவாட்ட்ரீகள் மற்ற இடஞ்சார்ந்த தரவு கட்டமைப்புகளுடன் எவ்வாறு ஒப்பிடுகின்றன?

தட்டையான கட்டங்களைப் போலல்லாமல், குவாட்ட்ரீகள் அவற்றின் தீர்மானத்தை தரவு அடர்த்திக்கு மாற்றியமைக்கின்றன - அரிதான பகுதிகள் கரடுமுரடாக இருக்கும், அதே நேரத்தில் நெரிசலான பகுதிகள் மேலும் பிரிக்கப்படுகின்றன. k-d மரங்களுடன் ஒப்பிடும்போது, ​​குவாட்ட்ரீகள் செயல்படுத்த எளிதானவை மற்றும் ஒரே மாதிரியாக விநியோகிக்கப்படும் 2D தரவுகளுக்கு மிகவும் பொருத்தமானவை. R-மரங்கள் ஒன்றுடன் ஒன்று சேரும் பகுதிகளை மிகவும் அழகாகக் கையாளுகின்றன, ஆனால் குவாட்ட்ரீகள் செருகும் வேகத்தில் வெற்றி பெறுகின்றன மற்றும் நிகழ்நேர பணிச்சுமைகளுக்கு இணையாக எளிதாக இருக்கும்.

வணிக மென்பொருளில் செயல்திறனை மேம்படுத்த quadtrees உதவுமா?

நிச்சயமாக. இருப்பிடத் தரவு, ஸ்பேஷியல் அனலிட்டிக்ஸ் அல்லது ஊடாடும் டாஷ்போர்டுகளைக் கையாளும் எந்தவொரு வணிகக் கருவியும் quadtree தேர்வுமுறையிலிருந்து பலன்களைப் பெறுகிறது. Mewayz போன்ற இயங்குதளங்கள், $19/mo இல் தொடங்கும் 207-தொகுதி வணிக OS, திரைக்குப் பின்னால் திறமையான தரவு கட்டமைப்புகளைப் பயன்படுத்தி, விரைவான, பதிலளிக்கக்கூடிய அனுபவங்களை - ஸ்டோர் லொக்கேட்டர் வரைபடங்கள் முதல் நிகழ்நேர பகுப்பாய்வுகள் வரை ஆயிரக்கணக்கான தரவு புள்ளிகளில்