কম্পিউটার

ডেটা স্ট্রাকচারে B+ ট্রি মুছে ফেলা


এখানে আমরা দেখব, কিভাবে B+ Tree থেকে একটি নোড ডিলিট করা যায়। ধরুন আমাদের একটি B+ বৃক্ষ আছে যেমন 7 মাইনাসের নিচে;

B+ গাছের উদাহরণ

ডেটা স্ট্রাকচারে B+ ট্রি মুছে ফেলা

মুছে ফেলার দুটি অংশ আছে। প্রথমে আমাদের উপাদানটি খুঁজে বের করতে হবে। সেই কৌশলটি প্রশ্ন করার মতো। এখন মুছে ফেলার জন্য, আমাদের কিছু নিয়মের যত্ন নিতে হবে। একটি নোডে কমপক্ষে m/2 উপাদান থাকতে হবে। সুতরাং যদি আমরা মুছে ফেলি, একটি উপাদান, এবং এটিতে m-1 এর কম উপাদান অবশিষ্ট থাকে, তাহলে এটি নিজেকে সামঞ্জস্য করবে। যদি পুরো নোডটি মুছে ফেলা হয়, তাহলে এর বাচ্চাদের একত্রিত করা হবে, এবং যদি তাদের আকার m এর মতো হয়, তাহলে তাদের দুটি অংশে বিভক্ত করুন, এবং আবার মধ্যম মান বেড়ে যাবে।

ধরুন আমরা 78 ডিলিট করতে চাই। এখন দুটি বাচ্চা আছে। [75, 77], এবং [78, 85], তারপর এটি প্রথমে লিফ নোড থেকে 78 মুছে ফেলবে, তারপরে 85 নেবে এবং কী 85-এর একটি অনুলিপি তৈরি করবে এবং এটিকে সাবট্রির মূল হিসাবে তৈরি করবে।

ডেটা স্ট্রাকচারে B+ ট্রি মুছে ফেলা

অ্যালগরিদম

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

  1. ডেটা স্ট্রাকচারে B+ গাছ

  2. ডেটা স্ট্রাকচারে ইন্টারভাল হিপস

  3. ডাটা স্ট্রাকচারে বাইনারি ট্রি এডিটি

  4. ডাটা স্ট্রাকচারে ভার্চুয়াল ট্রিতে খেলা