এখানে আমরা দেখব, B+ ট্রি থেকে একটি নোড ডিলিট কিভাবে করা যায়। ধরি আমাদের নিচের মতো একটি B+ ট্রি আছে 7minus;
B+ ট্রির উদাহরণ −
ডিলিশনের দুটি অংশ রয়েছে। প্রথমে উপাদানটি খুঁজে বের করতে হবে। সেই কৌশলটি কুয়েরির মত। এখন ডিলিশনের জন্য কিছু নিয়ম মেনে চলতে হবে। একটি নোডে কমপক্ষে m/2 উপাদান থাকতে হবে। তাই যদি আমরা একটি উপাদান ডিলিট করি, এবং তার কম m-1 উপাদান থাকে, তবে সেটি নিজের আপডেট করবে। যদি পুরো নোড ডিলিট হয়, তবে তার চাইল্ডগুলো মার্জ হবে, এবং যদি তাদের আকার m-এর সমান হয়, তবে সেগুলো দুটি ভাগে ভাগ হবে, এবং আবার মেডিয়ান মান উপরে যাবে।
ধরি আমরা 78 ডিলিট করতে চাই। এখন দুটি চাইল্ড আছে। [75, 77], এবং [78, 85], তাহলে এটি প্রথমে লিফ নোড থেকে 78 ডিলিট করবে, তারপর 85 নেবে, এবং কী 85-এর একটি কপি তৈরি করে সেটিকে সাবট্রির রুট করবে।
অ্যালগরিদম
BPlusTreeDelete(x, key) −
ইনপুট − ট্রির রুট, এবং ডিলিট করার কী
আমরা অনুমান করব, কীটি লিস্টে উপস্থিত আছে
রুট নোড থেকে শুরু করুন, কী হিসেবে 'key' exact match করুন যতক্ষণ না লিফ নোড। সার্চ পথ হবে x1, x2, … , xh। x1 প্রথম নোড অর্থাৎ রুট, তারপর xh লিফ নোড। প্রতিটি নোড xi হল xi+1-এর পেরেন্ট
'key' কী সহ অবজেক্টটি xh থেকে ডিলিট করুন।
যদি h = 1, তবে রিটার্ন করুন, কারণ শুধু একটি নোড আছে যা রুট।
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.
পেরেন্ট নোড xi-1-এ একটি কী k, redistribution অনুযায়ী পরিবর্তন হবে।
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
