डेटा संरचना में B+ ट्री क्वेरी

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

B+ ट्री का उदाहरण -

खोज तकनीक बहुत हद तक बाइनरी सर्च ट्री के समान है। मान लीजिए हम उपरोक्त पेड़ से 63 खोजना चाहते हैं। तो हम मूल से शुरू करेंगे, अब 63 मूल तत्व 60 से बड़ा है लेकिन 75 से छोटा है। इसलिए हम तत्व 60 के दाहिने बच्चे की ओर बढ़ेंगे। सही बच्चा 63 है। लेकिन अगर हम B ट्री का उपयोग करते हैं, तो वह होगा परिणाम। इस मामले में चूंकि वर्तमान नोड आंतरिक नोड है, तो वह वास्तविक डेटा नहीं है। हमें पहले सही बच्चे के पास जाना होगा। और पत्ती के स्तर पर, हम 63 को रिकॉर्ड के रूप में पा सकते हैं। यही वास्तविक परिणाम होगा।

यदि हम 63 से 78 तक सभी तत्वों को खोजना चाहते हैं, तो हमें प्रत्येक तत्व को एक-एक करके पीछे करने की आवश्यकता नहीं है। हम प्रारंभिक मान का लीफ नोड ढूंढते हैं, फिर लिंक किए गए लीफ नोड्स का उपयोग करके, 78 से पहले सभी नोड्स ढूंढते हैं। तो यह रेंज क्वेरी का समर्थन करता है।

आइए बी-ट्री के अंदर तत्व खोजने के लिए एल्गोरिथम देखें।

एल्गोरिदम

BPlusTreeSearch(root, key) −

इनपुट -पेड़ की जड़, और खोजने की कुंजी

आउटपुट - कुंजी के साथ नोड का मान, यदि यह मौजूद नहीं है, तो शून्य लौटाएं

Apply binary search on records
if record with the ‘key’ is found, then
   return required record
else if current node is leaf node, and key is not found, then
   return null