b+-tree-insertion

how insertion works in B+ Tree

tags: learning dsa database

content

When the leaf is not full

• simply adds to the leaf When the leaf is full

1. split the leaf into two halves
2. choose an appropriate value to shove to parent node
3. shove that value to parent node
4. update parent-child relation When parent node is also full in the above step 3

• break parent in halves
• bubble up the splitting process to the parent’s parents When the splitting bubbles up to root (see video in reference)
• root is split into halves
• a new root is created
• tree height grows by 1

Note

B+ Tree grows upwards at the root, instead of growing downwards at the leaves.
This is how it keeps balanced

up

• b+-tree

down

reference

• Lecture 6 Part 6