এখানে আমরা দেখব, কিভাবে B+ Tree থেকে একটি নোড ডিলিট করা যায়। ধরুন আমাদের একটি B+ বৃক্ষ আছে যেমন 7 মাইনাসের নিচে;
B+ গাছের উদাহরণ −
মুছে ফেলার দুটি অংশ আছে। প্রথমে আমাদের উপাদানটি খুঁজে বের করতে হবে। সেই কৌশলটি প্রশ্ন করার মতো। এখন মুছে ফেলার জন্য, আমাদের কিছু নিয়মের যত্ন নিতে হবে। একটি নোডে কমপক্ষে m/2 উপাদান থাকতে হবে। সুতরাং যদি আমরা মুছে ফেলি, একটি উপাদান, এবং এটিতে m-1 এর কম উপাদান অবশিষ্ট থাকে, তাহলে এটি নিজেকে সামঞ্জস্য করবে। যদি পুরো নোডটি মুছে ফেলা হয়, তাহলে এর বাচ্চাদের একত্রিত করা হবে, এবং যদি তাদের আকার m এর মতো হয়, তাহলে তাদের দুটি অংশে বিভক্ত করুন, এবং আবার মধ্যম মান বেড়ে যাবে।
ধরুন আমরা 78 ডিলিট করতে চাই। এখন দুটি বাচ্চা আছে। [75, 77], এবং [78, 85], তারপর এটি প্রথমে লিফ নোড থেকে 78 মুছে ফেলবে, তারপরে 85 নেবে এবং কী 85-এর একটি অনুলিপি তৈরি করবে এবং এটিকে সাবট্রির মূল হিসাবে তৈরি করবে।
অ্যালগরিদম
BPlusTreeDelete(x, কী) −
ইনপুট - গাছের মূল, এবং মুছে ফেলার কী
We will assume, that the key is present into the list Start from root node, perform exact match for key as ‘key’ till a leaf node. Let the search path be x1, x2, … , xh. The x1 is first node so root, then xh is leaf node. Each node xi is parent of xi+1 delete the object where key is ‘key’ from xh. if h = 1, then return, as there is only one node which is root. i := h while xi underflows, do if immediate sibling node s of xi, has at least m/2 + 1 elements, then redistribute entries evenly between s and xi. corresponding to redistribution, a key k in the parent node xi-1, will be changed. if xi is non-leaf node, then k is dragged down to xi. and a key from s is pushed up to fill the place of k else k is simply replaced by a key in s return else merge xi with the sibling node s. Delete the corresponding child pointer in xi-1. if xi is an internal node, then drag the key in xi-1. which is previously divides xi and s. into the new node xi and s, into the new node xi. else delete that key in xi-1. i := i – 1 end if done
