ที่นี่เราจะดูวิธีการแทรกลงใน B-Tree สมมติว่าเรามี B-Tree ด้านล่าง −
ตัวอย่าง B-Tree −
ในการแทรกองค์ประกอบ แนวคิดจะคล้ายกับ BST มาก แต่เราต้องปฏิบัติตามกฎบางประการ แต่ละโหนดมีลูก m และองค์ประกอบ m-1 หากเราแทรกองค์ประกอบลงในโหนดเดียว มีสองสถานการณ์ หากโหนดมีองค์ประกอบน้อยกว่า m-1 องค์ประกอบใหม่จะถูกแทรกลงในโหนดโดยตรง หากมีองค์ประกอบ m-1 แล้ว โดยนำองค์ประกอบทั้งหมดและองค์ประกอบที่จะแทรก แล้วนำค่ามัธยฐานขององค์ประกอบเหล่านั้น และค่ามัธยฐานจะถูกส่งไปยังรูทของโหนดนั้นโดยดำเนินการตามเกณฑ์เดียวกัน แล้วสร้างสองรายการ แยกรายการจากครึ่งซ้ายและครึ่งขวาของโหนด
สมมติว่าเราต้องการแทรก 79 เข้าไปในต้นไม้ ตอนแรกจะตรวจสอบด้วย root ซึ่งมีค่ามากกว่า 56 จากนั้นจะเข้าสู่แผนผังย่อยด้านขวาสุด ตอนนี้มันน้อยกว่า 81 ดังนั้นให้ย้ายไปที่ทรีย่อยทางซ้าย หลังจากนั้นก็จะถูกแทรกเข้าไปในรูท ตอนนี้มีสามองค์ประกอบ [66, 78, 79] ค่ามัธยฐานคือ 78 ดังนั้น 78 จะเพิ่มขึ้น และโหนดรากจะกลายเป็น [79, 81] และองค์ประกอบของโหนดจะถูกแบ่งออกเป็นสองโหนด คนหนึ่งถือ 66 และอีกคนถือ 79
B-Tree หลังจากใส่ 79.
อัลกอริทึม
BTreeInsert(root, key)−
ป้อนข้อมูล − รูทของต้นไม้และคีย์ที่จะแทรก เราจะถือว่าไม่มีคีย์อยู่ในรายการ
x := Read root if x is full, then y := new node z := new node Locate the middle object oi, stored in x, move the objects to the left of oi in to node y Move the object to the right of oi into node z. If x is an index node, then move the child pointers accordingly x->child[1] := address of y x->child[2] := address of z end if
