Skip to content

Operations On B+ Trees

Insertion

  • Search the leaf nodes for the correct place to put the new value (logarthmically complex process).
  • If there's a vacant slot in the node, place it there.
  • If there's no vacant slot in the node, break it into two nodes.
  • Insert the left-most value of the new node in the parent.
  • Repeat this process till you get to the root.
  • If the tree is full, make a new layer (at the top).

Deletion

  • Remove the value from the leaf layer
  • If the size of the node falls below half, merge it with the previous node
  • Propagate changes upwards accordingly