b_book1.gif (162 bytes)Data - Structures (Tree)

B+-tree: Deleting records

Assuming a Bktfr = 4 . The minimum number in each node (root or leaf) = Bktfr/2 = 2.

 

Example
A. If the leaf has more than the minimum number of records (2)
  • Delete the record
  • Leave the parent as is

[79 102]

[60 63 66] [ 79 83]  [102 110 115 160]

Delete 102

[ 79 102 ]

[ 60 63 66 ]  [ 79 83 ]  [ 110 115 160 ]
B. If the leaf has less than or equal the minimum number of records (2), check the adjacent siblings
  • 1. If one has more than the minimum
    • a. share the record between both
    • b. change the key in the parent
      (if both have more than the minimum and the same number, use the LHS.)

[79 102]

[ 60 63 66]  [  79 83 ]  [ 110 115 160 ]

Delete 83

[ 66 102 ]

[ 60 63]  [ 66 79 ]  [ 110 115 160]
  • 2. If neither has more than the minimum
    • a. combine the sparse leaf with one of the siblings, choose the LHS if there is one
    • b. delete a key from the parent node

[66 102]

[ 60 63]  [ 66 79 ]  [ 110 115 ]

Delete 79

[ 102 ]

[ 60 63 66]  [ 110 115 ]

[Rev 17/03/99] 14/3/99 © 1999 V/2-Com (Verhaart), P O Box 8415, Havelock North, New Zealand.