ডেটা স্ট্রাকচরে B-ট্রি কুয়েরি

এখানে আমরা দেখব, B-ট্রিতে সার্চিং কিভাবে করা যায়। B-ট্রি সার্চিংকে B-ট্রি কুয়েরিও বলা হয়। ধরি আমাদের নিচের মতো একটি B-ট্রি আছে −

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

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

B-ট্রির ভিতরে উপাদান সার্চ করার অ্যালগরিদম দেখি।

অ্যালগরিদম

BTreeSearch(root, key) −

ইনপুট − ট্রির রুট, এবং খুঁজতে চাওয়া কী

আউটপুট − কী সহ নোডের ভ্যালু, যদি না থাকে তবে null

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