अहो हाब्र! लेखाचा अनुवाद मी तुमच्या लक्षात आणून देत आहे
"रिलेशनल डेटाबेस कसा कार्य करतो".

जेव्हा रिलेशनल डेटाबेसचा विचार केला जातो तेव्हा मी मदत करू शकत नाही परंतु काहीतरी गहाळ आहे असे वाटते. ते सर्वत्र वापरले जातात. लहान आणि उपयुक्त SQLite पासून शक्तिशाली Teradata पर्यंत अनेक भिन्न डेटाबेस उपलब्ध आहेत. परंतु डेटाबेस कसे कार्य करते हे स्पष्ट करणारे काही लेख आहेत. किती कमी परिणाम आहेत हे पाहण्यासाठी तुम्ही "howdoesarelationaldatabasework" वापरून स्वतःचा शोध घेऊ शकता. शिवाय हे लेख छोटे आहेत. जर तुम्ही नवीनतम गुळगुळीत तंत्रज्ञान (बिगडेटा, NoSQL किंवा JavaScript) शोधत असाल, तर तुम्हाला ते कसे कार्य करतात हे स्पष्ट करणारे अधिक सखोल लेख सापडतील.

रिलेशनल डेटाबेस खूप जुने आणि खूप कंटाळवाणे आहेत का विद्यापीठ अभ्यासक्रम, शोधनिबंध आणि पुस्तकांच्या बाहेर स्पष्ट केले जाऊ शकते?

एक विकसक म्हणून, मला समजत नाही असे काहीतरी वापरणे मला आवडत नाही. आणि जर डेटाबेस 40 वर्षांहून अधिक काळ वापरला गेला असेल तर, एक कारण असणे आवश्यक आहे. गेल्या काही वर्षांत, मी दररोज वापरत असलेले हे विचित्र ब्लॅक बॉक्स खरोखर समजून घेण्यासाठी मी शेकडो तास घालवले आहेत. रिलेशनल डेटाबेस खूप मनोरंजक कारण ते उपयुक्त आणि पुन्हा वापरता येण्याजोग्या संकल्पनांवर आधारित. जर तुम्हाला डेटाबेस समजून घेण्यात स्वारस्य असेल, परंतु या विस्तृत विषयावर विचार करण्याची वेळ किंवा प्रवृत्ती कधीच नसेल, तर तुम्ही या लेखाचा आनंद घ्यावा.

या लेखाचे शीर्षक स्पष्ट असले तरी, या लेखाचा उद्देश डेटाबेस कसा वापरायचा हे समजून घेणे नाही. त्यामुळे, एक साधी कनेक्शन विनंती आणि मूलभूत प्रश्न कसे लिहायचे हे तुम्हाला आधीच माहित असले पाहिजे RAW; अन्यथा तुम्हाला हा लेख समजणार नाही. तुम्हाला फक्त हीच गोष्ट माहित असणे आवश्यक आहे, मी बाकीचे स्पष्टीकरण देईन.

मी काही संगणक विज्ञान मूलभूत गोष्टींसह प्रारंभ करेन, जसे की अल्गोरिदमची वेळ जटिलता (BigO). मला माहित आहे की तुमच्यापैकी काहींना या संकल्पनेचा तिरस्कार आहे, परंतु त्याशिवाय तुम्ही डेटाबेसमधील गुंतागुंत समजून घेऊ शकणार नाही. हा एक मोठा विषय असल्याने, मी लक्ष केंद्रित करेन मला काय वाटते ते महत्वाचे आहे: डेटाबेस प्रक्रिया कशी होते एस क्यू एल चौकशी. मी फक्त परिचय करून देतो मूलभूत डेटाबेस संकल्पनाजेणेकरून लेखाच्या शेवटी तुम्हाला हुडखाली काय चालले आहे याची कल्पना येईल.

हा एक लांबलचक आणि तांत्रिक लेख आहे ज्यामध्ये बरेच अल्गोरिदम आणि डेटा स्ट्रक्चर्स समाविष्ट आहेत, ते वाचण्यासाठी तुमचा वेळ घ्या. काही संकल्पना समजणे कठीण असू शकते; तुम्ही त्यांना वगळू शकता आणि तरीही सामान्य कल्पना मिळवू शकता.

तुमच्यातील अधिक जाणकारांसाठी, हा लेख 3 भागांमध्ये विभागलेला आहे:

• निम्न-स्तरीय आणि उच्च-स्तरीय डेटाबेस घटकांचे विहंगावलोकन
• क्वेरी ऑप्टिमायझेशन प्रक्रियेचे विहंगावलोकन
• व्यवहार आणि बफर पूल व्यवस्थापनाचा आढावा

मूलभूत गोष्टींकडे परत

वर्षापूर्वी (आकाशगंगेत, खूप दूर...), विकासकांना ते कोडिंग करत असलेल्या ऑपरेशन्सची संख्या अचूकपणे माहित असणे आवश्यक होते. त्यांना त्यांचे अल्गोरिदम आणि डेटा स्ट्रक्चर्स मनापासून माहित होते कारण त्यांना त्यांच्या स्लो कॉम्प्युटरचा CPU आणि मेमरी वाया घालवणे परवडणारे नव्हते.

या भागात, मी तुम्हाला यापैकी काही संकल्पनांची आठवण करून देईन कारण डेटाबेस समजून घेण्यासाठी त्या आवश्यक आहेत. मी ही संकल्पना मांडणार आहे डेटाबेस निर्देशांक.

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 ms गमावाल, फक्त तुमचे डोळे मिचकावण्याची वेळ आहे. खरंच, आधुनिक प्रोसेसर प्रक्रिया करू शकतात प्रति सेकंद शेकडो लाखो ऑपरेशन्स. म्हणूनच अनेक आयटी प्रकल्पांमध्ये कार्यप्रदर्शन आणि ऑप्टिमायझेशन ही समस्या नाही.

मी म्हटल्याप्रमाणे, प्रचंड प्रमाणात डेटासह काम करताना ही संकल्पना जाणून घेणे महत्त्वाचे आहे. या वेळी अल्गोरिदमला 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: हे भयंकर आहे! नमूद केलेल्या काही अल्गोरिदममध्ये ही जटिलता आहे.
• 3n: हे आणखी वाईट आहे! या लेखाच्या मध्यभागी आपण पाहणार असलेल्या अल्गोरिदमपैकी एक ही जटिलता आहे (आणि ते प्रत्यक्षात अनेक डेटाबेसमध्ये वापरले जाते).
• फॅक्टोरियल n: अगदी थोड्या प्रमाणात डेटा असतानाही तुम्हाला तुमचे परिणाम कधीही मिळणार नाहीत.
• nn: जर तुम्हाला ही जटिलता आली, तर तुम्ही स्वतःला विचारले पाहिजे की हे खरोखर तुमचे क्रियाकलाप आहे का...

टीप: मी तुम्हाला मोठ्या O पदनामाची वास्तविक व्याख्या दिलेली नाही, फक्त एक कल्पना आहे. तुम्ही हा लेख येथे वाचू शकता विकिपीडिया वास्तविक (असिम्प्टोटिक) व्याख्येसाठी.

विलीन करा

जेव्हा आपल्याला संग्रह क्रमवारी लावण्याची आवश्यकता असते तेव्हा आपण काय करता? काय? तुम्ही sort() फंक्शनला कॉल करा... ठीक आहे, चांगले उत्तर... पण डेटाबेससाठी, तुम्हाला हे sort() फंक्शन कसे कार्य करते हे समजले पाहिजे.

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

विलीन

अनेक उपयुक्त अल्गोरिदम प्रमाणे, मर्ज सॉर्ट एका युक्तीवर अवलंबून आहे: N/2 आकाराच्या 2 क्रमवारी लावलेल्या अॅरेला N-घटक क्रमवारी केलेल्या अॅरेमध्ये एकत्रित केल्याने फक्त N ऑपरेशन्स खर्च होतात. या ऑपरेशनला विलीनीकरण म्हणतात.

याचा अर्थ काय ते एका साध्या उदाहरणाने पाहू या:

ही आकृती दर्शवते की अंतिम क्रमवारीत 8-घटक अॅरे तयार करण्यासाठी, तुम्हाला 2 4-घटक अॅरेवर एकदाच पुनरावृत्ती करावी लागेल. दोन्ही 4-घटक अॅरे आधीच क्रमवारी लावलेले असल्याने:

• १) तुम्ही दोन अ‍ॅरेमधील दोन्ही वर्तमान घटकांची तुलना करता (सुरुवातीला वर्तमान = प्रथम)
• 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 चरणांमध्ये युनिटरी अॅरेमध्ये विभागली जाते. पायऱ्यांची औपचारिक संख्या लॉग(N) आहे (N=8 पासून, log(N) = 3).

हे मला कसे कळेल?

मी हुशार आहे! एका शब्दात - गणित. कल्पना अशी आहे की प्रत्येक पायरी मूळ अॅरेच्या आकाराला 2 ने विभाजित करते. पायऱ्यांची संख्या म्हणजे तुम्ही मूळ अॅरेला दोन भागांमध्ये किती वेळा विभाजित करू शकता. ही लॉगरिथमची अचूक व्याख्या आहे (बेस 2).

क्रमवारीचा टप्पा

क्रमवारीच्या टप्प्यात, तुम्ही एकात्मक (एकल-घटक) अॅरेसह प्रारंभ कराल. प्रत्येक चरणादरम्यान तुम्ही एकाधिक मर्ज ऑपरेशन्स लागू करता आणि एकूण किंमत N = 8 ऑपरेशन्स आहे:

• पहिल्या टप्प्यात तुमच्याकडे 4 विलीनीकरणे आहेत ज्यांची किंमत प्रत्येकी 2 ऑपरेशन्स आहे
• दुसर्‍या चरणात तुमच्याकडे 2 विलीनीकरणे आहेत ज्यांची किंमत प्रत्येकी 4 ऑपरेशन्स आहे
• तिसऱ्या चरणात तुमच्याकडे 1 मर्ज आहे ज्याची किंमत 8 ऑपरेशन्स आहे

लॉग(एन) पायऱ्या असल्याने, एकूण खर्च एन * log(N) ऑपरेशन्स.

मर्ज क्रमवारीचे फायदे

हे अल्गोरिदम इतके शक्तिशाली का आहे?

कारण:

• तुम्ही मेमरी फूटप्रिंट कमी करण्यासाठी ते बदलू शकता जेणेकरून तुम्ही नवीन अॅरे तयार करू शकत नाही परंतु थेट इनपुट अॅरेमध्ये बदल करू शकता.

टीप: या प्रकारच्या अल्गोरिदमला म्हणतात in-स्थान (अतिरिक्त मेमरीशिवाय क्रमवारी लावणे).

• तुम्ही डिस्क स्पेस आणि थोड्या प्रमाणात मेमरी वापरण्यासाठी त्याच वेळी लक्षणीय डिस्क I/O ओव्हरहेड न घेता बदलू शकता. मेमरीमध्ये फक्त तेच भाग लोड करण्याचा विचार आहे ज्यावर सध्या प्रक्रिया केली जात आहे. जेव्हा तुम्हाला केवळ 100-मेगाबाइट मेमरी बफरसह मल्टी-गीगाबाइट टेबलची क्रमवारी लावायची असते तेव्हा हे महत्त्वाचे असते.

टीप: या प्रकारच्या अल्गोरिदमला म्हणतात बाह्य क्रमवारी.

• तुम्ही ते एकाधिक प्रक्रिया/थ्रेड्स/सर्व्हरवर चालवण्यासाठी बदलू शकता.

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

• हा अल्गोरिदम शिसे सोन्यात बदलू शकतो (खरोखर!).

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

अॅरे, ट्री आणि हॅश टेबल

आता आम्हाला वेळेची जटिलता आणि वर्गीकरणाची कल्पना समजली आहे, मी तुम्हाला 3 डेटा स्ट्रक्चर्सबद्दल सांगू. हे महत्वाचे आहे कारण ते आधुनिक डेटाबेसचा आधार आहेत. मी ही संकल्पना मांडणार आहे डेटाबेस निर्देशांक.

रचना

द्विमितीय अॅरे ही सर्वात सोपी डेटा रचना आहे. सारणीचा अॅरे म्हणून विचार केला जाऊ शकतो. उदाहरणार्थ:

हा द्विमितीय अॅरे पंक्ती आणि स्तंभांसह एक सारणी आहे:

• प्रत्येक ओळ एक अस्तित्व दर्शवते
• स्तंभ गुणधर्म संग्रहित करतात जे घटकाचे वर्णन करतात.
• प्रत्येक स्तंभ विशिष्ट प्रकाराचा डेटा संग्रहित करतो (पूर्णांक, स्ट्रिंग, तारीख...).

डेटा संचयित करण्यासाठी आणि दृश्यमान करण्यासाठी हे सोयीस्कर आहे, तथापि, जेव्हा आपल्याला विशिष्ट मूल्य शोधण्याची आवश्यकता असते तेव्हा हे योग्य नाही.

उदाहरणार्थ, जर तुम्हाला यूकेमध्ये काम करणारी सर्व मुले शोधायची असतील, तर ती पंक्ती यूकेची आहे की नाही हे निर्धारित करण्यासाठी तुम्हाला प्रत्येक पंक्ती पाहणे आवश्यक आहे. यामुळे तुम्हाला एन व्यवहार खर्च होतीलकुठे 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, नोड अस्तित्वात आहे. मी नोडमधील रो आयडी पुनर्प्राप्त करतो (चित्रात दर्शविला नाही) आणि दिलेल्या पंक्ती आयडीसाठी टेबलमध्ये पाहतो.
• पंक्ती आयडी जाणून घेतल्याने मला टेबलमध्ये डेटा नेमका कुठे आहे हे कळू शकते, त्यामुळे मी तो त्वरित पुनर्प्राप्त करू शकतो.

सरतेशेवटी, दोन्ही शोधांमुळे मला झाडाच्या आतील स्तरांची संख्या मोजावी लागेल. जर तुम्ही विलीनीकरणाच्या क्रमवारीबद्दलचा भाग काळजीपूर्वक वाचलात, तर तुम्हाला लॉग(N) स्तर असल्याचे दिसले पाहिजे. हे बाहेर वळते, शोध खर्च लॉग(N), वाईट नाही!

चला आपल्या समस्येकडे परत जाऊया

परंतु हे खूप अमूर्त आहे, म्हणून आपल्या समस्येकडे परत जाऊया. साध्या पूर्णांकाऐवजी, मागील सारणीतील एखाद्याच्या देशाचे प्रतिनिधित्व करणाऱ्या स्ट्रिंगची कल्पना करा. समजा तुमच्याकडे एक झाड आहे ज्यामध्ये टेबलचे "देश" फील्ड (स्तंभ 3) आहे:

• यूकेमध्ये कोण काम करते हे जाणून घ्यायचे असल्यास
• ग्रेट ब्रिटनचे प्रतिनिधित्व करणारा नोड मिळविण्यासाठी तुम्ही झाडाकडे पहा
• "UKnode" मध्ये तुम्हाला UK कामगारांच्या नोंदींचे स्थान सापडेल.

तुम्ही थेट अॅरे वापरल्यास या शोधासाठी N ऑपरेशन्सऐवजी लॉग(N) ऑपरेशन्स खर्च होतील. जे तुम्ही आत्ताच मांडले होते डेटाबेस निर्देशांक.

तुम्ही फील्डच्या कोणत्याही गटासाठी (स्ट्रिंग, संख्या, 2 ओळी, संख्या आणि स्ट्रिंग, तारीख...) एक इंडेक्स ट्री तयार करू शकता जोपर्यंत तुमच्याकडे की (म्हणजे फील्ड गट) ची तुलना करण्याचे कार्य आहे जेणेकरून तुम्ही सेट करू शकता. किल्लींमध्ये ऑर्डर करा (जे डेटाबेसमधील कोणत्याही मूलभूत प्रकारांसाठी आहे).

B+TreeIndex

हे झाड विशिष्ट मूल्य मिळविण्यासाठी चांगले कार्य करते, परंतु जेव्हा आपल्याला आवश्यक असते तेव्हा एक मोठी समस्या असते दोन मूल्यांमध्ये अनेक घटक मिळवा. यासाठी O(N) खर्च येईल कारण तुम्हाला झाडातील प्रत्येक नोड पहावे लागेल आणि ते या दोन मूल्यांमधील आहे का ते तपासावे लागेल (उदा. झाडाच्या ऑर्डर केलेल्या ट्रॅव्हर्सलसह). शिवाय, हे ऑपरेशन डिस्क I/O अनुकूल नाही कारण तुम्हाला संपूर्ण झाड वाचावे लागेल. आम्हाला कार्यक्षमतेने कार्यान्वित करण्याचा मार्ग शोधण्याची आवश्यकता आहे श्रेणी विनंती. या समस्येचे निराकरण करण्यासाठी, आधुनिक डेटाबेस B+Tree नावाच्या मागील झाडाची सुधारित आवृत्ती वापरतात. बी + ट्री झाडामध्ये:

• फक्त सर्वात कमी नोड्स (पाने) माहिती साठवा (संबंधित सारणीतील पंक्तींचे स्थान)
• उर्वरित नोड्स येथे आहेत राउटिंग साठी योग्य नोडवर शोध दरम्यान.

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

या B+Tree सह, जर तुम्ही 40 आणि 100 मधील मूल्ये शोधत असाल तर:

• तुम्हाला फक्त 40 (किंवा 40 अस्तित्वात नसल्यास 40 नंतरचे सर्वात जवळचे मूल्य) शोधणे आवश्यक आहे जसे तुम्ही मागील झाडासह केले होते.
• नंतर तुम्ही 40 पर्यंत पोहोचेपर्यंत थेट वारस लिंक वापरून 100 वारस गोळा करा.

समजा तुम्हाला M उत्तराधिकारी सापडले आहेत आणि झाडाला N नोड आहेत. विशिष्ट नोड शोधण्यासाठी मागील झाडाप्रमाणे लॉग(एन) खर्च येतो. परंतु एकदा तुम्हाला हा नोड मिळाला की, तुम्हाला M ऑपरेशन्समध्ये त्यांच्या उत्तराधिकार्‍यांच्या संदर्भासह M उत्तराधिकारी मिळतील. या शोधासाठी फक्त M+log(N) खर्च येतो मागील झाडावरील N ऑपरेशनच्या तुलनेत ऑपरेशन्स. शिवाय, तुम्हाला पूर्ण ट्री (केवळ M+log(N) नोड्स) वाचण्याची गरज नाही, म्हणजे डिस्कचा कमी वापर. जर M लहान असेल (उदा. 200 पंक्ती) आणि N मोठा असेल (1 पंक्ती), तर मोठा फरक असेल.

पण इथे नवीन समस्या आहेत (पुन्हा!). तुम्ही डेटाबेसमध्ये एक पंक्ती जोडल्यास किंवा हटवल्यास (आणि म्हणून संबंधित B+Tree इंडेक्समध्ये):

• तुम्ही 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 स्वतःच चित्रित करू देईन. मी कीचे हॅश फंक्शन मोड्युलो १० वापरले. दुसऱ्या शब्दांत, मी घटकाचा विभाग शोधण्यासाठी फक्त शेवटचा अंक संग्रहित करतो:

• जर शेवटचा अंक 0 असेल, तर घटक विभाग 0 मध्ये येतो,
• जर शेवटचा अंक 1 असेल, तर घटक विभाग 1 मध्ये येतो,
• शेवटचा अंक 2 असल्यास, घटक क्षेत्र 2 मध्ये येतो,
• ...

मी वापरलेले तुलना कार्य फक्त दोन पूर्णांकांमधील समानता आहे.

समजा तुम्हाला घटक 78 मिळवायचा आहे:

• हॅश टेबल 78 साठी हॅश कोडची गणना करते, जे 8 आहे.
• हॅश टेबल सेगमेंट 8 कडे पाहतो आणि त्याला सापडलेला पहिला घटक 78 आहे.
• ती तुम्हाला आयटम 78 परत करते
• शोध खर्च फक्त 2 ऑपरेशन्स (एक हॅश व्हॅल्यू मोजण्यासाठी आणि दुसरा सेगमेंटमधील घटक शोधण्यासाठी).

आता समजा तुम्हाला घटक ५९ मिळवायचा आहे:

• हॅश टेबल 59 साठी हॅश कोडची गणना करते, जे 9 आहे.
• हॅश टेबल सेगमेंट 9 मध्ये शोधते, पहिला घटक 99 आढळला. 99!=59 पासून, घटक 99 हा वैध घटक नाही.
• समान तर्क वापरून, दुसरा घटक (9), तिसरा (79), ..., शेवटचा (29) घेतला जातो.
• घटक सापडला नाही.
• शोधासाठी 7 ऑपरेशन खर्च झाले.

चांगले हॅश फंक्शन

जसे आपण पाहू शकता, आपण शोधत असलेल्या मूल्यावर अवलंबून, किंमत समान नाही!

जर मी आता हॅश फंक्शन मॉड्युलो 1 की चे बदलले (म्हणजे शेवटचे 000 अंक घेतात), तर दुसऱ्या लुकअपला फक्त 000 ऑपरेशन लागते कारण सेगमेंट 6 मध्ये कोणतेही घटक नाहीत. एक चांगले हॅश फंक्शन शोधणे हे खरे आव्हान आहे जे खूप कमी घटक असलेल्या बादल्या तयार करेल.

माझ्या उदाहरणात, चांगले हॅश फंक्शन शोधणे सोपे आहे. परंतु हे एक साधे उदाहरण आहे, जेव्हा की आहे तेव्हा चांगले हॅश फंक्शन शोधणे अधिक कठीण आहे:

• स्ट्रिंग (उदाहरणार्थ - आडनाव)
• 2 ओळी (उदाहरणार्थ - आडनाव आणि नाव)
• 2 ओळी आणि तारीख (उदाहरणार्थ - आडनाव, नाव आणि जन्मतारीख)
• ...

चांगल्या हॅश फंक्शनसह, हॅश टेबल लुकअपची किंमत O(1).

अॅरे वि हॅश टेबल

अॅरे का वापरत नाही?

हम्म, चांगला प्रश्न.

• हॅश टेबल असू शकते अंशतः मेमरी मध्ये लोड, आणि उर्वरित विभाग डिस्कवर राहू शकतात.
• अॅरेसह तुम्ही मेमरीमध्ये संलग्न जागा वापरणे आवश्यक आहे. जर तुम्ही मोठे टेबल लोड करत असाल पुरेशी सतत जागा शोधणे खूप कठीण आहे.
• हॅश टेबलसाठी, तुम्ही तुम्हाला हवी असलेली की निवडू शकता (उदाहरणार्थ, देश आणि व्यक्तीचे आडनाव).

अधिक माहितीसाठी, आपण याबद्दल लेख वाचू शकता जावाहॅशमॅप, जे हॅश टेबलची कार्यक्षम अंमलबजावणी आहे; या लेखात समाविष्ट असलेल्या संकल्पना समजून घेण्यासाठी तुम्हाला Java समजण्याची गरज नाही.

स्त्रोत: www.habr.com