बी + ट्री क्या है?
एक बी + ट्री मुख्य रूप से कई स्तरों पर गतिशील अनुक्रमण लागू करने के लिए उपयोग किया जाता है। बी- ट्री की तुलना में, बी + ट्री केवल पेड़ के पत्ती नोड्स पर डेटा पॉइंटर्स को संग्रहीत करता है, जिससे खोज अधिक प्रक्रिया को अधिक सटीक और तेज बनाता है।
इस B + ट्री ट्यूटोरियल में, आप सीखेंगे:
- बी + ट्री क्या है?
- बी + ट्री के लिए नियम
- B + ट्री का उपयोग क्यों करें
- बी + ट्री बनाम बी ट्री
- सर्च ऑपरेशन
- ऑपरेशन डालें
- ऑपरेशन हटाएं
बी + ट्री के लिए नियम
यहाँ B + ट्री के लिए आवश्यक नियम हैं।
- पत्तियां डेटा रिकॉर्ड को संग्रहीत करने के लिए उपयोग की जाती हैं।
- यह ट्री के आंतरिक नोड्स में संग्रहीत है।
- यदि लक्ष्य कुंजी मान आंतरिक नोड से कम है, तो बस इसके बाईं ओर बिंदु का पालन किया जाता है।
- यदि लक्ष्य कुंजी मान आंतरिक नोड से अधिक या बराबर है, तो बस इसके दाईं ओर बिंदु का पालन किया जाता है।
- जड़ में न्यूनतम दो बच्चे हैं।
B + ट्री का उपयोग क्यों करें
यहाँ, B + ट्री का उपयोग करने के कारण हैं:
- कुंजी मुख्य रूप से उचित पत्ती को निर्देशित करके खोज की सहायता के लिए उपयोग की जाती है।
- बी + ट्री एक पेड़ में वृद्धि और कमी का प्रबंधन करने के लिए "भरण कारक" का उपयोग करता है।
- बी + पेड़ों में, कई चाबियाँ आसानी से स्मृति के पृष्ठ पर रखी जा सकती हैं, क्योंकि उनके पास आंतरिक नोड्स से जुड़ा डेटा नहीं है। इसलिए, यह ट्री डेटा को लीफ नोड पर जल्दी से एक्सेस करेगा।
- सभी तत्वों का एक व्यापक पूर्ण स्कैन एक पेड़ है जिसे सिर्फ एक रैखिक पास की आवश्यकता होती है क्योंकि बी + पेड़ के सभी पत्ती नोड एक दूसरे से जुड़े होते हैं।
बी + ट्री बनाम बी ट्री
यहाँ, B + ट्री बनाम B ट्री के बीच मुख्य अंतर हैं
| ब + वृक्ष | बी ट्री |
| खोज कुंजियों को दोहराया जा सकता है। | खोज कुंजी निरर्थक नहीं हो सकती। |
| डेटा केवल पत्ती नोड्स पर सहेजा जाता है। | पत्ती नोड्स और आंतरिक नोड्स दोनों डेटा स्टोर कर सकते हैं |
| पत्ती नोड पर संग्रहीत डेटा खोज को अधिक सटीक और तेज बनाता है। | लीफ और आंतरिक नोड्स पर संग्रहीत डेटा के कारण खोज धीमी है। |
| विलोपन कठिन नहीं है क्योंकि एक तत्व केवल एक पत्ती नोड से हटा दिया जाता है। | तत्वों का विलोपन एक जटिल और समय लेने वाली प्रक्रिया है। |
| लिंक्ड लीफ नोड्स खोज को कुशल और त्वरित बनाते हैं। | आप लीफ नोड्स लिंक नहीं कर सकते। |
सर्च ऑपरेशन
बी + ट्री में, एक खोज निष्पादित करने और उससे तेज और सटीक परिणाम प्राप्त करने के लिए सबसे आसान प्रक्रियाओं में से एक है।
निम्नलिखित खोज एल्गोरिथ्म लागू है:
- आवश्यक रिकॉर्ड खोजने के लिए, आपको ट्री में उपलब्ध रिकॉर्ड पर बाइनरी खोज को निष्पादित करना होगा।
- खोज कुंजी के साथ सटीक मिलान के मामले में, संबंधित रिकॉर्ड उपयोगकर्ता को वापस कर दिया जाता है।
- यदि माता-पिता, करंट या लीफ नोड में खोज द्वारा सटीक कुंजी स्थित नहीं है, तो उपयोगकर्ता को "नहीं मिला संदेश" प्रदर्शित होता है।
- बेहतर और अधिक सटीक परिणामों के लिए खोज प्रक्रिया को फिर से चलाया जा सकता है।
खोज ऑपरेशन एल्गोरिथम
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
आउटपुट :
सटीक कुंजी के खिलाफ मिलान किए गए रिकॉर्ड सेट को उपयोगकर्ता को प्रदर्शित किया जाता है; अन्यथा, उपयोगकर्ता को विफल प्रयास दिखाया गया है।
ऑपरेशन डालें
निम्नलिखित एल्गोरिथ्म सम्मिलित ऑपरेशन के लिए लागू है:
- नोड्स में 50 प्रतिशत तत्वों को भंडारण के लिए एक नए पत्ते में ले जाया जाता है।
- नए पत्ते का जनक न्यूनतम कुंजी मूल्य और ट्री में एक नए स्थान के साथ सटीक रूप से जुड़ा हुआ है।
- माता-पिता नोड को अधिक स्थानों में विभाजित करें यदि यह पूरी तरह से उपयोग हो जाता है।
- अब, बेहतर परिणामों के लिए, केंद्र कुंजी उस पत्ता के शीर्ष-स्तरीय नोड के साथ जुड़ा हुआ है।
- जब तक शीर्ष-स्तरीय नोड नहीं मिलता है, तब तक उपरोक्त चरणों में बताई गई प्रक्रिया को जारी रखें।
ऑपरेशन एल्गोरिथ्म डालें
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
आउटपुट :
एल्गोरिथ्म तत्व का निर्धारण करेगा और इसे आवश्यक पत्ती नोड में सफलतापूर्वक सम्मिलित करेगा।
उपरोक्त बी + ट्री नमूना उदाहरण नीचे दिए गए चरणों में समझाया गया है:
- सबसे पहले, हमारे पास 3 नोड हैं, और पहले 3 तत्व, जो 1, 4 और 6 हैं, नोड्स में उपयुक्त स्थानों पर जोड़े जाते हैं।
- डेटा की श्रृंखला में अगला मान 12 है जिसे ट्री का हिस्सा बनाने की आवश्यकता है।
- इसे प्राप्त करने के लिए, नोड को विभाजित करें, एक सूचक तत्व के रूप में 6 जोड़ें।
- अब, एक पेड़ का दायां-पदानुक्रम बनाया गया है, और शेष डेटा मानों को सही पर कुंजी-मान नोड्स के खिलाफ मानों के बराबर या उससे अधिक के लागू नियमों को ध्यान में रखकर समायोजित किया जाता है।
ऑपरेशन हटाएं
B + ट्री में डिलीट प्रक्रिया की जटिलता सम्मिलित और खोज की कार्यक्षमता से अधिक है।
निम्नलिखित एल्गोरिथ्म B + ट्री से एक तत्व को हटाते समय लागू होता है:
- सबसे पहले, हमें ट्री में एक पत्ती प्रविष्टि का पता लगाने की आवश्यकता है जो कुंजी और सूचक को पकड़े हुए है। , पेड़ से पत्ती प्रविष्टि को हटा दें यदि पत्ता रिकॉर्ड विलोपन की सटीक शर्तों को पूरा करता है।
- यदि पत्ती नोड केवल आधा भरा होने के संतोषजनक कारक को पूरा करता है, तो ऑपरेशन पूरा हो गया है; अन्यथा, लीफ नोड में न्यूनतम प्रविष्टियाँ हैं और इन्हें हटाया नहीं जा सकता।
- दाएं और बाएं दूसरे लिंक किए गए नोड्स किसी भी प्रविष्टि को खाली कर सकते हैं फिर उन्हें लीफ पर ले जा सकते हैं। यदि ये मानदंड पूरे नहीं होते हैं, तो उन्हें पेड़ की पदानुक्रम में लीफ नोड और इसके जुड़े नोड को संयोजित करना चाहिए।
- दाएं या बाएं अपने पड़ोसियों के साथ पत्ती नोड के विलय पर, पत्ती नोड में मूल्यों की प्रविष्टियां या शीर्ष-स्तरीय नोड की ओर इशारा करते हुए जुड़े हुए पड़ोसी हटा दिए जाते हैं।
ऊपर दिया गया उदाहरण एक विशिष्ट क्रम के बी + ट्री से एक तत्व को निकालने की प्रक्रिया को दिखाता है।
- सबसे पहले, हटाए जाने वाले तत्व के सटीक स्थानों की पहचान ट्री में की जाती है।
- यहां डिलीट किए जाने वाले तत्व को केवल लीफ लेवल पर ही पहचाना जा सकता है न कि इंडेक्स प्लेसमेंट पर। इसलिए, तत्व को हटाने के नियमों को प्रभावित किए बिना हटाया जा सकता है, जो नंगे-न्यूनतम कुंजी का मूल्य है।
- उपरोक्त उदाहरण में, हमें ट्री से 31 को हटाना होगा।
- हमें सूचकांक और पत्ती में 31 के उदाहरणों का पता लगाने की आवश्यकता है।
- हम देख सकते हैं कि 31 सूचकांक और लीफ नोड स्तर दोनों में उपलब्ध है। इसलिए, हम इसे दोनों उदाहरणों से हटाते हैं।
- लेकिन, हमें 42 की ओर इशारा करते हुए सूचकांक को भरना होगा। हम अब 25 वर्ष से कम उम्र के बच्चे को देखेंगे और न्यूनतम मूल्य लेंगे और इसे सूचकांक के रूप में रखेंगे। तो, 42 केवल वर्तमान मूल्य होने के नाते, यह सूचकांक बन जाएगा।
ऑपरेशन एल्गोरिथ्म हटाएं
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
आउटपुट :
कुंजी "K" को हटा दिया गया है, और यदि आवश्यक हो तो n और इसके मूल नोड्स में मानों को समायोजित करने के लिए भाई-बहनों से कुंजी उधार ली जाती है।
सारांश:
- B + ट्री सटीक और तेजी से खोज, डेटा पर प्रक्रियाओं को सम्मिलित करने और हटाने के लिए एक आत्म-संतुलन डेटा संरचना है
- हम आसानी से पूर्ण डेटा या आंशिक डेटा प्राप्त कर सकते हैं क्योंकि लिंक किए गए ट्री संरचना के माध्यम से जाना इसे कुशल बनाता है।
- B + ट्री संरचना संग्रहीत रिकॉर्ड की संख्या में वृद्धि / कमी के साथ बढ़ती और सिकुड़ती है।
- पत्ती नोड्स पर डेटा का भंडारण और आंतरिक नोड्स की बाद की शाखाएं स्पष्ट रूप से पेड़ की ऊंचाई को छोटा करती हैं, जो डिस्क इनपुट और आउटपुट संचालन को कम करती है, अंततः भंडारण उपकरणों पर बहुत कम जगह का उपभोग करती है।