डेटा संरचना में बी-पेड़ क्वेरी

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

बी-ट्री का उदाहरण -

खोज तकनीक बहुत हद तक बाइनरी सर्च ट्री के समान है। मान लीजिए हम उपरोक्त पेड़ से 66 खोजना चाहते हैं। तो हम जड़ से शुरू करेंगे, अब 66 मूल तत्व 46 से बड़ा है। तो हम जड़ के दाहिने बच्चे की ओर बढ़ेंगे। तब सही बच्चे में एक से अधिक तत्व होते हैं। तत्वों को क्रमबद्ध किया गया है, वे [56, 81] हैं। हमारा लक्ष्य कुंजी 56 से बड़ा है, लेकिन 81 से छोटा है, इसलिए हम सबट्री में प्रवेश करेंगे, जो 56 और 81 के बीच है। तो फिर हम लीफ स्तर पर चले गए हैं। उस समय हमें तत्व 66 मिल गया है।

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

एल्गोरिदम

BtreeSearch(root, key) -

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

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

x := Read root
if x is an index node, then
   if there is an object o in x, such that o->key = ‘key’, then return o->val
   Find the child of x, as x->child[i], whose key range is containing ‘key’
   return BTreeSearch(x->child[i], key)
else
   if there is an object o in x, such that o->key = ‘key’, then return o->val,
   else return null
   end if
end if