ที่นี่เราจะดูวิธีการลบโหนดจาก B+ Tree สมมติว่าเรามี B+ Tree เหมือนต่ำกว่า 7 ลบ;
ตัวอย่าง B+ Tree −
การลบมีสองส่วน อันดับแรกเราต้องหาองค์ประกอบ กลยุทธ์นั้นก็เหมือนกับการสอบถาม ตอนนี้สำหรับการลบ เราต้องคำนึงถึงกฎบางอย่าง โหนดหนึ่งต้องมีองค์ประกอบอย่างน้อย m/2 ดังนั้นหากเราลบองค์ประกอบหนึ่งองค์ประกอบและองค์ประกอบเหลือน้อยกว่า m-1 มันจะปรับตัวเอง หากโหนดทั้งหมดถูกลบ โหนดย่อยจะถูกรวมเข้าด้วยกัน และหากขนาดของโหนดเท่ากับ m ให้แยกโหนดออกเป็นสองส่วน และค่ามัธยฐานจะเพิ่มขึ้นอีกครั้ง
สมมติว่าเราต้องการลบ 78 ตอนนี้มีลูกสองคน [75, 77] และ [78, 85] จากนั้นจะลบ 78 ออกจากโหนดปลายสุดก่อน จากนั้นจึงใช้ 85 และทำสำเนาของคีย์ 85 และทำให้เป็นรูทของทรีย่อย
อัลกอริทึม
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
