डेटा संरचना में बी ट्री: खोजें, डालें, हटाएं Operaउदाहरण
बी ट्री क्या है?
बी वृक्ष यह एक स्व-संतुलन डेटा संरचना है जो डेटा को तेज़ और मेमोरी कुशल तरीके से खोजने, सम्मिलित करने और हटाने के लिए नियमों के एक विशिष्ट सेट पर आधारित है। इसे प्राप्त करने के लिए, बी ट्री बनाने के लिए निम्नलिखित नियमों का पालन किया जाता है।
बी-ट्री डेटा संरचना में एक विशेष प्रकार का पेड़ है। 1972 में, इस पद्धति को पहली बार मैकक्रेइट द्वारा पेश किया गया था, और बेयर ने इसे हाइट बैलेंस्ड एम-वे सर्च ट्री नाम दिया था। यह आपको डेटा को सॉर्ट करने में मदद करता है और कम समय में इन्सर्ट, सर्चिंग और डिलीट जैसे विभिन्न ऑपरेशन करने की अनुमति देता है।
बी-ट्री के लिए नियम
यहां, B_Tree बनाने के लिए महत्वपूर्ण नियम दिए गए हैं
- सभी पत्ते एक ही स्तर पर बनाए जाएंगे।
- बी-ट्री को डिग्री की एक संख्या द्वारा निर्धारित किया जाता है, जिसे "ऑर्डर" भी कहा जाता है (एक बाहरी अभिनेता द्वारा निर्दिष्ट, जैसे प्रोग्रामर), जिसे संदर्भित किया जाता है
m
आगे. का मूल्य
m
यह उस डिस्क के ब्लॉक आकार पर निर्भर करता है जिस पर डेटा मुख्य रूप से स्थित होता है।
- नोड के बाएं उपवृक्ष में उपवृक्ष के दाएं भाग की तुलना में कम मान होंगे। इसका मतलब है कि नोड्स को बाएं से दाएं बढ़ते क्रम में भी क्रमबद्ध किया जाता है।
- एक रूट नोड तथा उसके चाइल्ड नोड्स में सम्मिलित चाइल्ड नोड्स की अधिकतम संख्या की गणना इस सूत्र द्वारा की जाती है:
m – 1
उदाहरण के लिए:
m = 4 max keys: 4 – 1 = 3
- रूट को छोड़कर प्रत्येक नोड में न्यूनतम कुंजियाँ होनी चाहिए
[m/2]-1
उदाहरण के लिए:
m = 4 min keys: 4/2-1 = 1
- किसी नोड में चाइल्ड नोड्स की अधिकतम संख्या उसकी डिग्री के बराबर होती है, जो कि है
m
- एक नोड की न्यूनतम संतानें ऑर्डर की आधी होती हैं, जो कि m/2 होती है (अधिकतम मान लिया जाता है)।
- एक नोड में सभी कुंजियाँ बढ़ते क्रम में व्यवस्थित होती हैं।
बी-ट्री का उपयोग क्यों करें?
बी-ट्री का उपयोग करने के कारण यहां दिए गए हैं
- डिस्क पर किए गए रीड की संख्या कम करता है
- बी ट्री को डिस्क आकार के अनुसार इसके आकार (यानी चाइल्ड नोड्स की संख्या) को समायोजित करने के लिए आसानी से अनुकूलित किया जा सकता है
- यह भारी मात्रा में डेटा को संभालने के लिए विशेष रूप से डिज़ाइन की गई तकनीक है।
- यह डेटाबेस और फ़ाइल सिस्टम के लिए एक उपयोगी एल्गोरिथम है।
- जब डेटा के बड़े ब्लॉक को पढ़ने और लिखने की बात आती है तो यह एक अच्छा विकल्प है
बी ट्री का इतिहास
- डेटा को डिस्क पर ब्लॉकों में संग्रहीत किया जाता है, जब इस डेटा को मुख्य मेमोरी (या RAM) में लाया जाता है तो उसे डेटा संरचना कहा जाता है।
- विशाल डेटा के मामले में, डिस्क में एक रिकॉर्ड को खोजने के लिए संपूर्ण डिस्क को पढ़ने की आवश्यकता होती है; इससे उच्च डिस्क एक्सेस आवृत्ति और डेटा आकार के कारण समय और मुख्य मेमोरी की खपत बढ़ जाती है।
- इस पर काबू पाने के लिए, इंडेक्स टेबल बनाए जाते हैं जो रिकॉर्ड्स के रिकॉर्ड संदर्भ को उन ब्लॉकों के आधार पर सहेजते हैं जिनमें वे स्थित होते हैं। इससे समय और मेमोरी की खपत में भारी कमी आती है।
- चूंकि हमारे पास विशाल डेटा है, इसलिए हम बहु-स्तरीय सूचकांक तालिकाएं बना सकते हैं।
- डेटा को स्व-संतुलित ढंग से क्रमबद्ध रखने के लिए बी ट्री का उपयोग करके बहु-स्तरीय सूचकांक डिजाइन किया जा सकता है।
Search Operaउत्पादन
खोज ऑपरेशन बी ट्री पर सबसे सरल ऑपरेशन है।
निम्नलिखित एल्गोरिथ्म लागू किया जाता है:
- कुंजी (मान) को “k” द्वारा खोजा जाना चाहिए।
- मूल से खोजना शुरू करें और पुनरावर्ती रूप से नीचे की ओर जाएँ।
- यदि k मूल मान से कम है, तो बाएँ उपवृक्ष में खोजें, यदि k मूल मान से अधिक है, तो दाएँ उपवृक्ष में खोजें।
- यदि नोड में k पाया गया है, तो बस नोड को वापस कर दें।
- यदि नोड में k नहीं मिलता है, तो अधिक कुंजी वाले चाइल्ड तक नीचे जाएँ।
- यदि k वृक्ष में नहीं मिलता है, तो हम NULL लौटाते हैं।
सम्मिलित करें Operaउत्पादन
चूंकि बी ट्री एक स्व-संतुलन वाला ट्री है, इसलिए आप किसी भी नोड में कुंजी को जबरन नहीं डाल सकते।
निम्नलिखित एल्गोरिथ्म लागू होता है:
- खोज ऑपरेशन चलाएं और सम्मिलन का उपयुक्त स्थान ढूंढें।
- नई कुंजी को उचित स्थान पर डालें, लेकिन यदि नोड में पहले से ही अधिकतम संख्या में कुंजियाँ हैं:
- नोड, नई डाली गई कुंजी के साथ, मध्य तत्व से अलग हो जाएगा।
- मध्य तत्व अन्य दो संतान नोड्स के लिए पैरेंट बन जाएगा।
- नोड्स को कुंजियों को आरोही क्रम में पुनः व्यवस्थित करना होगा।
सुझाव | सम्मिलन एल्गोरिथ्म के बारे में निम्नलिखित बात सत्य नहीं है:
चूंकि नोड पूर्ण है, इसलिए यह विभाजित हो जाएगा, और फिर एक नया मान डाला जाएगा |
उपरोक्त उदाहरण में:
- कुंजी के लिए नोड में उचित स्थान खोजें
- लक्ष्य नोड में कुंजी डालें, और नियमों की जांच करें
- सम्मिलन के बाद, क्या नोड में न्यूनतम संख्या के बराबर कुंजियाँ हैं, जो 1 है? इस मामले में, हाँ, ऐसा है। अगला नियम देखें।
- सम्मिलन के बाद, क्या नोड में अधिकतम संख्या से ज़्यादा कुंजियाँ हैं, जो 3 है? इस मामले में, नहीं, ऐसा नहीं है। इसका मतलब है कि बी ट्री किसी भी नियम का उल्लंघन नहीं कर रहा है, और सम्मिलन पूरा हो गया है।
उपरोक्त उदाहरण में:
- नोड कुंजियों की अधिकतम संख्या तक पहुँच गया है
- नोड विभाजित हो जाएगा, और मध्य कुंजी शेष दो नोड्स का मूल नोड बन जाएगी।
- कुंजियों की सम संख्या होने पर, मध्य नोड का चयन बाएं बायस या दाएं बायस द्वारा किया जाएगा।
उपरोक्त उदाहरण में:
- नोड में अधिकतम से कम कुंजियाँ हैं
- 1 को 3 के आगे डाला गया है, लेकिन आरोही क्रम नियम का उल्लंघन किया गया है
- इसे ठीक करने के लिए, कुंजियों को क्रमबद्ध किया गया है
इसी प्रकार, 13 और 2 को नोड में आसानी से डाला जा सकता है क्योंकि वे नोड्स के लिए अधिकतम कुंजी नियम से कम को पूरा करते हैं।
उपरोक्त उदाहरण में:
- नोड में अधिकतम कुंजियों के बराबर कुंजियाँ होती हैं।
- कुंजी को लक्ष्य नोड में डाला जाता है, लेकिन यह अधिकतम कुंजी के नियम का उल्लंघन करता है।
- लक्ष्य नोड विभाजित हो गया है, तथा बायीं ओर झुकाव वाली मध्य कुंजी अब नए चाइल्ड नोड की पैरेंट है।
- नये नोड्स को आरोही क्रम में व्यवस्थित किया गया है।
इसी प्रकार, उपरोक्त नियमों और मामलों के आधार पर, शेष मानों को बी ट्री में आसानी से डाला जा सकता है।
मिटाना Operaउत्पादन
डिलीट ऑपरेशन में इन्सर्ट और सर्च ऑपरेशन की तुलना में अधिक नियम होते हैं।
निम्नलिखित एल्गोरिथ्म लागू होता है:
- खोज ऑपरेशन चलाएं और नोड्स में लक्ष्य कुंजी ढूंढें
- लक्ष्य कुंजी के स्थान के आधार पर तीन शर्तें लागू होती हैं, जैसा कि निम्नलिखित अनुभागों में बताया गया है
यदि लक्ष्य कुंजी लीफ नोड में है
- Target लीफ नोड में, न्यूनतम कुंजियों से अधिक है।
- इसे हटाने से B Tree की संपत्ति का उल्लंघन नहीं होगा
- Target लीफ नोड में है, इसमें न्यूनतम कुंजी नोड हैं
- इसे हटाने से B Tree की संपत्ति का उल्लंघन होगा
- Target नोड तत्काल बाएं नोड, या तत्काल दाएं नोड (भाई) से कुंजी उधार ले सकता है
- भाई-बहन कहेंगे हाँ यदि इसमें न्यूनतम संख्या से अधिक कुंजियाँ हों
- कुंजी को मूल नोड से उधार लिया जाएगा, अधिकतम मान मूल नोड में स्थानांतरित किया जाएगा, मूल नोड का अधिकतम मान लक्ष्य नोड में स्थानांतरित किया जाएगा, और लक्ष्य मान को हटा दिया जाएगा
- Target लीफ नोड में है, लेकिन किसी भी भाई-बहन के पास न्यूनतम संख्या से अधिक कुंजियाँ नहीं हैं
- कुंजी खोजें
- भाई-बहनों और न्यूनतम पैरेंट नोड्स के साथ विलय करें
- कुल कुंजियाँ अब न्यूनतम 1000 से अधिक होंगी
- लक्ष्य कुंजी को मूल नोड के न्यूनतम मान से प्रतिस्थापित किया जाएगा
यदि लक्ष्य कुंजी किसी आंतरिक नोड में है
- या तो चुनें, क्रमानुसार पूर्ववर्ती या क्रमानुसार उत्तराधिकारी
- क्रम-पूर्ववर्ती के मामले में, इसके बाएं उपवृक्ष से अधिकतम कुंजी का चयन किया जाएगा
- क्रम-क्रम उत्तराधिकारी के मामले में, उसके दाएं उपवृक्ष से न्यूनतम कुंजी का चयन किया जाएगा
- यदि लक्ष्य कुंजी के इन-ऑर्डर पूर्ववर्ती में न्यूनतम कुंजियों से अधिक कुंजियाँ हैं, तभी वह लक्ष्य कुंजी को इन-ऑर्डर पूर्ववर्ती की अधिकतम कुंजी से प्रतिस्थापित कर सकता है
- यदि लक्ष्य कुंजी के क्रमित पूर्ववर्ती में न्यूनतम कुंजियों से अधिक नहीं हैं, तो क्रमित उत्तराधिकारी की न्यूनतम कुंजी देखें।
- यदि लक्ष्य कुंजी के क्रम-पूर्ववर्ती और परवर्ती दोनों में न्यूनतम कुंजी से कम कुंजियाँ हैं, तो पूर्ववर्ती और परवर्ती को मर्ज करें।
यदि लक्ष्य कुंजी रूट नोड में है
- क्रम-पूर्ववर्ती उपवृक्ष के अधिकतम तत्व से प्रतिस्थापित करें
- यदि, हटाने के बाद, लक्ष्य में न्यूनतम कुंजी से कम कुंजियाँ हैं, तो लक्ष्य नोड अपने भाई-बहन के पैरेंट के माध्यम से अपने भाई-बहन से अधिकतम मान उधार लेगा।
- पैरेंट का अधिकतम मान लक्ष्य द्वारा लिया जाएगा, लेकिन सिबलिंग के अधिकतम मान के नोड्स के साथ।
अब, आइए एक उदाहरण से डिलीट ऑपरेशन को समझें।
उपरोक्त आरेख बी-ट्री में डिलीट ऑपरेशन के विभिन्न मामलों को प्रदर्शित करता है। यह बी-ट्री क्रम 5 का है, जिसका अर्थ है कि किसी भी नोड में चाइल्ड नोड्स की न्यूनतम संख्या 3 हो सकती है, और किसी भी नोड में चाइल्ड नोड्स की अधिकतम संख्या 5 हो सकती है। जबकि किसी भी नोड में कुंजियों की न्यूनतम और अधिकतम संख्या क्रमशः 2 और 4 हो सकती है।
उपरोक्त उदाहरण में:
- लक्ष्य नोड में हटाने के लिए लक्ष्य कुंजी है
- लक्ष्य नोड में न्यूनतम कुंजियों से अधिक कुंजियाँ हैं
- बस कुंजी को हटा दें
उपरोक्त उदाहरण में:
- लक्ष्य नोड में न्यूनतम कुंजियों के बराबर कुंजियाँ हैं, इसलिए इसे सीधे हटाया नहीं जा सकता क्योंकि यह शर्तों का उल्लंघन होगा
अब, निम्नलिखित चित्र बताता है कि इस कुंजी को कैसे हटाया जाए:
- लक्ष्य नोड अपने निकटतम सहोदर से कुंजी उधार लेगा, इस मामले में, क्रम-पूर्ववर्ती (बायां सहोदर) क्योंकि इसका कोई क्रम-उत्तराधिकारी (दायां सहोदर) नहीं है।
- इनऑर्डर पूर्ववर्ती का अधिकतम मान पैरेंट को हस्तांतरित कर दिया जाएगा, तथा पैरेंट अधिकतम मान को लक्ष्य नोड को हस्तांतरित कर देगा (नीचे आरेख देखें)
निम्नलिखित उदाहरण यह दर्शाता है कि किसी कुंजी को उसके क्रमित उत्तराधिकारी से किस प्रकार हटाया जाए, जिसके लिए मान की आवश्यकता होती है।
- लक्ष्य नोड अपने निकटतम सहोदर से कुंजी उधार लेगा, इस मामले में, क्रमानुसार उत्तराधिकारी (दायां सहोदर) क्योंकि इसके क्रमानुसार पूर्ववर्ती (बायां सहोदर) में न्यूनतम कुंजियों के बराबर कुंजियाँ हैं।
- इन-ऑर्डर उत्तराधिकारी का न्यूनतम मान पैरेंट को हस्तांतरित कर दिया जाएगा, तथा पैरेंट अधिकतम मान लक्ष्य नोड को हस्तांतरित कर देगा।
नीचे दिए गए उदाहरण में, लक्ष्य नोड का कोई भी भाई-बहन नहीं है जो लक्ष्य नोड को अपनी कुंजी दे सके। इसलिए, विलय की आवश्यकता है।
ऐसी कुंजी को हटाने की प्रक्रिया देखें:
- लक्ष्य नोड को उसके किसी भी निकटतम भाई-बहन के साथ मूल कुंजी के साथ मर्ज करें
- मूल नोड से कुंजी का चयन किया जाता है जो दो विलय नोड्स के बीच में भाई-बहन है
- मर्ज किए गए नोड से लक्ष्य कुंजी हटाएं
मिटाना Operation छद्म कोड
private int removeBiggestElement() { if (root has no child) remove and return the last element else { answer = subset[childCount-1].removeBiggestElement() if (subset[childCount-1].dataCount < MINIMUM) fixShort (childCount-1) return answer } }
उत्पादन:
बी-ट्री से सबसे बड़ा तत्व हटा दिया जाता है।
सारांश
- बी ट्री डिस्क से डेटा की बेहतर खोज, सम्मिलन और विलोपन के लिए एक स्व-संतुलन डेटा संरचना है।
- बी ट्री निर्दिष्ट डिग्री द्वारा विनियमित है
- बी ट्री कुंजियाँ और नोड्स आरोही क्रम में व्यवस्थित हैं।
- बी ट्री का खोज ऑपरेशन सबसे सरल है, जो हमेशा रूट से शुरू होता है और यह जांचना शुरू करता है कि लक्ष्य कुंजी नोड मान से अधिक है या कम।
- बी ट्री का सम्मिलन ऑपरेशन काफी विस्तृत है, जो पहले लक्ष्य कुंजी के लिए सम्मिलन की उपयुक्त स्थिति ढूंढता है, उसे सम्मिलित करता है, विभिन्न मामलों के विरुद्ध बी ट्री की वैधता का मूल्यांकन करता है, और फिर उसके अनुसार बी ट्री नोड्स को पुनर्गठित करता है।
- बी ट्री का डिलीट ऑपरेशन सबसे पहले डिलीट की जाने वाली लक्ष्य कुंजी को खोजता है, उसे डिलीट करता है, तथा लक्ष्य नोड, सिबलिंग और पैरेंट की न्यूनतम और अधिकतम कुंजियों जैसे कई मामलों के आधार पर वैधता का मूल्यांकन करता है।