Question

Database Management System

State the algorithms that apply for hanging nodes in a B+ Tree and tell me how they are different from the B Tree algorithms for hanging new nodes.

Answer 1

1. If node is not full add the record.
2. else split the bucket.
a. Insert the new leaf and move half the bucket’s elements to the new bucket.
b. Insert the new leaf’s smallest key and address into the parent.
c. If the parent is full, split the parent.
i. Add middle key to parent node.
d. Repeat until a parent is found that doesn't need to split.
3. If the root splits, create a new root which has one key and two pointers.

Unlike the B Tree insert node algorithm, B+ tree insert algorithm insert the new node only as a leaf node. But B tree algorithms can insert node as interior nodes.