এখানে আমরা দেখব, B-ট্রি থেকে একটি নোড ডিলিট কিভাবে করা যায়। ধরি আমাদের নিচের মতো একটি B-ট্রি আছে −
B-ট্রির উদাহরণ −
ডিলিশনের দুটি অংশ রয়েছে। প্রথমে উপাদানটি খুঁজে বের করতে হবে। সেই কৌশলটি কুয়েরির মত। এখন ডিলিশনের জন্য কিছু নিয়ম মেনে চলতে হবে। একটি নোডে কমপক্ষে m/2 উপাদান থাকতে হবে। তাই যদি আমরা একটি উপাদান ডিলিট করি, এবং তার কম m-1 উপাদান থাকে, তবে সেটি নিজের আপডেট করবে। যদি পুরো নোড ডিলিট হয়, তবে তার চাইল্ডগুলো মার্জ হবে, এবং যদি তাদের আকার m-এর সমান হয়, তবে সেগুলো দুটি ভাগে ভাগ হবে, এবং আবার মেডিয়ান মান উপরে যাবে।
ধরি আমরা 46 ডিলিট করতে চাই। এখন দুটি চাইল্ড আছে। [45], এবং [47, 49], তাহলে সেগুলো মার্জ হবে, হবে [45, 47, 49], এখন 47 উপরে যাবে।
অ্যালগরিদম
BTreeDelete(x, key) −
ইনপুট − ট্রির রুট, এবং ডিলিট করার কী
আমরা অনুমান করব, কীটি লিস্টে উপস্থিত আছে
if x is leaf, then
delete object with key 'key' from x
else if x does not contain the object with key 'key', then
locate the child x->child[i] whose key range is holding 'key'
y := x->child[i]
if y has m/2 elements, then
If the sibling node z immediate to the left or right of y, has at least one more
object than m/2, add one more object by moving x->key[i] from x to y, and
move that last or first object from z to x. If y is non-leaf node, then last or first
child pointer in z is also moved to y
else
any immediate sibling of y has m/2 elements, merge y with immediate sibling
end if
BTreeDelete(y, key)
else
if y that precedes 'key' in x, has at-least m/2 + 1 objects, then
find predecessor k of 'key', in the sub-tree rooted by y. then recursively delete k
from the sub-tree and replace key with k in x
else if ys has m/2 elements, then
check the child z, which is immediately follows 'key' in x
if z has at least m/2+1 elements, then
find successor k of 'key', in the sub-tree rooted by z. recursively delete k
from sub-tree, and replace key with k in x
else
both y and z has m/2 elements, then merge then into one node, and push 'key'
down to the new node as well. Recursively delete 'key' from this new node
end if
end if
