नमस्ते, हबर! मैं आपके ध्यान में लेख का अनुवाद प्रस्तुत करता हूँ
"रिलेशनल डेटाबेस कैसे काम करता है".

जब संबंधपरक डेटाबेस की बात आती है तो मैं यह सोचे बिना नहीं रह पाता कि कुछ कमी है। इनका प्रयोग हर जगह किया जाता है. छोटे और उपयोगी SQLite से लेकर शक्तिशाली टेराडेटा तक कई अलग-अलग डेटाबेस उपलब्ध हैं। लेकिन ऐसे कुछ ही लेख हैं जो बताते हैं कि डेटाबेस कैसे काम करता है। कितने कम परिणाम हैं यह देखने के लिए आप "howdoesarelationaldatabasework" का उपयोग करके स्वयं खोज सकते हैं। इसके अलावा, ये लेख छोटे हैं। यदि आप नवीनतम बज़ी तकनीकों (बिगडाटा, नोएसक्यूएल या जावास्क्रिप्ट) की तलाश में हैं, तो आपको अधिक गहन लेख मिलेंगे जो बताएंगे कि वे कैसे काम करते हैं।

क्या रिलेशनल डेटाबेस इतने पुराने और इतने उबाऊ हैं कि उन्हें विश्वविद्यालय के पाठ्यक्रमों, शोध पत्रों और पुस्तकों के बाहर समझाया नहीं जा सकता?

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

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

मैं कुछ कंप्यूटर विज्ञान की बुनियादी बातों से शुरुआत करूंगा, जैसे एल्गोरिदम की समय जटिलता (बिगओ)। मैं जानता हूं कि आपमें से कुछ लोग इस अवधारणा से नफरत करते हैं, लेकिन इसके बिना आप डेटाबेस के अंदर की जटिलताओं को नहीं समझ पाएंगे। चूँकि यह एक बहुत बड़ा विषय है, मैं पर ध्यान केंद्रित करूंगा मैं जो सोचता हूं वह महत्वपूर्ण है: डेटाबेस कैसे प्रोसेस करता है एसक्यूएल जांच. मैं अभी परिचय कराता हूँ बुनियादी डेटाबेस अवधारणाएँताकि लेख के अंत में आपको यह अंदाज़ा हो जाए कि हुड के नीचे क्या चल रहा है।

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

आपमें से अधिक जानकार लोगों के लिए, इस लेख को 3 भागों में विभाजित किया गया है:

• निम्न-स्तरीय और उच्च-स्तरीय डेटाबेस घटकों का अवलोकन
• क्वेरी अनुकूलन प्रक्रिया का अवलोकन
• लेनदेन और बफर पूल प्रबंधन का अवलोकन

बुनियादी बातों पर वापस

वर्षों पहले (दूर, बहुत दूर किसी आकाशगंगा में...), डेवलपर्स को यह जानना होता था कि वे कितने ऑपरेशनों को कोड कर रहे हैं। वे अपने एल्गोरिदम और डेटा संरचनाओं को दिल से जानते थे क्योंकि वे अपने धीमे कंप्यूटर के सीपीयू और मेमोरी को बर्बाद नहीं कर सकते थे।

इस भाग में, मैं आपको इनमें से कुछ अवधारणाओं की याद दिलाऊंगा क्योंकि वे डेटाबेस को समझने के लिए आवश्यक हैं। मैं इस अवधारणा का भी परिचय दूंगा डेटाबेस सूचकांक.

O(1) बनाम O(n2)

आजकल, कई डेवलपर्स एल्गोरिदम की समय जटिलता की परवाह नहीं करते हैं... और वे सही हैं!

लेकिन जब आप बहुत सारे डेटा के साथ काम कर रहे हों (मैं हजारों की बात नहीं कर रहा हूं) या यदि आप मिलीसेकंड में संघर्ष कर रहे हैं, तो इस अवधारणा को समझना महत्वपूर्ण हो जाता है। और जैसा कि आप कल्पना कर सकते हैं, डेटाबेस को दोनों स्थितियों से निपटना होगा! मैं आपको बात समझाने के लिए आवश्यकता से अधिक समय बर्बाद नहीं करने दूँगा। इससे हमें बाद में लागत-आधारित अनुकूलन की अवधारणा को समझने में मदद मिलेगी (लागत आधारित इष्टतमीकरण).

संकल्पना

एल्गोरिथम की समय जटिलता यह देखने के लिए उपयोग किया जाता है कि किसी दिए गए डेटा की मात्रा के लिए एल्गोरिदम को निष्पादित करने में कितना समय लगेगा. इस जटिलता का वर्णन करने के लिए, हम बड़े O गणितीय नोटेशन का उपयोग करते हैं। इस नोटेशन का उपयोग एक फ़ंक्शन के साथ किया जाता है जो बताता है कि किसी दिए गए इनपुट की संख्या के लिए एल्गोरिदम को कितने ऑपरेशन की आवश्यकता है।

उदाहरण के लिए, जब मैं कहता हूं "इस एल्गोरिदम में जटिलता O(some_function())" है, तो इसका मतलब है कि एल्गोरिदम को एक निश्चित मात्रा में डेटा संसाधित करने के लिए some_function(a_certain_amount_of_data) संचालन की आवश्यकता होती है।

इस मामले में, यह डेटा की मात्रा नहीं है जो मायने रखती है**, अन्यथा ** डेटा वॉल्यूम बढ़ने के साथ ऑपरेशन की संख्या कैसे बढ़ती है. समय जटिलता संचालन की सटीक संख्या प्रदान नहीं करती है, लेकिन निष्पादन समय का अनुमान लगाने का एक अच्छा तरीका है।

इस ग्राफ़ में आप विभिन्न प्रकार के एल्गोरिदम समय जटिलताओं के लिए इनपुट डेटा की मात्रा बनाम संचालन की संख्या देख सकते हैं। मैंने उन्हें प्रदर्शित करने के लिए एक लघुगणकीय पैमाने का उपयोग किया। दूसरे शब्दों में, डेटा की मात्रा तेजी से 1 से 1 बिलियन तक बढ़ जाती है। हम देख सकते हैं कि:

• O(1) या स्थिर जटिलता स्थिर रहती है (अन्यथा इसे स्थिर जटिलता नहीं कहा जाएगा)।
• O(लॉग इन(n)) अरबों डेटा के साथ भी कम रहता है.
• सबसे बड़ी कठिनाई - O(n2), जहां ऑपरेशनों की संख्या तेजी से बढ़ती है.
• अन्य दो जटिलताएँ भी उतनी ही तेजी से बढ़ती हैं।

उदाहरण

थोड़ी मात्रा में डेटा के साथ, O(1) और O(n2) के बीच अंतर नगण्य है। उदाहरण के लिए, मान लें कि आपके पास एक एल्गोरिदम है जिसे 2000 तत्वों को संसाधित करने की आवश्यकता है।

• O(1) एल्गोरिथम में आपको 1 ऑपरेशन का खर्च आएगा
• O(log(n)) एल्गोरिथम में आपको 7 ऑपरेशनों का खर्च आएगा
• O(n) एल्गोरिथम में आपको 2 ऑपरेशनों का खर्च आएगा
• O(n*log(n)) एल्गोरिथम में आपको 14 ऑपरेशनों का खर्च आएगा
• O(n2) एल्गोरिदम पर आपको 4 ऑपरेशन का खर्च आएगा

O(1) और O(n2) के बीच का अंतर बड़ा लगता है (4 मिलियन ऑपरेशन) लेकिन आप अधिकतम 2 एमएस खो देंगे, बस अपनी आँखें झपकाने का समय। दरअसल, आधुनिक प्रोसेसर प्रोसेस कर सकते हैं प्रति सेकंड करोड़ों ऑपरेशन. यही कारण है कि कई आईटी परियोजनाओं में प्रदर्शन और अनुकूलन कोई मुद्दा नहीं है।

जैसा कि मैंने कहा, भारी मात्रा में डेटा के साथ काम करते समय इस अवधारणा को जानना अभी भी महत्वपूर्ण है। यदि इस बार एल्गोरिदम को 1 तत्वों को संसाधित करना है (जो डेटाबेस के लिए उतना अधिक नहीं है):

• O(1) एल्गोरिथम में आपको 1 ऑपरेशन का खर्च आएगा
• O(log(n)) एल्गोरिथम में आपको 14 ऑपरेशनों का खर्च आएगा
• O(n) एल्गोरिथम में आपको 1 ऑपरेशन का खर्च आएगा
• O(n*log(n)) एल्गोरिदम पर आपको 14 ऑपरेशनों का खर्च आएगा
• O(n2) एल्गोरिदम पर आपको 1 ऑपरेशन का खर्च आएगा

मैंने गणित नहीं किया है, लेकिन मैं कहूंगा कि O(n2) एल्गोरिथम के साथ आपके पास एक कॉफ़ी पीने का समय है (दो भी!)। यदि आप डेटा वॉल्यूम में एक और 0 जोड़ते हैं, तो आपके पास झपकी लेने का समय होगा।

आइए गहराई में जाएं

आपकी जानकारी के लिए:

• एक अच्छा हैश टेबल लुकअप O(1) में एक तत्व ढूंढता है।
• एक अच्छी तरह से संतुलित पेड़ की खोज करने से O(log(n)) में परिणाम मिलते हैं।
• किसी सरणी को खोजने से O(n) में परिणाम प्राप्त होते हैं।
• सर्वोत्तम सॉर्टिंग एल्गोरिदम में जटिलता O(n*log(n)) होती है।
• एक ख़राब सॉर्टिंग एल्गोरिदम में जटिलता O(n2) होती है।

नोट: निम्नलिखित भागों में हम इन एल्गोरिदम और डेटा संरचनाओं को देखेंगे।

एल्गोरिथम समय जटिलता के कई प्रकार हैं:

• औसत मामला परिदृश्य
• बेहतरीन परिदृश्य
• और सबसे खराब स्थिति

समय की जटिलता अक्सर सबसे खराब स्थिति होती है।

मैं केवल एल्गोरिदम की समय जटिलता के बारे में बात कर रहा था, लेकिन जटिलता इस पर भी लागू होती है:

• एल्गोरिथ्म की मेमोरी खपत
• डिस्क I/O खपत एल्गोरिदम

बेशक, n2 से भी बदतर जटिलताएँ हैं, उदाहरण के लिए:

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

नोट: मैंने आपको बड़े O पदनाम की वास्तविक परिभाषा नहीं दी, बस एक विचार दिया। आप इस लेख को यहां पढ़ सकते हैं विकिपीडिया वास्तविक (स्पर्शोन्मुख) परिभाषा के लिए।

मर्ज़ सॉर्ट

जब आपको किसी संग्रह को क्रमबद्ध करने की आवश्यकता होती है तो आप क्या करते हैं? क्या? आप सॉर्ट() फ़ंक्शन को कॉल करते हैं... ठीक है, अच्छा उत्तर है... लेकिन डेटाबेस के लिए, आपको यह समझना होगा कि यह सॉर्ट() फ़ंक्शन कैसे काम करता है।

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

मर्ज

कई उपयोगी एल्गोरिदम की तरह, मर्ज सॉर्ट एक ट्रिक पर निर्भर करता है: आकार एन/2 के 2 सॉर्ट किए गए एरे को एन-एलिमेंट सॉर्ट किए गए एरे में संयोजित करने से केवल एन ऑपरेशन की लागत आती है। इस ऑपरेशन को मर्जिंग कहा जाता है।

आइए एक सरल उदाहरण से देखें कि इसका क्या अर्थ है:

यह आंकड़ा दिखाता है कि अंतिम क्रमबद्ध 8-तत्व सरणी बनाने के लिए, आपको केवल 2 4-तत्व सरणी पर एक बार पुनरावृति करने की आवश्यकता है। चूँकि दोनों 4-तत्व सरणियाँ पहले से ही क्रमबद्ध हैं:

• 1) आप दोनों वर्तमान तत्वों की तुलना दो सरणियों में करते हैं (शुरुआत में वर्तमान = पहले)
• 2) फिर इसे 8 तत्व सरणी में डालने के लिए सबसे छोटा लें
• 3) और सरणी में अगले तत्व पर जाएं जहां आपने सबसे छोटा तत्व लिया था
• और 1,2,3 को तब तक दोहराएँ जब तक आप किसी एक सरणी के अंतिम तत्व तक नहीं पहुँच जाते।
• फिर आप अन्य सरणी के शेष तत्वों को 8 तत्वों वाली सरणी में डालने के लिए लेते हैं।

यह काम करता है क्योंकि दोनों 4-तत्व सरणी क्रमबद्ध हैं और इसलिए आपको उन सरणी में "वापस जाने" की ज़रूरत नहीं है।

अब जब हम चाल को समझ गए हैं, तो मर्ज के लिए मेरा छद्म कोड यहां है:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

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

• विभाजन चरण, जहां सारणी को छोटे सारणियों में विभाजित किया जाता है
• सॉर्टिंग चरण वह है जहां एक बड़ी सरणी बनाने के लिए छोटी सारणियों को संयोजित किया जाता है (संघ का उपयोग करके)।

विभाजन चरण

विभाजन चरण में, सारणी को 3 चरणों में एकात्मक सारणियों में विभाजित किया जाता है। चरणों की औपचारिक संख्या लॉग(एन) है (चूंकि एन=8, लॉग(एन) = 3)।

मुझे इसके बारे में कैसे पता है?

मैं प्रतिभाशाली हूँ! एक शब्द में - गणित. विचार यह है कि प्रत्येक चरण मूल सरणी के आकार को 2 से विभाजित करता है। चरणों की संख्या वह संख्या है जितनी बार आप मूल सरणी को दो भागों में विभाजित कर सकते हैं। यह लघुगणक (आधार 2) की सटीक परिभाषा है।

छँटाई चरण

सॉर्टिंग चरण में, आप एकात्मक (एकल-तत्व) सरणियों से शुरू करते हैं। प्रत्येक चरण के दौरान आप एकाधिक मर्ज ऑपरेशन लागू करते हैं और कुल लागत N = 8 ऑपरेशन है:

• पहले चरण में आपके पास 4 मर्ज हैं जिनमें से प्रत्येक में 2 ऑपरेशन की लागत आती है
• दूसरे चरण में आपके पास 2 मर्ज हैं जिनमें से प्रत्येक में 4 ऑपरेशन की लागत है
• तीसरे चरण में आपके पास 1 मर्ज है जिसकी लागत 8 ऑपरेशन हैं

चूँकि लॉग(एन) चरण हैं, कुल लागत एन * लॉग (एन) संचालन.

मर्ज सॉर्ट के लाभ

यह एल्गोरिदम इतना शक्तिशाली क्यों है?

क्योंकि:

• आप मेमोरी फ़ुटप्रिंट को कम करने के लिए इसे बदल सकते हैं ताकि आप नए ऐरे न बनाएं बल्कि सीधे इनपुट ऐरे को संशोधित करें।

नोट: इस प्रकार के एल्गोरिदम को कहा जाता है in-जगह (अतिरिक्त मेमोरी के बिना सॉर्ट करना)।

• आप महत्वपूर्ण डिस्क I/O ओवरहेड खर्च किए बिना एक ही समय में डिस्क स्थान और थोड़ी मात्रा में मेमोरी का उपयोग करने के लिए इसे बदल सकते हैं। विचार केवल उन हिस्सों को मेमोरी में लोड करने का है जो वर्तमान में संसाधित हो रहे हैं। यह तब महत्वपूर्ण है जब आपको केवल 100-मेगाबाइट मेमोरी बफ़र वाली मल्टी-गीगाबाइट तालिका को सॉर्ट करने की आवश्यकता होती है।

नोट: इस प्रकार के एल्गोरिदम को कहा जाता है बाहरी प्रकार.

• आप इसे कई प्रक्रियाओं/थ्रेड्स/सर्वर पर चलाने के लिए बदल सकते हैं।

उदाहरण के लिए, वितरित मर्ज सॉर्ट प्रमुख घटकों में से एक है Hadoop (जो बड़े डेटा में एक संरचना है)।

• यह एल्गोरिदम सीसे को सोने में बदल सकता है (वास्तव में!)।

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

ऐरे, ट्री और हैश टेबल

अब जब हम समय की जटिलता और छँटाई के विचार को समझ गए हैं, तो मुझे आपको 3 डेटा संरचनाओं के बारे में बताना चाहिए। यह महत्वपूर्ण है क्योंकि वे आधुनिक डेटाबेस का आधार हैं. मैं इस अवधारणा का भी परिचय दूंगा डेटाबेस सूचकांक.

सरणी

द्वि-आयामी सरणी सबसे सरल डेटा संरचना है। एक तालिका को एक सारणी के रूप में सोचा जा सकता है। उदाहरण के लिए:

यह 2-आयामी सरणी पंक्तियों और स्तंभों वाली एक तालिका है:

• प्रत्येक पंक्ति एक इकाई का प्रतिनिधित्व करती है
• कॉलम उन गुणों को संग्रहीत करते हैं जो इकाई का वर्णन करते हैं।
• प्रत्येक कॉलम एक विशिष्ट प्रकार (पूर्णांक, स्ट्रिंग, दिनांक...) का डेटा संग्रहीत करता है।

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

उदाहरण के लिए, यदि आप यूके में काम करने वाले सभी लोगों को ढूंढना चाहते हैं, तो आपको यह निर्धारित करने के लिए प्रत्येक पंक्ति को देखना होगा कि वह पंक्ति यूके से संबंधित है या नहीं। इसमें आपको एन लेनदेन का खर्च आएगाजहां N - पंक्तियों की संख्या, जो ख़राब नहीं है, लेकिन क्या इससे तेज़ तरीका हो सकता है? अब समय आ गया है कि हम पेड़ों से परिचित हों।

ध्यान दें: अधिकांश आधुनिक डेटाबेस तालिकाओं को कुशलतापूर्वक संग्रहीत करने के लिए विस्तारित सरणी प्रदान करते हैं: ढेर-संगठित टेबल और इंडेक्स-संगठित टेबल। लेकिन इससे स्तंभों के समूह में किसी विशिष्ट स्थिति को तुरंत ढूंढने की समस्या नहीं बदलती है।

डेटाबेस ट्री और इंडेक्स

एक बाइनरी सर्च ट्री एक विशेष गुण वाला बाइनरी ट्री है, प्रत्येक नोड पर कुंजी होनी चाहिए:

• बाएँ उपवृक्ष में संग्रहीत सभी कुंजियों से अधिक
• दाएँ उपवृक्ष में संग्रहीत सभी कुंजियों से कम

आइए देखें कि इसका दृश्यात्मक अर्थ क्या है

विचार

इस पेड़ में N = 15 तत्व हैं। मान लीजिए कि मैं 208 की तलाश में हूं:

• मैं मूल से शुरू करता हूं जिसकी कुंजी 136 है। 136<208 के बाद से, मैं नोड 136 के दाहिने उपवृक्ष को देखता हूं।
• 398>208 इसलिए मैं नोड 398 के बाएँ उपवृक्ष को देख रहा हूँ
• 250>208 इसलिए मैं नोड 250 के बाएँ उपवृक्ष को देख रहा हूँ
• 200<208, इसलिए मैं नोड 200 का दायां उपवृक्ष देख रहा हूं। लेकिन 200 का कोई दायां उपवृक्ष नहीं है, मूल्य मौजूद नहीं है (क्योंकि यदि यह मौजूद है, तो यह सही सबट्री 200 में होगा)।

अब मान लीजिए कि मैं 40 की तलाश में हूं

• मैं मूल से शुरू करता हूं जिसकी कुंजी 136 है। 136 > 40 के बाद से, मैं नोड 136 के बाएं उपवृक्ष को देखता हूं।
• 80 > 40, इसलिए मैं नोड 80 के बाएँ उपवृक्ष को देख रहा हूँ
• 40=40, नोड मौजूद है. मैं नोड के अंदर पंक्ति आईडी पुनर्प्राप्त करता हूं (चित्र में नहीं दिखाया गया है) और दी गई पंक्ति आईडी के लिए तालिका में देखता हूं।
• पंक्ति आईडी जानने से मुझे ठीक-ठीक पता चल जाता है कि तालिका में डेटा कहाँ है, इसलिए मैं इसे तुरंत पुनः प्राप्त कर सकता हूँ।

अंत में, दोनों खोजों से मुझे पेड़ के अंदर के स्तरों की संख्या चुकानी पड़ेगी। यदि आप मर्ज सॉर्ट के बारे में भाग को ध्यान से पढ़ते हैं, तो आपको देखना चाहिए कि लॉग (एन) स्तर हैं। यह पता चला है, खोज लागत लॉग(एन), इतना खराब भी नहीं!

चलिए अपनी समस्या पर वापस आते हैं

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

• अगर आप जानना चाहते हैं कि यूके में कौन काम करता है
• आप उस नोड को पाने के लिए पेड़ को देखें जो ग्रेट ब्रिटेन का प्रतिनिधित्व करता है
• "यूकेनोड" के अंदर आपको यूके कार्यकर्ता रिकॉर्ड का स्थान मिलेगा।

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

आप फ़ील्ड के किसी भी समूह (स्ट्रिंग, संख्या, 2 लाइनें, संख्या और स्ट्रिंग, दिनांक...) के लिए एक इंडेक्स ट्री बना सकते हैं, जब तक आपके पास कुंजियों (यानी फ़ील्ड समूह) की तुलना करने के लिए एक फ़ंक्शन है ताकि आप सेट कर सकें चाबियों के बीच ऑर्डर करें (जो डेटाबेस में किसी भी बुनियादी प्रकार के लिए मामला है)।

बी+ट्रीइंडेक्स

हालाँकि यह पेड़ एक विशिष्ट मूल्य प्राप्त करने के लिए अच्छा काम करता है, लेकिन जरूरत पड़ने पर एक बड़ी समस्या होती है दो मानों के बीच एकाधिक तत्व प्राप्त करें. इसकी लागत O(N) होगी क्योंकि आपको पेड़ में प्रत्येक नोड को देखना होगा और जांचना होगा कि क्या यह इन दो मानों के बीच है (उदाहरण के लिए पेड़ के क्रमबद्ध ट्रैवर्सल के साथ)। इसके अलावा, यह ऑपरेशन डिस्क I/O अनुकूल नहीं है क्योंकि आपको पूरा पेड़ पढ़ना होगा। हमें कुशलतापूर्वक क्रियान्वयन का एक तरीका खोजने की जरूरत है रेंज अनुरोध. इस समस्या को हल करने के लिए, आधुनिक डेटाबेस पिछले ट्री के संशोधित संस्करण का उपयोग करते हैं जिसे B+Tree कहा जाता है। बी+ट्री पेड़ में:

• केवल निम्नतम नोड्स (पत्ते) दुकान की जानकारी (संबंधित तालिका में पंक्तियों का स्थान)
• शेष नोड यहां हैं रूटिंग के लिए सही नोड के लिए खोज के दौरान.

जैसा कि आप देख सकते हैं, यहां अधिक नोड हैं (दो बार)। दरअसल, आपके पास अतिरिक्त नोड्स, "निर्णय नोड्स" हैं, जो आपको सही नोड ढूंढने में मदद करेंगे (जो संबंधित तालिका में पंक्तियों के स्थान को संग्रहीत करता है)। लेकिन खोज जटिलता अभी भी O(log(N)) है (केवल एक और स्तर है)। बड़ा अंतर यह है निचले स्तर पर नोड अपने उत्तराधिकारियों से जुड़े होते हैं.

इस बी+ट्री के साथ, यदि आप 40 और 100 के बीच मान ढूंढ रहे हैं:

• आपको बस 40 (या यदि 40 मौजूद नहीं है तो 40 के बाद निकटतम मान) देखना होगा, जैसा आपने पिछले पेड़ के साथ किया था।
• फिर सीधे वारिस लिंक का उपयोग करके 40 वारिस इकट्ठा करें जब तक कि आप 100 तक न पहुंच जाएं।

मान लीजिए कि आपको एम उत्तराधिकारी मिलते हैं और पेड़ में एन नोड हैं। एक विशिष्ट नोड ढूँढने में पिछले पेड़ की तरह लॉग (एन) खर्च होता है। लेकिन एक बार जब आप यह नोड प्राप्त कर लेते हैं, तो आपको एम संचालन में एम उत्तराधिकारी उनके उत्तराधिकारियों के संदर्भ में मिलेंगे। इस खोज की लागत केवल M+log(N) है पिछले पेड़ पर एन संचालन की तुलना में संचालन। इसके अलावा, आपको पूरा ट्री (केवल एम+लॉग(एन) नोड्स) पढ़ने की ज़रूरत नहीं है, जिसका अर्थ है कम डिस्क उपयोग। यदि M छोटा है (जैसे 200 पंक्तियाँ) और N बड़ा है (1 पंक्तियाँ), तो एक बड़ा अंतर होगा।

लेकिन यहां (फिर से!) नई समस्याएं हैं। यदि आप डेटाबेस में (और इसलिए संबंधित बी+ट्री इंडेक्स में) कोई पंक्ति जोड़ते या हटाते हैं:

• आपको B+Tree के अंदर नोड्स के बीच क्रम बनाए रखना होगा, अन्यथा आप बिना छांटे गए पेड़ के अंदर नोड्स नहीं ढूंढ पाएंगे।
• आपको B+Tree में स्तरों की न्यूनतम संभव संख्या रखनी होगी, अन्यथा O(log(N)) समय जटिलता O(N) बन जाती है।

दूसरे शब्दों में, बी+ट्री को स्व-व्यवस्थित और संतुलित होना चाहिए। सौभाग्य से, यह स्मार्ट डिलीट और इंसर्ट ऑपरेशन के साथ संभव है। लेकिन इसकी एक कीमत होती है: B+ ट्री में सम्मिलन और विलोपन की लागत O(log(N)) होती है। इसीलिए आपमें से कुछ लोगों ने ऐसा सुना है बहुत अधिक अनुक्रमणिका का उपयोग करना एक अच्छा विचार नहीं है. वास्तव में, आप किसी तालिका में किसी पंक्ति को तेजी से डालने/अपडेट करने/हटाने की गति को धीमा कर रहे हैंक्योंकि डेटाबेस को प्रत्येक इंडेक्स के लिए महंगे O(log(N)) ऑपरेशन का उपयोग करके तालिका के इंडेक्स को अपडेट करने की आवश्यकता होती है। इसके अलावा, इंडेक्स जोड़ने का मतलब है अधिक कार्यभार लेन-देन प्रबंधक (लेख के अंत में वर्णित किया जाएगा)।

अधिक जानकारी के लिए आप विकिपीडिया लेख देख सकते हैं B+पेड़. यदि आप किसी डेटाबेस में B+Tree लागू करने का उदाहरण चाहते हैं, तो एक नज़र डालें यह लेख и यह लेख एक अग्रणी MySQL डेवलपर से। वे दोनों इस बात पर ध्यान केंद्रित करते हैं कि InnoDB (MySQL इंजन) इंडेक्स को कैसे संभालता है।

नोट: एक पाठक ने मुझे बताया कि, निम्न-स्तरीय अनुकूलन के कारण, B+ वृक्ष को पूरी तरह से संतुलित किया जाना चाहिए।

हैश तालिका

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

हैश तालिका एक डेटा संरचना है जो अपनी कुंजी द्वारा किसी तत्व को तुरंत ढूंढती है। हैश तालिका बनाने के लिए आपको परिभाषित करने की आवश्यकता है:

• कुंजी आपके तत्वों के लिए
• हैश फंकशन चाबियों के लिए. परिकलित कुंजी हैश तत्वों का स्थान देते हैं (जिन्हें कहा जाता है)। खंडों ).
• कुंजियों की तुलना करने का कार्य. एक बार जब आपको सही सेगमेंट मिल जाए, तो आपको इस तुलना का उपयोग करके सेगमेंट के भीतर वह तत्व ढूंढना होगा जिसे आप ढूंढ रहे हैं।

सरल उदाहरण है

आइए एक स्पष्ट उदाहरण लें:

इस हैश तालिका में 10 खंड हैं. क्योंकि मैं आलसी हूं, मैंने केवल 5 खंडों का चित्रण किया है, लेकिन मुझे पता है कि आप चतुर हैं, इसलिए मैं आपको अन्य 5 खंडों का चित्र स्वयं बनाने दूंगा। मैंने कुंजी के हैश फ़ंक्शन मॉड्यूलो 10 का उपयोग किया। दूसरे शब्दों में, मैं तत्व का खंड ढूंढने के लिए उसकी कुंजी का केवल अंतिम अंक संग्रहीत करता हूं:

• यदि अंतिम अंक 0 है, तो तत्व खंड 0 में आता है,
• यदि अंतिम अंक 1 है, तो तत्व खंड 1 में आता है,
• यदि अंतिम अंक 2 है, तो तत्व क्षेत्र 2 में आता है,
• ...

मैंने जिस तुलना फ़ंक्शन का उपयोग किया वह केवल दो पूर्णांकों के बीच समानता है।

मान लीजिए कि आप तत्व 78 प्राप्त करना चाहते हैं:

• हैश तालिका 78 के लिए हैश कोड की गणना करती है, जो 8 है।
• हैश तालिका खंड 8 को देखती है, और इसे मिलने वाला पहला तत्व 78 है।
• वह आपको आइटम 78 लौटाती है
• खोज में केवल 2 ऑपरेशन खर्च होते हैं (एक हैश मान की गणना करने के लिए और दूसरा खंड के भीतर तत्व को देखने के लिए)।

अब मान लीजिए कि आप तत्व 59 प्राप्त करना चाहते हैं:

• हैश तालिका 59 के लिए हैश कोड की गणना करती है, जो 9 है।
• हैश तालिका खंड 9 में खोजती है, पाया गया पहला तत्व 99 है। 99!=59 के बाद से, तत्व 99 एक वैध तत्व नहीं है।
• उसी तर्क का उपयोग करते हुए, दूसरा तत्व (9), तीसरा (79), ..., अंतिम (29) लिया जाता है।
• तत्व नहीं मिला.
• खोज में 7 ऑपरेशन खर्च हुए.

अच्छा हैश फ़ंक्शन

जैसा कि आप देख सकते हैं, आप जिस मूल्य की तलाश कर रहे हैं उसके आधार पर, लागत समान नहीं है!

यदि मैं अब कुंजी के हैश फ़ंक्शन मॉड्यूलो 1 को बदलता हूं (अर्थात, अंतिम 000 अंक लेता हूं), तो दूसरे लुकअप में केवल 000 ऑपरेशन की लागत आती है क्योंकि खंड 6 में कोई तत्व नहीं हैं। असली चुनौती एक अच्छा हैश फ़ंक्शन ढूंढना है जो बहुत कम संख्या में तत्वों वाली बकेट बनाएगा.

मेरे उदाहरण में, एक अच्छा हैश फ़ंक्शन ढूंढना आसान है। लेकिन यह एक सरल उदाहरण है, एक अच्छा हैश फ़ंक्शन ढूंढना अधिक कठिन होता है जब कुंजी है:

• स्ट्रिंग (उदाहरण के लिए - अंतिम नाम)
• 2 पंक्तियाँ (उदाहरण के लिए - अंतिम नाम और पहला नाम)
• 2 पंक्तियाँ और दिनांक (उदाहरण के लिए - अंतिम नाम, प्रथम नाम और जन्म तिथि)
• ...

अच्छे हैश फ़ंक्शन के साथ, हैश तालिका लुकअप की लागत O(1) है.

ऐरे बनाम हैश टेबल

किसी सरणी का उपयोग क्यों न करें?

हम्म, अच्छा सवाल है.

• हैश तालिका हो सकती है स्मृति में आंशिक रूप से लोड किया गया, और शेष खंड डिस्क पर बने रह सकते हैं।
• किसी सारणी के साथ आपको स्मृति में सन्निहित स्थान का उपयोग करना होगा। यदि आप एक बड़ी तालिका लोड कर रहे हैं पर्याप्त सतत स्थान ढूँढना बहुत कठिन है.
• हैश तालिका के लिए, आप अपनी इच्छित कुंजी का चयन कर सकते हैं (उदाहरण के लिए, देश और व्यक्ति का अंतिम नाम)।

अधिक जानकारी के लिए आप इसके बारे में आर्टिकल पढ़ सकते हैं जावाहैश मैप, जो हैश तालिका का एक कुशल कार्यान्वयन है; इस आलेख में शामिल अवधारणाओं को समझने के लिए आपको जावा को समझने की आवश्यकता नहीं है।

स्रोत: www.habr.com