बी+ ट्री : खोजें, डालें और मिटाएं Operaउदाहरण

बी+ वृक्ष क्या है?

A बी+ वृक्ष मुख्य रूप से कई स्तरों पर गतिशील अनुक्रमण को लागू करने के लिए उपयोग किया जाता है। बी-ट्री की तुलना में, बी+ ट्री डेटा पॉइंटर्स को केवल ट्री के लीफ नोड्स पर संग्रहीत करता है, जिससे खोज प्रक्रिया अधिक सटीक और तेज़ हो जाती है।

बी+ ट्री के लिए नियम

यहां बी+ ट्री के लिए आवश्यक नियम दिए गए हैं।

• पत्तियों का उपयोग डेटा रिकॉर्ड को संग्रहीत करने के लिए किया जाता है।
• यह वृक्ष के आंतरिक नोड्स में संग्रहीत होता है।
• यदि लक्ष्य कुंजी का मान आंतरिक नोड से कम है, तो उसके ठीक बाईं ओर स्थित बिंदु का अनुसरण किया जाता है।
• यदि लक्ष्य कुंजी का मान आंतरिक नोड से अधिक या उसके बराबर है, तो उसके ठीक दाईं ओर स्थित बिंदु का अनुसरण किया जाता है।
• मूल में कम से कम दो संतानें होती हैं।

B+ ट्री का उपयोग क्यों करें

B+ ट्री का उपयोग करने के कारण इस प्रकार हैं:

• कुंजी का उपयोग मुख्य रूप से उचित पत्ते की ओर निर्देशित करके खोज में सहायता के लिए किया जाता है।
• बी+ ट्री एक पेड़ में वृद्धि और कमी को प्रबंधित करने के लिए "भरण कारक" का उपयोग करता है।
• बी+ ट्री में, मेमोरी के पेज पर कई कुंजियाँ आसानी से रखी जा सकती हैं क्योंकि उनमें आंतरिक नोड्स से जुड़ा डेटा नहीं होता है। इसलिए, यह लीफ नोड पर मौजूद ट्री डेटा को जल्दी से एक्सेस कर लेगा।
• सभी तत्वों का एक व्यापक पूर्ण स्कैन एक वृक्ष है, जिसे केवल एक रैखिक पास की आवश्यकता होती है, क्योंकि B+ वृक्ष के सभी पत्ती नोड एक दूसरे से जुड़े होते हैं।

बी+ ट्री बनाम बी ट्री

यहां, बी+ ट्री और बी ट्री के बीच मुख्य अंतर दिए गए हैं

खोजें Operaउत्पादन

बी+ ट्री में, खोज सबसे आसान प्रक्रियाओं में से एक है और इससे तीव्र एवं सटीक परिणाम प्राप्त होते हैं।

निम्नलिखित खोज एल्गोरिथ्म लागू है:

• आवश्यक रिकॉर्ड ढूंढने के लिए, आपको निष्पादित करने की आवश्यकता है द्विआधारी खोज वृक्ष में उपलब्ध अभिलेखों पर.
• खोज कुंजी के साथ सटीक मिलान होने पर, संबंधित रिकॉर्ड उपयोगकर्ता को वापस कर दिया जाता है।
• यदि खोज के दौरान पैरेंट, वर्तमान या लीफ नोड में सटीक कुंजी नहीं मिलती है, तो उपयोगकर्ता को "नहीं मिला" संदेश प्रदर्शित किया जाता है।
• बेहतर और अधिक सटीक परिणामों के लिए खोज प्रक्रिया को पुनः चलाया जा सकता है।

खोजें Operaएल्गोरिथ्म

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

उत्पादन:

सटीक कुंजी के विरुद्ध मिलान किया गया रिकॉर्ड उपयोगकर्ता को प्रदर्शित किया जाता है; अन्यथा, उपयोगकर्ता को असफल प्रयास दिखाया जाता है।

सम्मिलित करें Operaउत्पादन

सम्मिलित ऑपरेशन के लिए निम्नलिखित एल्गोरिथ्म लागू है:

• नोड्स में 50 प्रतिशत तत्वों को भंडारण के लिए नए लीफ में ले जाया जाता है।
• नए लीफ के पैरेंट को न्यूनतम कुंजी मान और ट्री में एक नए स्थान के साथ सटीक रूप से जोड़ा गया है।
• यदि मूल नोड का पूर्ण उपयोग हो जाए तो उसे अधिक स्थानों में विभाजित करें।
• अब, बेहतर परिणामों के लिए, केंद्र कुंजी को उस लीफ के शीर्ष-स्तरीय नोड के साथ संबद्ध किया जाता है।
• जब तक शीर्ष-स्तरीय नोड नहीं मिल जाता, तब तक उपरोक्त चरणों में बताई गई प्रक्रिया को दोहराते रहें।

सम्मिलित करें Operaएल्गोरिथ्म

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. 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 tree
      b. 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.  

उत्पादन:

एल्गोरिथ्म तत्व का निर्धारण करेगा और उसे आवश्यक लीफ नोड में सफलतापूर्वक सम्मिलित करेगा।

उपरोक्त B+ ट्री नमूना उदाहरण नीचे दिए गए चरणों में समझाया गया है:

• सबसे पहले, हमारे पास 3 नोड्स हैं, और पहले 3 तत्व, जो 1, 4 और 6 हैं, नोड्स में उचित स्थानों पर जोड़े गए हैं।
• डेटा की श्रृंखला में अगला मान 12 है जिसे ट्री का हिस्सा बनाया जाना चाहिए।
• इसे प्राप्त करने के लिए, नोड को विभाजित करें, पॉइंटर तत्व के रूप में 6 जोड़ें।
• अब, वृक्ष का दायाँ पदानुक्रम बनाया जाता है, तथा शेष डेटा मानों को दाएँ ओर स्थित कुंजी-मान नोड्स के विरुद्ध बराबर या उससे अधिक मानों के लागू नियमों को ध्यान में रखते हुए तदनुसार समायोजित किया जाता है।

मिटाना Operaउत्पादन

बी+ ट्री में डिलीट प्रक्रिया की जटिलता, इन्सर्ट और सर्च कार्यक्षमता से अधिक है।

B+ ट्री से किसी तत्व को हटाते समय निम्नलिखित एल्गोरिथ्म लागू होता है:

• सबसे पहले, हमें ट्री में एक लीफ प्रविष्टि का पता लगाना होगा जो कुंजी और पॉइंटर को पकड़ रहा है। यदि लीफ रिकॉर्ड हटाने की सटीक शर्तों को पूरा करता है, तो ट्री से लीफ प्रविष्टि को हटा दें।
• यदि लीफ नोड केवल आधा भरा होने के संतोषजनक कारक को पूरा करता है, तो ऑपरेशन पूरा हो जाता है; अन्यथा, लीफ नोड में न्यूनतम प्रविष्टियां होती हैं और उन्हें हटाया नहीं जा सकता।
• दाएं और बाएं ओर के अन्य लिंक किए गए नोड किसी भी प्रविष्टि को खाली कर सकते हैं और फिर उन्हें लीफ में ले जा सकते हैं। यदि ये मानदंड पूरे नहीं होते हैं, तो उन्हें लीफ नोड और उसके लिंक किए गए नोड को ट्री पदानुक्रम में संयोजित करना चाहिए।
• लीफ नोड को उसके दाएं या बाएं पड़ोसी नोड के साथ विलय करने पर, शीर्ष-स्तरीय नोड की ओर इंगित करने वाले लीफ नोड या लिंक किए गए पड़ोसी नोड में मानों की प्रविष्टियां हटा दी जाती हैं।

उपरोक्त उदाहरण एक विशिष्ट क्रम के B+ वृक्ष से एक तत्व को हटाने की प्रक्रिया को दर्शाता है।

• सबसे पहले, हटाए जाने वाले तत्व के सटीक स्थानों की पहचान ट्री में की जाती है।
• यहाँ हटाए जाने वाले तत्व को केवल लीफ स्तर पर ही सटीक रूप से पहचाना जा सकता है, न कि इंडेक्स प्लेसमेंट पर। इसलिए, तत्व को हटाने के नियमों को प्रभावित किए बिना हटाया जा सकता है, जो कि न्यूनतम कुंजी का मान है।

• उपरोक्त उदाहरण में, हमें वृक्ष से 31 हटाना है।
• हमें इंडेक्स और लीफ में 31 के उदाहरणों का पता लगाना होगा।
• हम देख सकते हैं कि 31 इंडेक्स और लीफ नोड लेवल दोनों में उपलब्ध है। इसलिए, हम इसे दोनों इंस्टेंस से हटा देते हैं।
• लेकिन, हमें 42 की ओर इशारा करते हुए इंडेक्स भरना होगा। अब हम 25 से कम उम्र के दाएँ बच्चे को देखेंगे और न्यूनतम मान लेंगे और उसे इंडेक्स के रूप में रखेंगे। इसलिए, 42 एकमात्र मौजूद मान होने के कारण, यह इंडेक्स बन जाएगा।

मिटाना Operaएल्गोरिथ्म

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) 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 node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

उत्पादन:

कुंजी "K" को हटा दिया जाता है, और यदि आवश्यक हो तो n और उसके मूल नोड्स में मान समायोजित करने के लिए भाई-बहनों से कुंजियाँ उधार ली जाती हैं।

सारांश

• बी+ वृक्ष एक आत्म-संतुलन है डेटा संरचना डेटा पर सटीक और तेज़ खोज, सम्मिलित करने और हटाने की प्रक्रियाओं को निष्पादित करने के लिए
• हम आसानी से संपूर्ण डेटा या आंशिक डेटा प्राप्त कर सकते हैं, क्योंकि लिंक्ड ट्री संरचना के माध्यम से जाने से यह कुशल हो जाता है।
• बी+ वृक्ष संरचना संग्रहित रिकार्डों की संख्या में वृद्धि/कमी के साथ बढ़ती और सिकुड़ती है।
• लीफ नोड्स पर डेटा का भंडारण और तत्पश्चात आंतरिक नोड्स की शाखाएं स्पष्ट रूप से वृक्ष की ऊंचाई को कम कर देती हैं, जिससे डिस्क इनपुट और आउटपुट संचालन कम हो जाता है, और अंततः भंडारण उपकरणों पर बहुत कम स्थान की खपत होती है।