7.4B+ tree insertion and deletion
The idea
B+ tree insertion places the key in a leaf and splits upwards if a node overflows. In a leaf split the middle key is copied up; in an internal split it is moved up.
Think of it like this: A filing cabinet drawer that splits in two when full, with a new label added above it.
Why it exists
GATE gives keys and asks for the shape, the height or the number of splits.
How it works
- Find the leaf and insert the key in sorted order.
- If the leaf has more than the maximum, split it into two halves; copy the first key of the right half to the parent.
- If the parent overflows, split it and move the middle key up.
- A split of the root creates a new root (height + 1).
Worked example: Keys 10, 20, 30 into a tree with at most 2 keys per node.
Inserting 30 overflows the leaf [10, 20, 30]: it splits into [10, 20] and [30], and 30 is copied up as the root.
Now play with it
- →Press Next step through the textbook example.
- →Change the maximum keys to 3 and compare the height.
Press Next step to insert the first key.
- insert 10
- insert 20
- insert 30 (leaf split, 30 is copied up); new root
- insert 5
- insert 15 (internal split, 20 is moved up); new root
- insert 25
- insert 35
- insert 40
- insert 3
Leaf split: the middle key is copied up (it stays in a leaf). Internal split: the middle key is moved up. All data keys live in the leaves.
Check yourself
When an internal node of a B+ tree splits, the middle key
Exam notes (the dense version)
Insert into the correct leaf. If it overflows, split: a leaf split copies the middle key up; an internal split moves it up; splits can cascade and grow a new root (height + 1). Delete: remove from the leaf; if it underflows, borrow from a sibling or merge with it, and fix the parent. Insertion and deletion take O(log n). Leaves are linked, so a range query walks the leaf list.
Previous year questions: File Organisation & Indexing (9)
PYQs are grouped by topic, so this is the full set for File Organisation & Indexing; try the ones that match this subtopic. Open all 9 on the topic page.