B+ Tree Deletion
Case 1: Simple Deletion Delete from leaf with enough entries remaining.
Example: Delete 17 from [10, 12, 17] → Result: [10, 12]
Case 2: Underflow - Borrow from Sibling When leaf has too few entries, borrow from adjacent sibling.
Example: Before: [5] [10, 12, 15] [20, 25] Delete 5: [empty] [10, 12, 15] [20, 25] Borrow from right: [10] [12, 15] [20, 25] Update parent separator from 10 to 12
Case 3: Underflow - Merge with Sibling When borrowing isn't possible, merge nodes.
Example: Before: [5, 7] [12] [20, 25]
Delete 12: [5, 7] [empty] [20, 25] Merge: [5, 7, 20, 25]
Handling Non-Unique Keys
Problem: Multiple records with same search key value
Solution 1: Make keys unique Add record ID to make composite key: (department, record_ID)
Solution 2: Bucket approach Store all pointers for same key together:
Physics → [pointer1, pointer2, pointer3, ...]
B+ Tree File Organization
Instead of storing pointers in leaves, store actual records.
Advantages:
-
No pointer following needed
-
Data automatically sorted
-
Efficient range queries
Example:
Leaf 1: [Student 1001][Student 1005][Student 1008]
Leaf 2: [Student 1012][Student 1015][Student 1020]