बी-वृक्ष

परिचय

पेड़ डेटा संरचनाएं हैं जिनमें गतिशील सेटों पर संचालन लागू किया जाता है। इन परिचालनों में, मैं तत्व की खोज करना चाहता हूं, न्यूनतम (अधिकतम) तत्व की खोज करना, सम्मिलन, विलोपन, माता-पिता के लिए संक्रमण, बच्चे को संक्रमण। इस प्रकार, पेड़ को एक सामान्य शब्दकोश के रूप में और प्राथमिकता कतार के रूप में दोनों का उपयोग किया जा सकता है।

पेड़ों में मुख्य संचालन एक समय में इसकी ऊँचाई के अनुपात में किया जाता है। संतुलित पेड़ उनकी ऊंचाई को कम करते हैं (उदाहरण के लिए, एन नोड्स के साथ एक द्विआधारी संतुलित पेड़ की ऊंचाई लॉग एन है)। अधिकांश संतुलित वृक्षों जैसे लाल-काले वृक्ष, एवीएल वृक्ष, कार्तीय वृक्ष से परिचित हैं, इसलिए हम गहराई तक नहीं जाएंगे।

इन मानक खोज पेड़ों के साथ क्या समस्या है? उल्लिखित पेड़ों में से एक के रूप में प्रस्तुत एक विशाल डेटाबेस पर विचार करें। जाहिर है, हम रैम में इस सारे पेड़ को स्टोर नहीं कर सकते हैं = हम इसमें केवल जानकारी का एक हिस्सा संग्रहीत करते हैं, बाकी को तीसरे पक्ष के माध्यम (उदाहरण के लिए, एक हार्ड डिस्क, एक्सेस स्पीड, जो बहुत धीमी है) पर संग्रहीत किया जाता है। लाल-काले या कार्टेशियन जैसे पेड़ों को हमें एन-थर्ड पार्टी कैरियर में एन कॉल लॉग करने की आवश्यकता होगी। बड़े एन के लिए यह बहुत कुछ है। यह ठीक यही समस्या है कि बी-ट्रीज़ को हल करने के लिए डिज़ाइन किया गया है!

बी-पेड़ भी संतुलित पेड़ हैं, इसलिए उनमें मानक संचालन समय ऊंचाई के लिए आनुपातिक है। लेकिन, बाकी पेड़ों के विपरीत, वे विशेष रूप से डिस्क मेमोरी (पिछले उदाहरण में - तीसरे पक्ष के मीडिया) के साथ कुशल काम के लिए बनाए गए थे, या बल्कि, वे I / O प्रकार के आक्रमणों को कम करते हैं।

संरचना

बी-ट्री का निर्माण करते समय, कारक टी, जिसे न्यूनतम डिग्री कहा जाता है, को लागू किया जाता है। प्रत्येक नोड, रूट को छोड़कर, कम से कम t - 1, और 2t - 1 कुंजी से अधिक नहीं होना चाहिए। यह n [x] निर्दिष्ट है - नोड x में कुंजियों की संख्या।

नोड में कीज़ को गैर-घटते क्रम में संग्रहीत किया जाता है। यदि x एक पत्ती नहीं है, तो इसमें n [x] + 1 बच्चे हैं। यदि हम नोड x में k [i] और बच्चों c [i] के रूप में कुंजी रखते हैं, तो रूट c [i] (k1) के साथ एक उपप्रकार की कुंजी के लिए, निम्नलिखित असमानता रखती है - k [i-1] ≤k1≤ k [i] (c [0] के लिए: k [i-1] =-and, और c [n [x]] के लिए: k [i] = + ∞)। इस प्रकार, नोड की चाबियाँ उनके बच्चों की कुंजी के लिए सीमा निर्धारित करती हैं।

बी-ट्री के सभी पत्ते एक ही ऊंचाई पर स्थित होने चाहिए, जो कि पेड़ की ऊंचाई है। N of 1 नोड्स के साथ बी-ट्री की ऊंचाई और t ≥ 2 की एक न्यूनतम डिग्री logt (n + 1) से अधिक नहीं होती है। यह एक बहुत ही महत्वपूर्ण कथन है (क्यों - हम थोड़ी देर बाद समझेंगे)!

h 2 logt ((n + 1) / 2) t का आधार लघुगणक है।

बी-ट्री ऑपरेशन

जैसा कि ऊपर उल्लेख किया गया है, बी-ट्री में, खोज, डालने, हटाने आदि के लिए सभी मानक संचालन किए जाते हैं।

खोज

बी-ट्री में खोज बाइनरी ट्री में खोज के समान है, केवल यहां हमें 2 विकल्पों से नहीं, बल्कि कई से वंशज का रास्ता चुनना होगा। अन्यथा, कोई मतभेद नहीं हैं। नीचे दिया गया चित्र कुंजी 27 की खोज दिखाता है। आइए हम दृष्टांत समझाते हैं (और, तदनुसार, मानक खोज एल्गोरिदम):

• हम जड़ की कुंजी का पालन करते हैं, जबकि यह आवश्यक से कम है। इस मामले में, हम 31 पर पहुँच गए।
• हम बच्चे के लिए नीचे उतरते हैं, जो इस कुंजी के बाईं ओर है।
• हम नए नोड की कुंजियों का पालन करते हैं, जबकि 27 से कम है। इस मामले में, हमने 27 पाया और बंद कर दिया।

खोज ऑपरेशन समय O (t logt n) में किया जाता है, जहां t न्यूनतम डिग्री है। यहाँ यह महत्वपूर्ण है कि हम डिस्क संचालन केवल O (logt n) करें!

इसके अलावा

खोज के विपरीत, बाइनरी ट्री की तुलना में ऐड ऑपरेशन बहुत अधिक जटिल है, क्योंकि आप बस एक नई शीट नहीं बना सकते हैं और वहां कुंजी डाल सकते हैं, क्योंकि बी-ट्री के गुणों का उल्लंघन होगा। पहले से भरे हुए शीट में एक चाबी डालना भी असंभव है = => नोड को 2 में विभाजित करने का संचालन आवश्यक है। यदि शीट भरी गई थी, तो 2t-1 कीज़ थीं => हम इसे 2 में t-1 से विभाजित करते हैं, और मध्य तत्व (जिसके लिए t-1 पहला है) कम कुंजियाँ हैं, और बाद का t-1 बड़ा है) मूल नोड में जाता है। तदनुसार, यदि मूल नोड पूर्ण भी था, तो फिर से हमें विभाजित करना होगा। और इसलिए जड़ पर (यदि जड़ टूट गई है, तो एक नई जड़ दिखाई देती है और पेड़ की गहराई बढ़ जाती है)। जैसे कि साधारण बाइनरी पेड़ों के मामले में, जड़ से पत्ती तक एक पास में सम्मिलन किया जाता है। प्रत्येक पुनरावृत्ति पर (एक नई कुंजी के लिए स्थिति की तलाश में - जड़ से पत्ती तक), हम सभी भरे हुए नोड्स को तोड़ते हैं जिसके माध्यम से हम जाते हैं (पत्ती सहित)। इस प्रकार, यदि आपको सम्मिलित करने के लिए कुछ नोड को तोड़ने की आवश्यकता है, तो हमें यकीन है कि इसका मूल पूर्ण नहीं है!

नीचे दिया गया चित्र उसी पेड़ को दिखाता है जैसे खोज (t = 3)। केवल अब हम कुंजी "15" जोड़ते हैं। एक नई कुंजी के लिए एक स्थिति की तलाश में, हम एक आबादी वाले नोड (7, 9, 11, 13, 16) पर ठोकर खाते हैं। एल्गोरिथ्म का अनुसरण करते हुए, हम इसे तोड़ते हैं - इस मामले में, "11" मूल नोड में जाता है, और मूल एक को 2 में विभाजित किया जाता है। अगला, "15" कुंजी को दूसरे "ब्रेकवे" नोड में डाला जाता है। बी-ट्री के सभी गुण बच जाते हैं!





ऐड ऑपरेशन O (t logt n) के दौरान भी होता है। यह फिर से महत्वपूर्ण है कि हम डिस्क संचालन केवल ओ (एच) करते हैं, जहां एच पेड़ की ऊंचाई है।

निष्कासन

बी-ट्री से चाबी निकालना, डालने से भी अधिक बोझिल और जटिल है। यह इस तथ्य के कारण है कि आंतरिक नोड से हटाने के लिए पूरे के रूप में पेड़ के पुनर्निर्माण की आवश्यकता होती है। सम्मिलन के समान, यह सत्यापित करना आवश्यक है कि हम बी-ट्री के गुणों को संरक्षित करते हैं, केवल इस मामले में यह निगरानी करना आवश्यक है कि चाबियाँ टी -1 हैं (यदि कुंजी इस नोड से हटा दी जाती है, तो नोड मौजूद नहीं हो सकता है)। विलोपन एल्गोरिथ्म पर विचार करें:
1) यदि एक शीट से विलोपन होता है, तो यह जांचना आवश्यक है कि इसमें कितनी चाबियाँ हैं। यदि टी -1 से अधिक है, तो हम बस इसे हटा देते हैं और कुछ और करने की आवश्यकता नहीं है। अन्यथा, यदि कोई पड़ोसी पत्ता है (उसके बगल में स्थित है और उसी माता-पिता के पास है) जिसमें टी -1 कुंजी से अधिक हैं, तो हम इस पड़ोसी से एक कुंजी चुनेंगे, जो पड़ोसी नोड की शेष कुंजियों और स्रोत नोड के बीच एक विभाजक है (अर्थात, और नहीं) सभी एक समूह से और सभी दूसरे से कम नहीं)। यह कुंजी k1 हो। हम मूल नोड से कुंजी k2 का चयन करते हैं, जो स्रोत नोड और इसके पड़ोसी का विभाजक है, जिसे हमने पहले चुना था। हम स्रोत नोड से कुंजी को हटाते हैं (जिसे हटाने की आवश्यकता होती है), k2 को इस नोड पर जाने दें, और k2 के बजाय पैरेंट नोड में k1 डालें। इसे स्पष्ट करने के लिए, नीचे दिया गया चित्र (चित्र 1) प्रस्तुत किया गया है, जहाँ कुंजी "9" को हटा दिया गया है। यदि हमारे नोड के सभी पड़ोसियों के पास टी -1 कुंजी है। फिर हम इसे किसी भी पड़ोसी के साथ जोड़ते हैं, वांछित कुंजी को हटाते हैं। और मूल नोड से कुंजी, जो इन दो "पूर्व" पड़ोसियों के लिए विभाजक थी, को हमारे नवगठित नोड में ले जाया जाएगा (जाहिर है, यह इसमें एक मंझला होगा)।
अंजीर। 1।


2) अब आंतरिक नोड x से की के को हटाने पर विचार करें। यदि कुंजी k से पहले के बच्चे के नोड में t-1 कुंजी से अधिक है, तो हम k1 - इस नोड के उपशीर्षक में k का पूर्ववर्ती पाते हैं। इसे हटा दें (पुन: हमारे एल्गोरिथ्म को चलाएं)। K1 के साथ सोर्स नोड में k को बदलें। हम एक समान काम करते हैं यदि कुंजी के बाद बच्चे के नोड में टी -1 कुंजी से अधिक है। यदि दोनों (अगले और पिछले बच्चे के नोड्स) में टी -1 कुंजी है, तो हम इन बच्चों को जोड़ते हैं, उन्हें कश्मीर में स्थानांतरित करते हैं, और फिर नए नोड से कश्मीर हटाते हैं (हम अपने एल्गोरिदम को पुनरावर्ती रूप से चलाते हैं)। यदि जड़ के अंतिम 2 वंशज विलीन हो जाते हैं, तो वे जड़ बन जाते हैं, और पिछली जड़ को मुक्त कर दिया जाता है। नीचे एक चित्र (छवि 2) है, जहां "11" को जड़ से हटा दिया जाता है (मामला जब अगले नोड में टी -1 से अधिक बच्चे हैं)।
अंजीर। २।


डिलीट ऑपरेशन उसी समय होता है जब इन्सर्ट O (t logt n) के रूप में होता है। हां, और डिस्क संचालन के लिए केवल ओ (एच) की आवश्यकता होती है, जहां एच पेड़ की ऊंचाई है।

इसलिए, हमने यह सुनिश्चित किया कि बी-ट्री एक तेज़ डेटा संरचना है (साथ ही लाल-काला, एवीएल)। और एक और महत्वपूर्ण संपत्ति जो हमने मानक संचालन पर विचार करके प्राप्त की - शेष संपत्ति का स्वचालित रखरखाव - हम ध्यान दें कि हम इसे विशेष रूप से कहीं भी संतुलित नहीं करते हैं।

डेटाबेस

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

जाहिर है, बढ़ती टी (न्यूनतम डिग्री), हम अपने पेड़ की शाखाओं को बढ़ाते हैं, और इसलिए ऊंचाई कम करते हैं! क्या टी चुनें? - हमारे पास उपलब्ध रैम के आकार के अनुसार चुनें (यानी हम एक समय में कितनी चाबियाँ देख सकते हैं)। आमतौर पर यह संख्या 50 से 2000 के बीच की होती है। आइए जानें कि मानक उदाहरण पर हमें ब्रांचिंग ट्री क्या देता है, जो कि बी-ट्री के बारे में सभी लेखों में उपयोग किया जाता है। मान लीजिए हमारे पास एक बिलियन कुंजी है, और टी = 1001 है। फिर हमें किसी भी कुंजी को खोजने के लिए केवल 3 डिस्क संचालन की आवश्यकता है! उसी समय, हम इस बात को ध्यान में रखते हैं कि हम रूट को स्थायी रूप से स्टोर कर सकते हैं। अब आप देखें कि यह कितना कम है!

इसके अलावा, हम अलग-अलग जगहों से नहीं, बल्कि पूरे ब्लॉक में अलग-अलग डेटा पढ़ते हैं। ट्री नोड को रैम में स्थानांतरित करते हुए, हम अनुक्रमिक मेमोरी के आवंटित ब्लॉक को स्थानांतरित करते हैं, इसलिए यह ऑपरेशन काफी जल्दी काम करता है।

तदनुसार, हमारे पास सर्वर पर एक न्यूनतम लोड है, और एक ही समय में एक कम विलंबता है। इन और अन्य वर्णित लाभों ने डीबीएमएस में बी-पेड़ों को पेड़-आधारित अनुक्रमितों का आधार बनने की अनुमति दी है।

अपडेट: विजुअलाइज़र

साहित्य

"एल्गोरिदम। निर्माण और विश्लेषण "थॉमस कॉर्मेन, चार्ल्स लेज़रसन, रोनाल्ड रिवेस्ट, क्लिफोर्ड स्टीन (दूसरा संस्करण)
"प्रोग्रामिंग की कला। क्रमबद्ध करें और खोजें »डोनाल्ड नथ।