हिल्बर्ट, लेब्सेग ... और शून्य

कटौती के तहत, एक अच्छे बहुआयामी अनुक्रमण एल्गोरिदम को कैसे व्यवस्थित किया जाना चाहिए, इस सवाल की जांच की जाती है। हैरानी की बात है कि इतने सारे विकल्प नहीं हैं।

वन-डाइमेंशनल इंडेक्स, बी-ट्रीज़

खोज एल्गोरिथ्म की सफलता का माप 2 तथ्य माना जाएगा -

1. डिस्क पृष्ठ के रीड की संख्या के लघुगणक (सूचकांक के आकार के संबंध में) की उपस्थिति या परिणाम की अनुपस्थिति के तथ्य की स्थापना होती है
2. एक परिणाम जारी करने की लागत इसकी मात्रा के लिए आनुपातिक है

इस अर्थ में, बी-पेड़ काफी सफल हैं और इसका कारण एक संतुलित पेड़ का उपयोग माना जा सकता है। एल्गोरिथ्म की सादगी कुंजी स्थान की एक-आयामीता के कारण है - यदि आवश्यक हो, तो पृष्ठ को विभाजित करें, यह इस पृष्ठ के दो सॉर्ट किए गए कई तत्वों में विभाजित करने के लिए पर्याप्त है। आमतौर पर तत्वों की संख्या से विभाजित, हालांकि यह आवश्यक नहीं है।

क्योंकि पेड़ के पन्नों को डिस्क पर संग्रहीत किया जाता है, यह कहा जा सकता है कि बी-पेड़ में एक आयामी डिस्क स्थान के लिए एक आयामी कुंजी स्थान को बहुत कुशलता से बदलने की क्षमता है।

अधिक या कम "सही सम्मिलन" के साथ एक पेड़ को भरने पर, और यह एक काफी सामान्य मामला है, कुंजी विकास के क्रम में पृष्ठ उत्पन्न होते हैं, कभी-कभी उच्च पृष्ठों के साथ वैकल्पिक। अच्छी संभावना है कि वे डिस्क पर भी होंगे। इस प्रकार, किसी भी प्रयास के बिना, उच्च डेटा स्थानीयता प्राप्त की जाती है - वे डेटा जो मूल्य में करीब हैं वे पास और डिस्क पर कहीं न कहीं होंगे।

बेशक, जब यादृच्छिक क्रम में मान सम्मिलित करते हैं, तो चाबियाँ और पृष्ठ अनियमित रूप से उत्पन्न होते हैं, जिसके परिणामस्वरूप तथाकथित सूचकांक विखंडन। एंटी-विखंडन उपकरण भी हैं जो डेटा स्थानीयता को पुनर्स्थापित करते हैं।

ऐसा लगता है कि हमारे RAID और SSD के युग में डिस्क से पढ़ने के क्रम से कोई फर्क नहीं पड़ता। लेकिन, बल्कि, इसका पहले जैसा अर्थ नहीं है। SSD में प्रमुखों का कोई भौतिक अग्रेषण नहीं होता है, इसलिए इसकी यादृच्छिक रीड गति, HDD की तरह, ठोस रीडिंग की तुलना में सैकड़ों गुना कम नहीं होती है। और हर 10 या अधिक बार केवल एक बार।

याद रखें कि बी-पेड़ 1970 में चुंबकीय टेप और ड्रम के युग में दिखाई दिए थे। जब HDD और SSD की तुलना में उल्लेखित टेप और ड्रम के लिए यादृच्छिक अभिगम गति में अंतर बहुत अधिक नाटकीय था।

इसके अलावा, 10 गुना भी मायने रखता है। और इन 10 बार में न केवल एसएसडी की भौतिक विशेषताएं शामिल हैं, बल्कि मूल बिंदु भी है - पाठक व्यवहार की भविष्यवाणी। यदि पाठक को इस ब्लॉक के लिए अगले ब्लॉक के लिए पूछने की बहुत संभावना है, तो यह धारणा द्वारा इसे डाउनलोड करने के लिए समझ में आता है। और यदि व्यवहार अराजक है, तो भविष्यवाणी के सभी प्रयास निरर्थक हैं और हानिकारक भी हैं।

बहुआयामी अनुक्रमण

इसके अलावा, हम दो-आयामी बिंदुओं (X, Y) के सूचकांक से निपटेंगे, सिर्फ इसलिए कि उनके साथ काम करना सुविधाजनक और सहज है। लेकिन समस्याएं मूल रूप से समान हैं।

एक्स और वाई के लिए अलग-अलग सूचकांकों के साथ एक सरल, "अनसोफिसेबल" विकल्प हमारी सफलता की कसौटी के अनुसार नहीं गुजरता है। यह पहले बिंदु को प्राप्त करने के लघुगणक लागत नहीं देता है। वास्तव में, प्रश्न का उत्तर देने के लिए, क्या वांछित सीमा तक कुछ भी है, हमें चाहिए

• इंडेक्स एक्स में एक खोज करें और एक्स-अंतराल अंतराल से सभी पहचानकर्ता प्राप्त करें
• Y के लिए समान है
• पहचानकर्ताओं के इन दो सेटों को काटना

पहले से ही पहला आइटम सीमा के आकार पर निर्भर करता है और लघुगणक की गारंटी नहीं देता है।

"सफल" होने के लिए, एक बहुआयामी सूचकांक को कम या ज्यादा संतुलित पेड़ के रूप में व्यवस्थित किया जाना चाहिए। यह कथन विवादास्पद लग सकता है। लेकिन एक लघुगणक खोज की आवश्यकता हमें इस तरह के एक उपकरण के लिए निर्धारित करती है। दो पेड़ या उससे अधिक क्यों नहीं? पहले से ही दो पेड़ों के साथ "अपरिष्कृत" और अनुपयुक्त विकल्प माना जाता है। शायद वहाँ उपयुक्त हैं। लेकिन दो पेड़ - यह दोगुना है (साथ-साथ) ताले, दो बार ज्यादा लागत, एक गतिरोध को पकड़ने के लिए काफी अधिक संभावना। यदि आप एक पेड़ से प्राप्त कर सकते हैं, तो आपको निश्चित रूप से इसका उपयोग करना चाहिए।

यह सब देखते हुए, एक बहुत ही सफल बी-ट्री अनुभव के आधार पर लेने की इच्छा और दो-आयामी डेटा के साथ काम करने के लिए इसे "सामान्य" करना काफी स्वाभाविक है।

तो आर-ट्री दिखाई दिया।

आर-वृक्ष

आर-ट्री को निम्नानुसार व्यवस्थित किया गया है:
प्रारंभ में, हमारे पास एक खाली पृष्ठ है, बस उसमें डेटा (अंक) जोड़ें।
लेकिन यहां पेज भरा हुआ है और इसे विभाजित करने की आवश्यकता है।
बी-ट्री में, पृष्ठ तत्वों को प्राकृतिक तरीके से ऑर्डर किया जाता है, इसलिए सवाल यह है कि कितना कटौती करना है। आर-ट्री में कोई प्राकृतिक क्रम नहीं है। दो विकल्प हैं:

• ऑर्डर लाओ, अर्थात एक फ़ंक्शन का परिचय दें, जो X & Y पर आधारित है, एक मूल्य देगा जिसके अनुसार पृष्ठ तत्वों को आदेश दिया जाएगा और उसके अनुसार विभाजित किया जाएगा। इस मामले में, संपूर्ण सूचकांक निर्दिष्ट फ़ंक्शन के मूल्यों से निर्मित एक नियमित बी-ट्री में पतित हो जाता है। स्पष्ट प्लसस के अलावा, एक बड़ा सवाल है - ठीक है, ठीक है, हम अनुक्रमित हैं, लेकिन कैसे देखें? उस पर अधिक बाद में, पहले दूसरे विकल्प पर विचार करें।
• पृष्ठ को स्थानिक मानदंड से विभाजित करें। ऐसा करने के लिए, प्रत्येक पृष्ठ को उसके नीचे / नीचे स्थित तत्वों की सीमा निर्धारित की जानी चाहिए। यानी रूट पृष्ठ में संपूर्ण परत की सीमा होती है। बंटवारे के समय, दो (या अधिक) पृष्ठ उत्पन्न होते हैं, जिनके अंश मूल पृष्ठ (खोज के लिए) की सीमा में शामिल होते हैं।

सरासर अनिश्चितता है। पेज को कैसे विभाजित करें? क्षैतिज या ऊर्ध्वाधर? आधे क्षेत्र या तत्वों के आधे से आगे बढ़ें? लेकिन क्या होगा अगर अंक दो समूहों का गठन करते हैं, लेकिन आप उन्हें केवल एक विकर्ण रेखा के साथ अलग कर सकते हैं? और अगर तीन क्लस्टर हैं?

---

इस तरह के सवालों की मौजूदगी यह दर्शाती है कि आर-ट्री एक एल्गोरिथ्म नहीं है। यह उत्तराधिकार का एक सेट है, कम से कम प्रविष्टि के दौरान एक पृष्ठ को विभाजित करने के लिए, विलोपन / संशोधन के दौरान पृष्ठों को विलय के लिए, थोक सम्मिलन के लिए प्रीप्रोसेसिंग के लिए।

हेयूरिस्टिक्स में एक विशेष डेटा प्रकार पर एक विशेष पेड़ की विशेषज्ञता शामिल है। यानी एक खास तरह के डेटासेट पर, वह अक्सर कम गलत करती है। “आंकड़े पूरी तरह से गलत नहीं हो सकते, क्योंकि इस मामले में, यह एक एल्गोरिथ्म होगा "©।

इस संदर्भ में अनुमानी त्रुटि का क्या अर्थ है? उदाहरण के लिए, यह पृष्ठ असफल हो जाएगा / विलय हो जाएगा और पृष्ठ एक दूसरे को आंशिक रूप से ओवरलैप करना शुरू कर देंगे। यदि अचानक खोज सीमा पृष्ठों के ओवरलैप क्षेत्र पर पड़ती है, तो खोज की लागत पहले से ही काफी लघुगणक नहीं होगी। समय के साथ, जैसे ही आप सम्मिलित करते हैं / हटाते हैं, त्रुटियों की संख्या जमा होती है और पेड़ का प्रदर्शन ख़राब होने लगता है।


चित्र 1 यहाँ R * वृक्ष का उदाहरण दिया गया है, जो प्राकृतिक तरीके से बनाया गया है।


चित्र 2 और यहाँ एक ही डाटासेट पहले से संसाधित है और पेड़ बड़े पैमाने पर सम्मिलन द्वारा बनाया गया है

हम कह सकते हैं कि बी-ट्री भी समय के साथ खराब हो जाता है, लेकिन यह थोड़ा अलग गिरावट है। बी-ट्री का प्रदर्शन इस तथ्य के कारण होता है कि इसके पृष्ठ एक पंक्ति में नहीं हैं। यह आसानी से पेड़ को "सीधा" करके इलाज किया जाता है - डीफ़्रेग्मेंटेशन। एक आर-पेड़ के मामले में, इसे से छुटकारा पाना इतना आसान नहीं है; स्थिति को सही करने के लिए पेड़ की संरचना ही "वक्र" है;

बहु-आयामी स्थानों के लिए आर-ट्री के सामान्यीकरण स्पष्ट नहीं हैं। उदाहरण के लिए, पृष्ठों को विभाजित करते समय, हमने बाल पृष्ठों की परिधि को कम कर दिया। त्रि-आयामी मामले में क्या कम करना है? आयतन या सतह क्षेत्र? और आठ आयामी मामले में? सामान्य ज्ञान अब सलाहकार नहीं है।

अनुक्रमित स्थान अच्छी तरह से गैर-आइसोट्रोपिक हो सकता है। क्यों नहीं सूचकांक केवल अंक, लेकिन समय में उनकी स्थिति, अर्थात्। (एक्स, वाई, टी)। इस मामले में, उदाहरण के लिए, परिधि के आधार पर अनुमान के बाद से निरर्थक हैं समय अंतराल पर लंबाई को ढेर करता है।

आर-ट्री की सामान्य छाप गिल-फुट क्रस्टेशियंस जैसी है । उन लोगों के पास अपना खुद का पारिस्थितिक क्षेत्र है, जिसमें उनका मुकाबला करना मुश्किल है। लेकिन सामान्य मामले में, उनके पास अधिक विकसित जानवरों के साथ प्रतिस्पर्धा करने का कोई मौका नहीं है।

चौकोर वृक्ष

एक क्वाडट्री में, प्रत्येक गैर-पत्ती पृष्ठ में ठीक चार वंशज होते हैं, जो समान रूप से अपनी जगह को क्वाड्रंट में विभाजित करते हैं।


चित्र 3 एक निर्मित चतुष्कोणीय वृक्ष का उदाहरण

यह एक अच्छा डेटाबेस डिज़ाइन नहीं है।

• प्रत्येक पृष्ठ प्रत्येक समन्वय के लिए खोज स्थान को केवल दो बार बताता है। हां, यह खोज का लघुगणक जटिलता प्रदान करता है, लेकिन यह आधार 2 लघुगणक है, पृष्ठ पर तत्वों की संख्या नहीं है, (यहां तक ​​कि 100) एक बी-पेड़ के रूप में।
• प्रत्येक पृष्ठ छोटा है, लेकिन इसके पीछे आपको अभी भी डिस्क पर जाना है।
• क्वाड ट्री की गहराई सीमित होनी चाहिए, अन्यथा इसका असंतुलन प्रदर्शन को प्रभावित करता है। नतीजतन, अत्यधिक क्लस्टर किए गए डेटा पर (उदाहरण के लिए, एक नक्शे पर मकान - शहरों में बहुत से शहर हैं, कुछ क्षेत्रों में) पत्ती पृष्ठों पर बड़ी मात्रा में डेटा जमा हो सकता है। सटीक एक इंडेक्स ब्लॉक हो जाता है और पोस्ट-प्रोसेसिंग की आवश्यकता होती है।
  
  खराब रूप से चयनित जाली आकार (पेड़ की गहराई) प्रदर्शन को मार सकती है। फिर भी, मैं एल्गोरिथ्म के प्रदर्शन के लिए मानव कारक पर गंभीर रूप से निर्भर नहीं होना चाहूंगा।
  
• एक बिंदु के भंडारण के लिए स्थान की लागत काफी बड़ी है।

अंतरिक्ष की संख्या

यह एक फ़ंक्शन के साथ पहले आस्थगित संस्करण पर विचार करने के लिए बना रहता है, जो एक बहुआयामी कुंजी के आधार पर, नियमित बी-ट्री में लिखने के लिए मूल्य की गणना करता है।

इस तरह के सूचकांक का निर्माण स्पष्ट है, और सूचकांक में बी-ट्री के सभी फायदे हैं। एकमात्र सवाल यह है कि क्या प्रभावी खोज के लिए इस सूचकांक का उपयोग किया जा सकता है।

इस तरह के कार्यों की एक बड़ी संख्या है, यह माना जा सकता है कि उनमें से एक छोटी संख्या में "अच्छे", बड़ी संख्या में "बुरे" और बड़ी संख्या में "बस भयानक" हैं।

एक भयानक कार्य ढूँढना मुश्किल नहीं है - हम कुंजी को एक स्ट्रिंग में क्रमबद्ध करते हैं, इसमें से एमडी 5 पर विचार करें और एक मान प्राप्त करें जो हमारे उद्देश्यों के लिए पूरी तरह से बेकार है।

और अच्छे से कैसे संपर्क करें? यह पहले ही कहा जा चुका है कि एक उपयोगी सूचकांक डेटा का "स्थानीयता" प्रदान करता है - ऐसे बिंदु जो अंतरिक्ष में करीब हैं और अक्सर डिस्क में सहेजे जाने पर एक दूसरे के करीब होते हैं। जैसा कि वांछित फ़ंक्शन पर लागू होता है, इसका मतलब है कि स्थानिक रूप से करीबी बिंदुओं के लिए यह करीबी मूल्य देता है।

एक बार सूचकांक में, गणना किए गए मान "भौतिक" पृष्ठों पर उनके मूल्यों के क्रम में दिखाई देंगे। "भौतिक अर्थ" के दृष्टिकोण से, खोज सीमा संभव के रूप में कुछ भौतिक सूचकांक पृष्ठों को प्रभावित करना चाहिए। जो आम तौर पर स्पष्ट है। इस दृष्टिकोण से, संख्या घटता है कि डेटा "खराब" है। और वे जो "एक गेंद में भ्रमित करते हैं" - "अच्छे" के करीब।

Naive नंबरिंग

एक वर्ग (हाइपरक्यूब) में एक खंड को निचोड़ने का प्रयास जबकि एक आयामी अंतरिक्ष के तर्क में शेष है यानी। टुकड़ों में काटें और इन टुकड़ों के साथ वर्ग भरें। यह हो सकता है


4 लाइन स्कैन


5 इंटरलेक्टेड


चित्र 6 सर्पिल

या ... आप कई विकल्पों के साथ आ सकते हैं, उन सभी में दो कमियां हैं

1. अस्पष्टता, उदाहरण के लिए: सर्पिल को दक्षिणावर्त क्यों कर्ल किया जाता है और इसके खिलाफ नहीं, या क्यों क्षैतिज स्कैन पहले एक्स के साथ और फिर वाई के साथ होता है
   
2. लंबे सीधे टुकड़ों की उपस्थिति जो बहुआयामी अनुक्रमण के लिए इस तरह की विधि का उपयोग अप्रभावी बनाते हैं (बड़े पृष्ठ परिधि)

सीधी पहुँच सुविधाएँ

यदि "भोली" विधियों का मुख्य दावा यह है कि वे बहुत लम्बी पृष्ठ उत्पन्न करते हैं, तो हम अपने दम पर "सही" पृष्ठ उत्पन्न करते हैं।

विचार सरल है - चलो ब्लॉकों में अंतरिक्ष का एक बाहरी विभाजन हो, प्रत्येक ब्लॉक को एक पहचानकर्ता असाइन करें और यह स्थानिक सूचकांक की कुंजी होगी।

• X & Y निर्देशांक को 16-बिट होने दें (स्पष्टता के लिए)
• हम 1024x1024 आकार के वर्ग ब्लॉकों के साथ अंतरिक्ष को कवर करने जा रहे हैं
• निर्देशांक coarsen, दाईं ओर 10 बिट्स द्वारा स्थानांतरित करें
• और पेज आईडी प्राप्त करें, एक्सएंडवाई से बिट्स को गोंद करें। अब पहचानकर्ता में निचले 6 अंक X से सबसे पुराने हैं, अगले 6 अंक Y से सबसे पुराने हैं
  

यह देखना आसान है कि ब्लॉक एक लाइन स्कैन बनाते हैं, इसलिए, खोज सीमा के लिए डेटा खोजने के लिए, आपको ब्लॉकों की प्रत्येक पंक्ति के लिए सूचकांक में एक खोज / पढ़ना होगा जो इस सीमा पर रखी गई है। सामान्य तौर पर, यह विधि महान काम करती है, हालांकि इसके कई नुकसान हैं।

• एक इंडेक्स बनाते समय, आपको इष्टतम ब्लॉक आकार चुनना होगा, जो पूरी तरह से अप्रयुक्त है
• यदि ब्लॉक एक विशिष्ट क्वेरी से काफी बड़ा है, तो खोज अक्षम होगी बहुत अधिक पढ़ना और फ़िल्टर करना (पोस्टप्रोसेसिंग) है
  
• यदि ब्लॉक एक सामान्य क्वेरी से काफी छोटा है, तो खोज अक्षम होगी कई प्रश्नों को पंक्ति द्वारा पंक्तिबद्ध करना होगा
  
• यदि ब्लॉक में औसतन बहुत अधिक या बहुत कम डेटा है, तो खोज अप्रभावी होगी
  
• यदि डेटा को क्लस्टर किया गया है (उदाहरण के लिए, नक्शे पर घर पर), तो खोज हर जगह प्रभावी नहीं होगी
• यदि डेटासेट बड़ा हो गया है, तो यह अच्छी तरह से पता चल सकता है कि ब्लॉक आकार इष्टतम हो गया है।
  

आंशिक रूप से, इन समस्याओं को बहु-स्तरीय ब्लॉकों के निर्माण से हल किया जाता है। एक ही उदाहरण के लिए:

• अभी भी 1024X1024 ब्लॉक चाहते हैं
• लेकिन अब हमारे पास अभी भी आकार के शीर्ष स्तर के ब्लॉक 8X8 निचले ब्लॉक होंगे
• कुंजी को निम्नानुसार व्यवस्थित किया गया है (निम्न से उच्च तक):
  3 अंक - अंक 10 ... 12 X निर्देशांक
  3 अंक - अंक 10 ... 12 Y निर्देशांक
  3 अंक - अंक 13 ... 15 X निर्देशांक
  3 अंक - अंक 13 ... 15 Y निर्देशांक

7 निम्न-स्तरीय ब्लॉक उच्च-स्तरीय ब्लॉक बनाते हैं

अब बड़े विस्तार के लिए आपको बड़ी संख्या में छोटे ब्लॉकों को पढ़ने की आवश्यकता नहीं है, यह उच्च-स्तरीय ब्लॉकों की कीमत पर किया जाता है।

दिलचस्प है, निर्देशांक को मोटा करना संभव नहीं था, लेकिन उसी तरह से उन्हें कुंजी में निचोड़ना था। इस मामले में, पोस्ट-फिल्टरिंग सस्ता होगा क्योंकि सूचकांक पढ़ते समय होता है।

स्थानिक जीआरआईडी इंडेक्स को एमएस SQL में एक समान तरीके से व्यवस्थित किया जाता है, उनमें 4 ब्लॉक स्तर तक की अनुमति दी जाती है।


अंजीर। GRID सूचकांक

प्रत्यक्ष अनुक्रमण का एक और दिलचस्प तरीका अंतरिक्ष के बाहरी विभाजन के लिए एक चौकोर पेड़ का उपयोग करना है।

क्वाड ट्री इस मायने में उपयोगी है कि यह वस्तुओं के घनत्व के अनुकूल हो सकता है जब नोड ओवरफ्लो होता है, तो यह विभाजित होता है। नतीजतन, जहां वस्तुओं का घनत्व अधिक होता है, ब्लॉक छोटे और इसके विपरीत निकल जाएंगे। यह खाली इंडेक्स कॉल की संख्या को कम करता है।

सच है, क्वाड ट्री मक्खी पर पुनर्निर्माण के लिए एक असुविधाजनक निर्माण है, यह समय-समय पर ऐसा करना फायदेमंद है।

सुखद बात से, जब एक क्वाड ट्री का पुनर्निर्माण होता है, तो इंडेक्स को फिर से बनाने की आवश्यकता नहीं होती है यदि मोर्टन कोड द्वारा ब्लॉकों की पहचान की जाती है और ऑब्जेक्ट इसका उपयोग करके एन्कोडेड होते हैं। यहां यह चाल है: यदि बिंदु के निर्देशांक एक मोर्टन कोड के साथ एन्कोड किए गए हैं, तो पृष्ठ पहचानकर्ता उस कोड में एक उपसर्ग है। पृष्ठ डेटा की खोज करते समय, सभी कुंजियाँ जो [उपसर्ग] 00 ... 00B से [उपसर्ग] 11 ... 11B की सीमा में होती हैं, यदि पृष्ठ विभाजित किया जाता है, तो इसका अर्थ है कि उसके वंश का केवल उपसर्ग लंबा हो गया है।

स्वयं जैसी सुविधाएँ

आत्म-समान कार्यों का उल्लेख करते समय पहली बात जो ध्यान में आती है वह है "स्वीपिंग कर्व्स"। "ध्यान देने योग्य वक्र एक निरंतर मानचित्रण है, जिसका डोमेन इकाई खंड [0, 1] है, और डोमेन यूक्लिडियन (अधिक सख्ती से, सामयिक) स्थान है।" एक उदाहरण पीनो वक्र है।


अंजीर। पीनो कर्व के पहले 9 पुनरावृत्तियों

निचले बाएं कोने में परिभाषा क्षेत्र (और फ़ंक्शन का शून्य मान) की शुरुआत है, ऊपरी दाएं कोने में अंत (और 1) है, हर बार जब हम 1 कदम बढ़ाते हैं, तो मूल्य में 1 / (एन * एन) जोड़ें (बशर्ते कि एन - डिग्री 3, निश्चित रूप से)। नतीजतन, ऊपरी दाएं कोने में मान 1 तक पहुंचता है। यदि हम प्रत्येक चरण पर एक जोड़ते हैं, तो ऐसा फ़ंक्शन बस वर्ग जाली को क्रमिक रूप से संख्या देता है, जो कि हम चाहते थे।

सभी व्यापक वक्र स्व-समान हैं। इस मामले में, सिम्प्लेक्स एक 3x3 वर्ग है। प्रत्येक पुनरावृत्ति पर, सिम्पलेक्स का प्रत्येक बिंदु समान सिम्प्लेक्स में बदल जाता है, निरंतरता सुनिश्चित करने के लिए, आपको मैपिंग (फ़्लिप) का सहारा लेना होगा।

स्व - समानता हमारे लिए एक बहुत ही महत्वपूर्ण गुण है। यह खोज के लघुगणक मूल्य के लिए आशा देता है। उदाहरण के लिए, एक 3x3 सिम्प्लेक्स के लिए, विस्तार के बाद के पुनरावृत्तियों द्वारा 9 प्राथमिक वर्गों में से प्रत्येक के भीतर उत्पन्न सभी संख्याएं एक ही सीमा के भीतर होंगी। सिर्फ इसलिए कि संख्या शुरू से ही यात्रा का मार्ग है। यानी यदि आप सीमा को 9 भागों में विभाजित करते हैं, तो उनमें से प्रत्येक की सामग्री एक सूचकांक के निशान से प्राप्त की जा सकती है। और इसलिए पुनरावर्ती रूप से, प्रत्येक वर्ग के 9 उप-वर्गों में से प्रत्येक को सूचकांक पर एक क्वेरी द्वारा प्राप्त किया जा सकता है (हालांकि एक छोटी सी सीमा में)। इसलिए खोज सीमा को छोटी संख्या में वर्ग उप-श्रेणियों में तोड़ा जा सकता है, या तो पूरे या फ़िल्टरिंग (परिधि के आसपास) में पढ़ा जा सकता है। चित्र 9 हरे रंग में खोज की सीमा को दिखाता है, जो लाल रेखाओं द्वारा उप-श्रेणियों में टूट गया है।

हालांकि, आत्म-समानता स्वचालित रूप से नंबरिंग वक्र को अनुक्रमण उद्देश्यों के लिए उपयुक्त नहीं बनाती है।

• वक्र को वर्ग ग्रिड को भरना चाहिए। हम वर्ग जाली के नोड्स में मूल्यों को अनुक्रमित करते हैं और हर बार जब हम जाली पर उपयुक्त नोड की तलाश नहीं करना चाहते हैं, उदाहरण के लिए, एक त्रिकोणीय। कम से कम गोलाई के साथ समस्याओं से बचने के लिए। यहाँ, उदाहरण के लिए, (चित्र 10)
  
  
  चित्र 10 टेरीनरी झील कोखा
  
  वक्र हमें शोभा नहीं देता। हालांकि, यह सतह को पूरी तरह से "पुल" करता है।
  
• वक्र अंतराल के बिना अंतरिक्ष को भरना चाहिए ( भग्न आयाम डी = 2)। यहाँ यह है (चित्र 11):
  
  11 अनाम भग्न वक्र
  
  भी फिट नहीं है।
  
• नंबरिंग फ़ंक्शन के मूल्य (शुरुआत से वक्र के साथ यात्रा की गई पथ) को आसानी से गणना की जानी चाहिए। यह इस प्रकार है कि अस्पष्टता उत्पन्न होने के कारण, स्व-स्पर्श वक्र उपयुक्त नहीं हैं, जैसे सीरपिन्स्की वक्र
  
  
  अंजीर। 12 Sierpinski वक्र
  
  या, जो (हमारे लिए) समान है, " सेसरो के साथ त्रिकोण गुजर रहा है "
  
  
  अंजीर। 13 सेसरो त्रिकोण, स्पष्टता के लिए, सही कोण को 85 ° से बदल दिया जाता है
• नंबरिंग फ़ंक्शन में पैरामीटर नहीं होना चाहिए, वक्र समान होना चाहिए (समरूपता के लिए सटीक)। . : ( )
  
  
  . 14 “A Plane Filling Curve for the Year 2017”
  
  , ( ) .
  , , , .

आइसोट्रॉपी एक और महत्वपूर्ण विशेषता है। यह समझा जाता है कि नंबरिंग फ़ंक्शन को आसानी से उच्च आयामों के लिए सामान्य बनाना चाहिए। और यह अच्छा है यदि एन-डायमेंशनल क्यूब के लिए आयामों (एन -1) पर उसके सभी एन अनुमानों समान हैं। यह इस तथ्य से निम्न है कि हम आइसोट्रोपिक स्थान का उपयोग करते हैं और यह अजीब होगा अगर अलग-अलग कुल्हाड़ियों का उपयोग कार्यों में अलग-अलग तरीके से किया गया हो।


अंजीर। 15 एक 3x3x3 पीनो वक्र

आइसोट्रॉपी के तीन आयामी सिम्प्लेक्स एक सख्त आवश्यकता नहीं है, लेकिन यह एक नंबरिंग वक्र की गुणवत्ता का एक महत्वपूर्ण संकेतक है। निरंतरता के

बारे में ।

ऊपर, हमने निरंतर संख्या वाले कार्यों के उदाहरण देखे जो हमारे उद्देश्यों के लिए उपयुक्त नहीं थे। दूसरी ओर, ब्लॉक के साथ काफी असंतत लाइन स्कैन फ़ंक्शन इसके लिए बहुत अच्छा है (कुछ सीमाओं के साथ)। इतना ही नहीं, अगर हमने निरंतर इंटरलेक्टेड स्कैनिंग के आधार पर एक ब्लॉक इंडेक्स बनाया है, तो इससे प्रदर्शन के मामले में कुछ भी नहीं बदलेगा। क्योंकि अगर ब्लॉक को पूरा पढ़ा जाता है, तो वस्तुओं को प्राप्त करने के क्रम में कोई अंतर नहीं होता है।

स्व-समान वक्रों के लिए भी यह सत्य है।

• चलिए पृष्ठ का आकार, डिस्क पृष्ठ पर सभी वस्तुओं का सीमा क्षेत्र कहते हैं
  
• विशेषता आकार औसत पृष्ठ क्षेत्र होगा
• ( ) , . , . — . .
• — , .. .
  
• , . , , . , , — () 3...10% () Z-.
  
  — , .

जो कहा गया है, उससे यह पता चलता है कि बहुआयामी अनुक्रमण के प्रयोजनों के लिए, केवल वर्ग (हाइपरकुबिक) सिम्प्लेक्स को कई बार आवश्यकतानुसार (जाली के पर्याप्त विवरण के लिए) पुनरावर्ती रूप से लागू किया जाता है।

हां, एक वर्ग जाली को पाटने के अन्य स्व-समान तरीके हैं, हालांकि, इस तरह के परिवर्तन को विपरीत करने के लिए कोई कम्प्यूटेशनल सस्ता तरीका नहीं है। शायद ऐसी संख्यात्मक चालें मौजूद हैं, लेकिन वे लेखक को नहीं जानते हैं। इसके अलावा, वर्गाकार सिम्प्लेक्स निर्देशांक में से एक के साथ कटौती द्वारा उप-प्रकारों में खोज की सीमा को प्रभावी ढंग से विभाजित करना संभव बनाता है । सिंप्लेक्स के बीच टूटी हुई सीमा के साथ, यह असंभव है ।

सिंप्लेक्स स्क्वायर क्यों हैं और आयताकार नहीं हैं? आइसोट्रॉपी के कारणों के लिए।

यह सिंप्लेक्स (बाईपास) के अंदर उचित आकार और संख्या का चयन करने के लिए बनी हुई है। एक सिंप्लेक्स

के आकार को चुनने के लिए , आपको यह पता लगाने की आवश्यकता है कि यह क्या प्रभावित करता है। खोज के दौरान उत्पन्न होने वाली उप-श्रेणियों की संख्या। उदाहरण के लिए, एक पीनो वक्र का एक सिम्प्लेक्स 3X3 3 संख्याओं में कट जाता है जिसमें संख्याओं के निरंतर अंतराल होते हैं, पहले X में और फिर उनमें से प्रत्येक को Y में 3 भागों में। परिणामस्वरूप, हम पुनरावृत्ति के अगले चरण में लौट आते हैं। यदि हमारे पास समान (इंटरलेस्ड) सिम्प्लेक्स 5X5 था, तो उसे 5 भागों में काटना होगा। या असमान भागों में (उदा: 2 + 3), जो अजीब है।

यह कुछ तरीकों से खोज के पेड़ों की याद दिलाता है - आप निश्चित रूप से, 5-दशमलव और 7-दशमलव दोनों पेड़ों का उपयोग कर सकते हैं, लेकिन व्यवहार में केवल द्विआधारी का उपयोग किया जाता है। त्रिमूर्ति वृक्षउपसर्ग द्वारा खोजने के लिए अपने स्वयं के संकीर्ण आला है। और यह बिल्कुल वैसा नहीं है जैसा कि सहज ज्ञान युक्त वृक्षों के रूप में समझा जाता है।

इसे दक्षता द्वारा समझाया गया है। एक टर्नरी नोड में, एक वंश का चयन करने के लिए, किसी को 2 तुलना करना होगा। एक द्विआधारी पेड़ में, यह 4 विकल्पों में से एक विकल्प से मेल खाती है। छोटी पेड़ों की गहराई भी उत्पादकता की हानि की तुलना में वृद्धि की संख्या से नहीं रोकती है।

इसके अलावा, अगर 3X3 केवल 2X2 से अधिक प्रभावी थे, क्योंकि 3> 2, 4X4 3X3 से अधिक प्रभावी होगा, और 8X8 5X5 से अधिक प्रभावी होगा। आप हमेशा दो की उपयुक्त शक्ति पा सकते हैं, जो 2X2 के कई पुनरावृत्तियों द्वारा बनाई गई है ...

और सिम्पलेक्स बाईपास से क्या प्रभावित होता है ? सबसे पहले, खोज द्वारा उत्पन्न उपश्रेणियों की संख्या। क्योंकियह अच्छा है अगर सिंप्लेक्स आपको संख्याओं के निरंतर अंतराल के साथ खुद को टुकड़ों में काटने की अनुमति देता है। यहाँ Peano 3X3 अनुमति देता है, इसलिए एक पुनरावृत्ति इसे 3 भागों में काटती है। और अगर आप एक शतरंज शूरवीर (छवि 16) के साथ 8x8 सिम्प्लेक्स लेते हैं, तो एकमात्र विकल्प तुरंत 64 तत्व हैं।


अंजीर। 16 8x8 सिम्प्लेक्स को दरकिनार करने के लिए विकल्पों में से एक

इसलिए, क्योंकि हमें पता चला कि इष्टतम सिम्प्लेक्स 2x2 है, हमें विचार करना चाहिए कि इसके लिए क्या विकल्प मौजूद हैं।


अंजीर। 2x2 सिम्प्लेक्स को दरकिनार करने के लिए 17 विकल्प

उनमें से केवल तीन हैं, समरूपता तक, हम पारंपरिक रूप से "जेड", "ओमेगा" और "अल्फा" के रूप में कहेंगे।
यह तुरंत आंख को पकड़ता है कि "अल्फा" खुद को पार करता है, और इसलिए बाइनरी बंटवारे के लिए अनुपयुक्त है। इसे तुरंत 4 भागों में काटना होगा। या 8-आयामी मामले में 256।

विभिन्न आयामों के रिक्त स्थान के लिए एकल एल्गोरिथ्म का उपयोग करने की क्षमता (जिसे हम "अल्फा" जैसे वक्र के मामले में वंचित करते हैं) बहुत आकर्षक लगता है। इसलिए, भविष्य में हम केवल पहले दो विकल्पों पर विचार करेंगे।


अंजीर।


एफआईजी का 18 जेड-वक्र । 19 "ओमेगा" - हिल्बर्ट वक्र।

एक बार इन वक्रों की करीबी रिश्तेदारी होने के बाद, उन्हें एक एल्गोरिथ्म के साथ संसाधित किया जा सकता है। वक्री की मुख्य विशिष्टता उपकुंजी के विभाजन में स्थानीयकृत है।

• पहले हम शुरू की सीमा पाते हैं, यह न्यूनतम आयत है जिसमें खोज सीमा शामिल है और इसमें प्रमुख मूल्यों का एक निरंतर अंतराल होता है।
  यह इस प्रकार पाया जाता है -
  
  • खोज सीमा के निचले बाएँ और ऊपरी दाएँ बिंदु (KMin, KMax) के लिए मुख्य मानों की गणना करें
    
  • ( ) KMin, KMax
    
  • , SMin, , SMax
    
  • . , , SMin, . .
  • , , ( ).
    
  • Z- . z- — , — ( ). , , .
• • , , . ,
  • , . — “ ” >= “ ” () , “ ”
    
    
    • “ ” > , ,
      
    • , ,
      
    • “ ” > , , ,
    • अलग मामला "अंतिम कुंजी" == वर्तमान सबक्वेरी का अधिकतम मूल्य, आगे की ओर ट्रैवर्स द्वारा अलग से संसाधित
      
  • वर्तमान उप-विभाजन को विभाजित करें
    • इसके उपसर्ग में 0 और 1 जोड़ें - हमें दो नए उपसर्ग मिलते हैं
    • कुंजी 0 या 1 के शेष भाग में भरें - हमें नई उपश्रेणियों के न्यूनतम और अधिकतम मान मिलते हैं
    • हम उन्हें स्टैक पर धक्का देते हैं, पहले वह जो 1 पूरक था, फिर 0. यह सूचकांक के अप्रत्यक्ष रूप से पढ़ने के लिए है।
  
  

Z- वक्र पर, यह इस तरह काम करता है:


अंजीर। 20 - जेड-वक्र के मामले में उप-क्वेरी विभाजन


अंजीर। 21 हिल्बर्ट वक्र, मामला जब शुरुआती सीमा अधिकतम है

पहला चरण यहाँ दिखाया गया है - अधिकतम सीमा से अतिरिक्त परत को काटकर।


अंजीर। 22 हिल्बर्ट कर्व, खोज क्वेरी क्षेत्र

और यहां खोज क्वेरी क्षेत्र में उपश्रेणियों, अंक मिले, और सूचकांक कॉल में एक ब्रेकडाउन है। हिल्बर्ट वक्र के संदर्भ में यह अभी भी एक बहुत ही असफल क्वेरी है। आमतौर पर सब कुछ बहुत कम खूनी होता है।

हालाँकि, क्वेरी आँकड़े कहते हैं कि (लगभग) एक ही डेटा पर, हिल्बर्ट वक्र पर आधारित एक दो-आयामी सूचकांक औसतन 5% कम डिस्क पृष्ठ पढ़ता है, लेकिन यह आधे धीमे काम करता है। मंदी भी इस तथ्य के कारण है कि इस वक्र की गणना स्वयं (प्रत्यक्ष और रिवर्स) बहुत कठिन है - जेड-वक्र के लिए 50 की तुलना में हिल्बर्ट के लिए 2000 प्रोसेसर चक्र।

हिल्बर्ट वक्र का समर्थन करना बंद करके, एल्गोरिथ्म को सरल बनाया जा सकता है, पहली नज़र में, ऐसी मंदी का औचित्य नहीं है। दूसरी ओर, यह सिर्फ एक दो-आयामी मामला है, उदाहरण के लिए, 8-आयामी स्थान या अधिक में, आंकड़े पूरी तरह से अलग रंगों के साथ चमक सकते हैं। इस मुद्दे पर अभी भी स्पष्टीकरण का इंतजार है।

पुनश्च : मान की गणना के लिए एल्गोरिथ्म के कारण जेड-वक्र को कभी-कभी बिट-इंटरलेइंग वक्र कहा जाता है - निर्देशांक में से प्रत्येक के अंक एक के माध्यम से महत्वपूर्ण मूल्य में आते हैं, जो बहुत ही तकनीकी है। लेकिन आप कर सकते हैं, सब के बाद, अलग-अलग नहीं, बल्कि 2.3 ... 8 ... टुकड़ों के पैक को डिस्चार्ज करें। अब, यदि हम 8 बिट्स लेते हैं, तो 32-बिट कुंजी पर हमें MS SQL से 4-स्तरीय GRID इंडेक्स का एनालॉग मिलता है। और एक चरम मामले में - प्रत्येक 32 बिट्स का एक पैकेट - एक क्षैतिज स्कैनिंग एल्गोरिदम।

इस तरह के एक सूचकांक (कम नहीं, निश्चित रूप से) बहुत प्रभावी हो सकता है, यहां तक ​​कि कुछ डेटा सेटों पर जेड-वक्र की तुलना में अधिक कुशल है। दुर्भाग्य से, सामान्यता के नुकसान के कारण।

PPS : वर्णित इंडेक्स क्वाड ट्री के साथ काम करने के समान है। अधिकतम सीमा क्वाड ट्री का मूल पृष्ठ है, इसमें 4 वंशज हैं ... और इसलिए, एल्गोरिथ्म को "सीधी पहुंच विधियों" के लिए जिम्मेदार ठहराया जा सकता है।

अंतर अभी भी मौलिक हैं।

क्वाड ट्री को कहीं भी संग्रहीत नहीं किया गया है, यह संख्याओं की प्रकृति में अंतर्निहित आभासी है। पेड़ की गहराई पर कोई प्रतिबंध नहीं है, हम मुख्य पेड़ की आबादी से वंशजों की आबादी के बारे में जानकारी प्राप्त करते हैं। इसके अलावा, मुख्य पेड़ एक बार पढ़ा जाता है, हम सबसे छोटे से सबसे पुराने मूल्यों तक जाते हैं। यह हास्यास्पद है, लेकिन बी-ट्री की भौतिक संरचना खाली प्रश्नों से बचने और पुनरावृत्ति की गहराई को सीमित करना संभव बनाती है।

एक और बात - प्रत्येक पुनरावृत्ति पर केवल दो वंशज दिखाई देते हैं - उनमें से 4 उपश्रेणियाँ उत्पन्न की जा सकती हैं, और उनके तहत कोई डेटा नहीं होने पर उत्पन्न नहीं किया जा सकता है। 3-आयामी मामले में, हम 8 वंशजों के बारे में बात करेंगे, 8-आयामी मामले में - लगभग 256।

PPPS : इस लेख की शुरुआत में, हमने डायोडोटॉमी के बारे में बात की जब एक बहुआयामी सूचकांक में खोज की जाती है - लॉगरिदमिक मान प्राप्त करने के लिए, यह आवश्यक है कि कुछ परिमित संसाधनों को या तो पुनरावृत्ति में विभाजित किया जाए - या तो कुंजी स्थान या खोज स्थान। प्रस्तुत एल्गोरिथ्म में, यह द्विभाजन ध्वस्त हो गया - हम एक साथ कुंजी और स्थान दोनों साझा करते हैं।

"मैं दोनों गज में रहता हूँ, और मेरे पेड़ हमेशा ऊँचे होते हैं।" ( सी )

PPPPS : जैसे ही वे Z-वक्र कहते हैं, यहां आपके पास Z- ऑर्डर और बिट-इंटरलेविंग और मॉर्टन कोड / वक्र है। इसे लेबेस लीग वक्र के रूप में भी जाना जाता है, इसलिए संतुलन बनाए रखने के लिए, लेखक ने लेख का हकदार बनाया, जिसमें हेनरी लियोन रॉबर्ट्स के सम्मान में भी शामिल था।

PPPPPS : शीर्षक चित्रण में, फेडचेनो ग्लेशियर का दृश्य बस सुंदर है, और पर्याप्त खालीपन है। वास्तव में, लेखक इस बात से प्रभावित था कि अलग-अलग विचार और तरीके एक दूसरे में आसानी से कैसे प्रवाहित होते हैं, धीरे-धीरे एक एल्गोरिथ्म में विलय हो जाते हैं। बस कई छोटे पानी के स्रोत हैं जो जलग्रहण क्षेत्र को एक अपवाह बनाते हैं।