এখানে আমরা দেখব, কিভাবে B+ Tree-এ সার্চিং করতে হয়। B+ ট্রি অনুসন্ধানকে B+ ট্রি অনুসন্ধান নামেও পরিচিত। এই অ্যালগরিদমটি বি-ট্রির অনুসন্ধানের সাথে অনেকটাই মিল। অধিকন্তু, এটি পরিসীমা ক্যোয়ারী সমর্থন করে। ধরুন আমাদের নিচের মত একটি B+ গাছ আছে -
B+ গাছের উদাহরণ −
অনুসন্ধানের কৌশলটি বাইনারি অনুসন্ধান গাছের অনুরূপ। ধরুন আমরা উপরের গাছ থেকে 63 সার্চ করতে চাই। সুতরাং আমরা রুট থেকে শুরু করব, এখন 63 মূল উপাদান 60 এর চেয়ে বড় কিন্তু 75 এর থেকে ছোট। তাই আমরা 60 মৌলের ডান চাইল্ডে চলে যাব। ডান শিশুটি 63। কিন্তু যদি আমরা B Tree ব্যবহার করি, তাহলে সেটা হবে ফলাফল. এই ক্ষেত্রে বর্তমান নোডটি অভ্যন্তরীণ নোড, তাহলে এটি একটি প্রকৃত তথ্য নয়। আমাদের প্রথমে সঠিক সন্তানের কাছে যেতে হবে। এবং পাতার স্তরে, আমরা রেকর্ড হিসাবে 63 খুঁজে পেতে পারি। এটাই হবে প্রকৃত ফলাফল।
আমরা যদি 63 থেকে 78 পর্যন্ত সমস্ত উপাদান অনুসন্ধান করতে চাই, তাহলে আমাদের প্রতিটি উপাদানকে একের পর এক ব্যাকট্র্যাক করার দরকার নেই। আমরা প্রাথমিক মানের লিফ নোড খুঁজে পাই, তারপরে লিঙ্ক করা লিফ নোড ব্যবহার করে, 78-এর আগে সব নোড খুঁজে বের করি। তাই এটি রেঞ্জ কোয়েরি সমর্থন করে।
আসুন B-Tree-এর ভিতরে উপাদান অনুসন্ধান করার অ্যালগরিদম দেখি।
অ্যালগরিদম
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
