यहाँ हम देखेंगे कि B+ ट्री में सम्मिलन कैसे किया जाता है। मान लीजिए हमारे पास नीचे जैसा B+ ट्री है:
B+ ट्री का उदाहरण –
एक तत्व सम्मिलित करने के लिए, विचार B-ट्री के समान ही है, यदि एक तत्व सम्मिलित किया जाता है, तो उसे पत्ती नोड पर संग्रहीत किया जाएगा। यदि यह किसी आंतरिक नोड में मौजूद है, तो यह वहां भी होगा, स्वयं के दाएं बच्चे के रूप में।
मान लीजिए हम ट्री में 65 सम्मिलित करना चाहते हैं। तो यह 60 से बड़ा है, और 75 से कम है। फिर इसे मध्य उप-ट्री में सम्मिलित किया जाएगा। अब, 65, 63 के बाद नोड में सम्मिलित होगा, फिर वह नोड दो भागों में विभाजित हो जाएगा, 65 ऊपर जाएगा, और 65 उसके दाएं नोड पर भी होगा।
65 सम्मिलित करने के बाद B+ ट्री।
एल्गोरिदम
BPlusTreeInsert(root, key) –
इनपुट – ट्री की जड़, और सम्मिलित करने के लिए कुंजी
हम मान लेंगे, कि कुंजी सूची में मौजूद नहीं है
रूट नोड से शुरू करें, 'key' के रूप में कुंजी के लिए सटीक मिलान करें जब तक एक पत्ती नोड न मिल जाए। खोज पथ x₁, x₂, …, xₕ हो। x₁ पहला नोड है यानी रूट, फिर xₕ पत्ती नोड है। प्रत्येक नोड xᵢ, xᵢ₊₁ का माता-पिता है
xₕ में नया ऑब्जेक्ट सम्मिलित करें जहां कुंजी 'key' है, और मान v है
i := h
while xᵢ ओवरफ्लो करता है, do
xᵢ को दो नोड्स में विभाजित करें, बड़े आधे कुंजियों को एक नए नोड p में ले जाकर।
if xᵢ पत्ती नोड है, p को पत्ती नोड्स के बीच लिंक्ड सूची में लिंक करें।
एक कुंजी k की पहचान करें, जिसे चाइल्ड पॉइंटर के साथ पैरेंट लेवल में सम्मिलित किया जाना है जो p की ओर इंगित करता है।
k का चुनाव नोड xᵢ के प्रकार पर निर्भर करता है। यदि xᵢ पत्ती नोड है, तो हम कॉपी अप करेंगे। इसलिए p में सबसे छोटी कुंजी, पैरेंट लेवल पर k के रूप में कॉपी की जाती है। दूसरी ओर, यदि xᵢ गैर-पत्ती नोड है, तो हम पुश अप करेंगे। इसलिए p में सबसे छोटी कुंजी, पैरेंट नोड में k में कॉपी की जाएगी।
if i = 0, then
एक नया इंडेक्स नोड नई रूट के रूप में बनाएं। नई रूट में कुंजी k के साथ नोड स्टोर करें, और दो चाइल्ड xᵢ और p।
return
else
कुंजी k और p की ओर इंगित करने वाला चाइल्ड पॉइंटर, नोड xᵢ₋₁ में सम्मिलित करें।
i := i – 1
end if
done
