ডেটা স্ট্রাকচারে বি-ট্রি কোয়েরি

এখানে আমরা দেখব, বি-ট্রিতে কীভাবে অনুসন্ধান করা যায়। বি-ট্রি অনুসন্ধানকে বি-ট্রি অনুসন্ধান নামেও পরিচিত। ধরুন আমাদের নিচের মত একটি বি-ট্রি আছে -

বি-ট্রির উদাহরণ −

অনুসন্ধানের কৌশলটি বাইনারি অনুসন্ধান গাছের অনুরূপ। ধরুন আমরা উপরের গাছ থেকে 66 সার্চ করতে চাই। তাই আমরা রুট থেকে শুরু করব, এখন 66 রুট এলিমেন্ট 46 থেকে বড়। তাই আমরা রুটের ডান চাইল্ডে চলে যাব। তারপর ডান সন্তানের একাধিক উপাদান আছে। উপাদানগুলি সাজানো হয়েছে, তারা হল [56, 81]। আমাদের টার্গেট কী 56-এর থেকে বড়, কিন্তু 81-এর থেকে ছোট, তাই আমরা সাবট্রিতে প্রবেশ করব, যা 56 এবং 81-এর মধ্যে রয়েছে। তাই আমরা পাতার স্তরে চলে এসেছি। সেই মুহুর্তে আমরা 66 উপাদান পেয়েছি।

আসুন B-Tree-এর ভিতরে উপাদান অনুসন্ধান করার অ্যালগরিদম দেখি।

অ্যালগরিদম

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