तुलना में बी + ट्री और हैश के साथ संक्षेप में डेटाबेस इंडेक्सिंग

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

अनुक्रमणिका एक डेटा संरचना है जो कुछ प्रकार के पुनर्प्राप्ति कार्यों को अनुकूलित करने के लिए रिकॉर्ड व्यवस्थित करती है। हम तालिका के किसी फ़ील्ड पर अनुक्रमणिका बना सकते हैं और फिर search-key पर खोज शर्तों को पूरा करने वाले सभी रिकॉर्ड पुनर्प्राप्त कर सकते हैं खेत। अनुक्रमणिका के बिना, हमारी क्वेरी केवल एक या कुछ रिकॉर्ड प्राप्त करने के लिए तालिका की संपूर्ण सामग्री को रैखिक रूप से स्कैन करना समाप्त कर देगी।

इस पोस्ट में, मैं दो सामान्य अनुक्रमण तकनीकों के प्रदर्शन और उपयोग के मामलों को सारांशित करना चाहता हूं:हैश अनुक्रमणिका और B+पेड़

हैश इंडेक्स

मेन मेमोरी . में इंडेक्स बनाने के लिए इस तकनीक का व्यापक रूप से उपयोग किया जाता है क्योंकि इसकी प्रकृति द्वारा तेजी से पुनर्प्राप्ति। इसमें औसत ओ (1) ऑपरेशन जटिलता और ओ (एन) भंडारण जटिलता है।
कई किताबों में लोग bucket . शब्द का इस्तेमाल करते हैं भंडारण की एक इकाई को निरूपित करने के लिए जो एक या अधिक रिकॉर्ड संग्रहीत करता है
जब हैशिंग की बात आती है तो दो बातों पर चर्चा होती है:

• हैश फ़ंक्शन:बाल्टी में उस कुंजी का प्रतिनिधित्व करने वाले पूर्णांक में खोज कुंजी (इसके इनपुट के रूप में) को मैप करता है।
• हैशिंग योजना:हैशिंग के बाद मुख्य टक्कर से कैसे निपटें।

कुछ लोग पूछते हैं:टक्कर क्यों? क्या एक आदर्श हैश फ़ंक्शन कभी मौजूद है? वास्तव में, मान लें कि आपकी चाबियाँ एक अनंत सेट हैं, बिना किसी टकराव के उन्हें 32-बिट पूर्णांक के सेट में मैप करना असंभव है। गणना और टक्कर दर के बीच एक समझौता होना चाहिए।

उल्लेख के लायक कुछ हैशिंग योजनाएं हैं:रैखिक जांच, जंजीर हैशिंग और विस्तार योग्य हैशिंग। लुकअप/इन्सर्ट/डिलीट एल्गोरिदम हैशिंग स्कीम के अनुसार अलग-अलग होते हैं, उदाहरण के लिए, एक ही बाल्टी में समान हैश मान वाले तत्वों को रखकर प्रमुख टकरावों के साथ जंजीर हैशिंग डील।

पेशेवर

• हैश इंडेक्स समानता या प्राथमिक कुंजी लुकअप के लिए उपयुक्त है। परिशोधन O(1) लुकअप लागत प्राप्त करने के लिए क्वेरीज़ हैश इंडेक्स से लाभ उठा सकती हैं। उदाहरण के लिए:SELECT name, id FROM student WHERE id = '1315';

विपक्ष

हैश तालिका की कुछ सीमाएँ हैं:

• श्रेणी क्वेरी कुशल नहीं हैं। हैश तालिका समान वितरण पर आधारित है। दूसरे शब्दों में, आपके पास इस पर कोई नियंत्रण नहीं है कि अनुक्रमणिका प्रविष्टि कहाँ रखी जाएगी।
• निम्न मापनीयता:जब बहुत सारी टक्करें होती हैं तो लुकअप ऑपरेशन का प्रदर्शन खराब हो सकता है और इसके लिए हैश तालिका का आकार बदलने की आवश्यकता होती है और फिर मौजूदा अनुक्रमणिका प्रविष्टियों को दोबारा दोहराएं।

B+ट्री

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

बी+ट्री मूल रूप से एक एम-वे सर्च ट्री है जिसकी संरचना निम्नलिखित है:

• पूरी तरह से संतुलन:लीफ नोड्स की ऊंचाई हमेशा समान होती है।
• रूट के अलावा हर आंतरिक नोड कम से कम आधा भरा हुआ है (एम/2 - 1 <=चाबियों की संख्या <=एम -1)।
• k कुंजी वाले प्रत्येक आंतरिक नोड में k+1 गैर-शून्य बच्चे होते हैं।

पेड़ के प्रत्येक नोड में क्रमबद्ध कुंजी-मूल्य जोड़े की एक सरणी होती है। की-वैल्यू पेयर रूट और इनर नोड्स के लिए (सर्च-की वैल्यू, पॉइंटर) से बनाया गया है। लीफ नोड मान 2 संभावनाएं हो सकती हैं:

• वास्तविक रिकॉर्ड
• वास्तविक रिकॉर्ड का सूचक

एक मान देखें v

• रूट नोड से शुरू करें
• जबकि नोड एक लीफ नोड नहीं है, हम करते हैं:
  • सबसे छोटा Ki ढूंढें जहां Ki>=v
  • यदि Ki ==v:वर्तमान नोड को Pi+1 द्वारा इंगित नोड पर सेट करें
  • अन्यथा, वर्तमान नोड को Pi द्वारा इंगित नोड पर सेट करें

डुप्लीकेट कुंजियां

सामान्य तौर पर, खोज-कुंजी डुप्लिकेट हो सकती है, इसे हल करने के लिए, अधिकांश डेटाबेस कार्यान्वयन समग्र खोज कुंजी के साथ आते हैं। उदाहरण के लिए, हम student_name . पर एक इंडेक्स बनाना चाहते हैं तो हमारी समग्र खोज कुंजी होनी चाहिए (student_name, एपी) जहां एपी तालिका की प्राथमिक कुंजी है।

पेशेवर

B+tree दो प्रमुख विशेषताएं प्रदान करता है:

• I/O संचालन को कम करना
  • कम ऊंचाई:बी+ट्री में काफी बड़ा ब्रांचिंग फैक्टर होता है (50 और 2000 के बीच का मान अक्सर इस्तेमाल किया जाता है) जो पेड़ को मोटा और छोटा बनाता है। नीचे दिया गया आंकड़ा 2 की ऊंचाई के साथ एक बी + ट्री को दिखाता है। जैसा कि हम देख सकते हैं कि नोड्स फैले हुए हैं, यह एक पत्ती तक जाने के लिए कम नोड्स लेता है। तालिका में रैंडम एक्सेस के लिए एकल मान को देखने की लागत पेड़ की ऊंचाई + 1 है।
• मापनीयता:
  • आपके पास सभी मामलों के लिए अनुमानित प्रदर्शन है, विशेष रूप से O(log(n)) । डेटाबेस के लिए, यह आमतौर पर बेहतर सर्वश्रेष्ठ या औसत केस प्रदर्शन की तुलना में अधिक महत्वपूर्ण होता है।
  • पेड़ हमेशा अपने क्रियान्वयन से संतुलित रहता है। n कुंजी वाले A B+ट्री में हमेशा O(log(n)) की गहराई होती है। इस प्रकार, यदि डेटाबेस बड़ा हो जाता है तो प्रदर्शन खराब नहीं होगा। 500 के ब्रांचिंग फैक्टर वाला चार-स्तरीय पेड़ 256 टीबी तक स्टोर कर सकता है बशर्ते कि एक पेज 4KB के आकार का हो।

• बी+ट्री श्रेणी प्रश्नों के लिए सबसे उपयुक्त है, उदाहरण के लिए "SELECT * FROM student WHERE age > 20 AND age < 22"

निष्कर्ष

हालांकि हैश इंडेक्स सटीक मिलान प्रश्नों के मामले में बेहतर प्रदर्शन करता है, लेकिन बी + ट्री यकीनन आरडीबीएमएस में सबसे व्यापक रूप से उपयोग की जाने वाली इंडेक्स संरचना है, जो समग्र और उच्च स्केलेबिलिटी में लगातार प्रदर्शन के कारण है।

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