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