यहाँ हम देखेंगे कि B+ ट्री से नोड को कैसे हटाया जाता है। मान लीजिए हमारे पास नीचे जैसा B+ ट्री है:
B+ ट्री का उदाहरण –
विलोपन के दो भाग हैं। सबसे पहले हमें तत्व ढूंढना होगा। वह रणनीति क्वेरी करने जैसी है। अब विलोपन के लिए, हमें कुछ नियमों का ध्यान रखना होगा। एक नोड में कम से कम m/2 तत्व होने चाहिए। इसलिए यदि हम एक तत्व हटाते हैं, और इसमें m-1 से कम तत्व शेष रहते हैं, तो यह स्वयं को समायोजित करेगा। यदि पूरा नोड हटा दिया जाता है, तो उसके बच्चों को मर्ज किया जाएगा, और यदि उनका आकार m के समान है, तो उन्हें दो भागों में विभाजित किया जाएगा, और फिर से माध्यिका मान ऊपर जाएगा।
मान लीजिए हम 78 को हटाना चाहते हैं। अब दो बच्चे हैं। [75, 77], और [78, 85], फिर यह पहले पत्ती नोड से 78 को हटाएगा, उसके बाद 85 लेगा, और कुंजी 85 की एक प्रति बनाएगा, और इसे उपट्री की जड़ बना देगा।
एल्गोरिदम
BPlusTreeDelete(x, key) –
इनपुट – ट्री की जड़, और हटाने के लिए कुंजी
हम मान लेंगे, कि कुंजी सूची में मौजूद है
रूट नोड से शुरू करें, 'key' के रूप में कुंजी के लिए सटीक मिलान करें जब तक एक पत्ती नोड न मिल जाए। खोज पथ x₁, x₂, …, xₕ हो। x₁ पहला नोड है यानी रूट, फिर xₕ पत्ती नोड है। प्रत्येक नोड xᵢ, xᵢ₊₁ का माता-पिता है
xₕ से ऑब्जेक्ट को हटाएं जहां कुंजी 'key' है
if h = 1, then return, क्योंकि केवल एक नोड है जो रूट है
i := h
while xᵢ अंडरफ्लो करता है, do
if xᵢ का तत्काल सहोदर नोड s, में कम से कम m/2 + 1 तत्व हैं, then
s और xᵢ के बीच प्रविष्टियों को समान रूप से पुनर्वितरित करें।
पुनर्वितरण के अनुरूप, पैरेंट नोड xᵢ₋₁ में एक कुंजी k, बदल जाएगी।
if xᵢ गैर-पत्ती नोड है, then
k को xᵢ तक नीचे खींचा जाता है। और s से एक कुंजी को k के स्थान को भरने के लिए ऊपर धकेला जाता है
else
k को केवल s में एक कुंजी द्वारा प्रतिस्थापित किया जाता है
return
else
xᵢ को सहोदर नोड s के साथ मर्ज करें। xᵢ₋₁ में संबंधित चाइल्ड पॉइंटर हटाएं।
if xᵢ आंतरिक नोड है, then
xᵢ₋₁ में कुंजी को खींचें। जो पहले xᵢ और s को विभाजित करता था। नए नोड में
xᵢ और s, नए नोड xᵢ में।
else
xᵢ₋₁ में उस कुंजी को हटाएं।
i := i – 1
end if
done
