अनुक्रमणिका और अभिगम विधियाँ

अनुक्रमणिकाएँ और अभिगम विधियाँ सहायक डेटा संरचनाएँ हैं — मुख्य रूप से B+-ट्री और हैश अनुक्रमणिकाएँ — जो एक डेटाबेस को पूरी तालिका को स्कैन किए बिना मिलान करने वाले टुपल्स का पता लगाने देती हैं, जिससे तेज़ अभिगम पथ मिलते हैं जिन पर ऑप्टिमाइज़र निर्भर करता है।

Definition

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

Scope

यह विषय डेटा अभिगम पथों के पीछे की संरचनाओं और अवधारणाओं को शामिल करता है: क्लस्टर्ड और अनक्लस्टर्ड, प्राथमिक और द्वितीयक अनुक्रमणिकाओं के बीच का अंतर; समानता और श्रेणी खोज का समर्थन करने वाले कार्यसाधक क्रमबद्ध अनुक्रमणिका के रूप में B+-ट्री; समानता खोज के लिए हैश-आधारित अनुक्रमणिकाएँ; और चयन, जॉइन और सॉर्ट से बचने में अनुक्रमणिकाओं की भूमिका। यह बताता है कि अनुक्रमणिका का चुनाव क्वेरी लागत और अद्यतन ओवरहेड को कैसे प्रभावित करता है। यह लागत-आधारित ऑप्टिमाइज़र के समग्र योजना चयन को बाहर करता है, जो एक अलग विषय है।

Core questions

• एक B+-ट्री समानता और श्रेणी दोनों क्वेरीज़ को कुशलतापूर्वक कैसे समर्थन देता है?
• क्लस्टर्ड और अनक्लस्टर्ड, प्राथमिक और द्वितीयक अनुक्रमणिकाओं में क्या अंतर है?
• एक ट्री अनुक्रमणिका की तुलना में हैश अनुक्रमणिका कब बेहतर है?
• अनुक्रमणिकाएँ चयन, जॉइन और क्रमबद्ध पुनर्प्राप्ति को कैसे गति देती हैं?
• इन्सर्ट, अपडेट और डिलीट के तहत अनुक्रमणिकाओं को बनाए रखने की लागत क्या है?

Key concepts

• B+-ट्री अनुक्रमणिका
• हैश अनुक्रमणिका
• क्लस्टर्ड बनाम अनक्लस्टर्ड अनुक्रमणिका
• प्राथमिक और द्वितीयक अनुक्रमणिकाएँ
• घनी और विरल अनुक्रमणिकाएँ
• श्रेणी और समानता खोज
• विस्तारणीय और रैखिक हैशिंग
• अनुक्रमणिका रखरखाव लागत

Key theories

B+-ट्री अनुक्रमणिकाएँ

B+-ट्री एक संतुलित, उच्च-फैनआउट सर्च ट्री है जो सभी डेटा संदर्भों के साथ पत्तियों में क्रमबद्ध क्रम में कुंजियों को संग्रहीत करता है; यह लॉगरिदमिक I/O में समानता और श्रेणी क्वेरीज़ और क्रमबद्ध स्कैन का समर्थन करता है और इन्सर्शन और डिलीशन के तहत संतुलित रहता है।

क्लस्टर्ड बनाम अनक्लस्टर्ड अनुक्रमणिकाएँ

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

हैश अनुक्रमणिकाएँ

हैश-आधारित अनुक्रमणिकाएँ कुंजियों को बकेट में मैप करती हैं ताकि अपेक्षित स्थिर-समय समानता लुकअप हो सके लेकिन श्रेणी क्वेरीज़ का समर्थन नहीं करती हैं; विस्तारणीय और रैखिक हैशिंग जैसी गतिशील योजनाएँ उन्हें डेटा के साथ धीरे-धीरे बढ़ने देती हैं।

Clinical relevance

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

History

बेयर और मैकक्रेइट ने 1972 में डिस्क पर बड़े क्रमबद्ध अनुक्रमणिकाओं को बनाए रखने के लिए B-ट्री पेश किया; B+-ट्री संस्करण, जो सभी डेटा को पत्तियों में रखता है, मानक डेटाबेस अनुक्रमणिका बन गया, जैसा कि कॉमर के 1979 के 'यूबिक्विटस B-ट्री' में सर्वेक्षण किया गया है। हैश-आधारित अभिगम विधियाँ और गतिशील हैशिंग योजनाएँ समानांतर में विकसित हुईं, और दोनों परिवार हर संबंधपरक इंजन के मूल में बने हुए हैं।

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

डेटाबेस में बाइनरी सर्च ट्री के बजाय B+-ट्री का उपयोग क्यों किया जाता है?

डेटाबेस डिस्क पर डेटा संग्रहीत करते हैं, जहाँ लागत पृष्ठ रीड की संख्या से निर्धारित होती है। B+-ट्री में उच्च फैनआउट होता है, इसलिए प्रत्येक नोड एक डिस्क पृष्ठ को भरता है और ट्री बहुत उथला होता है, किसी भी रिकॉर्ड तक पहुँचने के लिए केवल कुछ I/O की आवश्यकता होती है। एक बाइनरी ट्री बहुत गहरा होगा और इसमें कई अधिक डिस्क एक्सेस होंगे।

मुझे B+-ट्री के बजाय हैश अनुक्रमणिका का उपयोग कब करना चाहिए?

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