If I want to delete 19 and 20 from the B+ Tree.
After deleting 19 and 20 from the B+ Tree.
Redistribution and merging is required here because
The left pointer of 24 is pointing to 20 but not 19. That's why redistribution is required for 20 but not 19.
These are the properties that will help you out Doing Above Procedure.
Properties of B+ Tree.
-
All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
-
All the leaves are in same depth, and here d = 2.
- Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.
- All the data pointers are contained in leaf nodes.
- All elements should be contained in leaf nodes.
- There should be between
d
to 2*d
keys at node except possibly the root.
- There should be between
d + 1
to 2*d + 1
child pointers.