3
$\begingroup$

My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:

1- First navigate to the leaf *L* where it belongs.
2- If the *L* is at least half full if you can simply delete it.
3- If it contains d-1 elements then you need to redistribute and merge.

If you see the below image, here I want to delete 19 and 20 from the B+ Tree.

enter image description here

After deleting 19 and 20 from the B+ Tree.

enter image description here

Question:

I am confused why the redistribution and merging is required here at all? If you just simply delete 19 and 20 from the leaf nodes without any distribution it should work right? Why redistribution is performed here? Could anyone explain?

Is it because the left pointer of 24 is pointing to 20 but no 19. Thats why redistribution is required for 20 but not 19.

Improve this question
$\endgroup$
2
  • $\begingroup$ B-trees are documented in many places on the web and in standard textbooks. Have you checked those resources? $\endgroup$
    – D.W. ♦
    Dec 6, 2015 at 5:10
  • $\begingroup$ @D.W. B+-trees are less standard and may only be available in database books which may not exhibit the concepts as clearly as an algorithms texbook would. (Guessing here, I haven't actually read a database book.) $\endgroup$
    – Raphael ♦
    Jan 5, 2016 at 10:02

1 Answer 1

Reset to default
5
$\begingroup$

Okay I understood the issue.

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.

In the B+ Tree given below, each node has 2 and 2*2 data entries except possible the root. Each node has a mininum of 2 keys.

Only root of the B+ Tree can only fewer than d keys, its the only exception we have.

In my question, when you remove 19, the property of B+ Tree is not violated but when you remove 20, the total number of elements contained in the node is less than d. Hence redistribution and merging have to be performed so that the property of B+ tree is not violated.

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.