यहाँ हम देखेंगे कि B-ट्री में सम्मिलन कैसे किया जाता है। मान लीजिए हमारे पास नीचे जैसा B-ट्री है:
B-ट्री का उदाहरण –
एक तत्व सम्मिलित करने के लिए, विचार BST के समान ही है, लेकिन हमें कुछ नियमों का पालन करना होगा। प्रत्येक नोड में m बच्चे, और m-1 तत्व होते हैं। यदि हम एक तत्व को एक नोड में सम्मिलित करते हैं, तो दो स्थितियाँ होती हैं। यदि नोड में तत्व m-1 से कम हैं, तो नया तत्व सीधे नोड में सम्मिलित किया जाएगा। यदि इसमें m-1 तत्व हैं, तो सभी तत्वों को लेते हुए, और वह तत्व जो सम्मिलित किया जाएगा, फिर उनमें से माध्यिका (median) लें, और माध्यिका मान को उस नोड की जड़ में भेजें उसी मानदंड को करके, फिर नोड के बाएं आधे और दाएं आधे से दो अलग-अलग सूचियाँ बनाएं।
मान लीजिए हम ट्री में 79 सम्मिलित करना चाहते हैं। सबसे पहले इसकी जांच रूट से की जाएगी, यह 56 से बड़ा है। फिर यह सबसे दाएं उप-ट्री में आएगा। अब यह 81 से कम है, तो बाएं उप-ट्री पर जाएं। उसके बाद इसे रूट में सम्मिलित किया जाएगा। अब तीन तत्व [66, 78, 79] हैं। माध्यिका मान 78 है, इसलिए 78 ऊपर जाएगा, और रूट नोड [79, 81] बन जाएगा, और नोड के तत्व दो नोड्स में विभाजित हो जाएंगे। एक 66 रखेगा, और दूसरा 79 रखेगा।
79 सम्मिलित करने के बाद B-ट्री।
एल्गोरिदम
BTreeInsert(root, key)–
इनपुट – ट्री की जड़, और सम्मिलित करने के लिए कुंजी हम मान लेंगे, कि कुंजी सूची में मौजूद नहीं है
x := रूट पढ़ें
if x भरा हुआ है, then
y := नया नोड
z := नया नोड
x में संग्रहीत मध्य ऑब्जेक्ट oi का पता लगाएं, oi के बाएं ऑब्जेक्ट्स को नोड y में ले जाएं
oi के दाएं ऑब्जेक्ट्स को नोड z में ले जाएं।
यदि x एक इंडेक्स नोड है, तो चाइल्ड पॉइंटर्स को तदनुसार ले जाएं
x->child[1] := y का पता
x->child[2] := z का पता
end if
