ที่นี่เราจะดูวิธีการแทรกลงใน B+ Tree สมมติว่าเรามี B+ Tree อยู่ด้านล่าง −
ตัวอย่าง B+ Tree −
ในการแทรกองค์ประกอบ แนวคิดจะคล้ายกับ B-Tree มาก หากองค์ประกอบหนึ่งถูกแทรก สิ่งนั้นจะถูกเก็บไว้ที่โหนดปลายสุด หากสิ่งนั้นมีอยู่ในโหนดภายใน โหนดนั้นจะอยู่ที่นั่นที่ส่วนปลายของตัวมันเอง
สมมติว่าเราต้องการแทรก 65 เข้าไปในต้นไม้ นั่นคือมากกว่า 60 และน้อยกว่า 75 จากนั้นจะถูกแทรกลงในทรีย่อยตรงกลาง ตอนนี้ 65 จะถูกแทรกเข้าไปในโหนดหลังจาก 63 จากนั้นโหนดนั้นจะถูกแบ่งออกเป็นสองส่วน 65 จะขึ้นไปและ 65 จะอยู่ที่นั่นที่โหนดด้านขวาของมันด้วย
B+ ต้นไม้หลังจากแทรก 65.
อัลกอริทึม
BPlusTreeInsert(รูท, คีย์) −
ป้อนข้อมูล − รากของต้นไม้และกุญแจที่จะแทรก
We will assume, that the key is not 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 Insert the new object where key is ‘key’, and value is v into xh. i := h while xi overflows, do divide xi into two nodes, by moving the larger half of the keys into a new node p. if xi is leaf node, link p into the linked list among leaf nodes. identify a key k, to be inserted into the parent level along with child pointer pointing p. The choice of k depends on the type of the node xi. If xi is leaf node, we will perform copy up. So smallest key in p, is copied as k to the parent level. On the other hand, if xi is non-leaf node, then we will perform push up. So smallest key in p, will be copied into k, in the parent node. if i = 0, then create a new index node as the new root. In the new root store node with key k, and two child xi and p. return else insert a key k and a child pointer pointing to p, into node xi-1. i := i – 1 end if done
