Trees Flashcards
Structure of a B+ Tree?
Internal Nodes:
- Internal nodes contain more keys and no pointer records
- Internal Structure: P1, K1, … PN-1, KN-1, PN
Leaf Nodes:
- Leaf nodes have key values plus pointers to record data
- Leaf nodes have pointer to next leaf node
- Every item MUST be in leaf node.
- Keys can appear in internal node AND leaf node
- Leaf structure K1, Pr1, … Km-1, Pr m-1, P (next)
B+ Tree Insertion algorithm
1 Descend to the leaf where the key fits.
2 If the node has an empty space, insert the key/reference pair into the node.
3 If the node is already full, split it into two nodes, distributing the keys evenly between the two nodes.
4 If the node is a leaf, take a copy of the minimum value in the second of these two nodes and repeat this insertion algorithm to insert it into the parent node.
5 If the node is a non-leaf, exclude the middle value during the split and repeat this insertion algorithm to insert this excluded value into the parent node.
B+ Tree Deletion algorithm
1 Descend to the leaf where the key exists.
2 Remove the required key and associated reference from the node.
3 If the node still has enough keys and references to satisfy the invariants, stop.
4 If the node has too few keys to satisfy the invariants, but its next oldest or next youngest sibling at the same level has more than necessary, distribute the keys between this node and the neighbor.
5 Repair the keys in the level above to represent that these nodes now have a different “split point”
6 if node and immediate siblings have too few keys to satisfy invariant, merge node with sibling
7 if the node is a non-leaf, we will need to incorporate the “split key” from the parent into our merging.
8 repeat the removal algorithm on the parent node to remove the “split key” that previously separated these merged nodes
9 if the parent is the root and we are removing the final key from the root, in which case the merged node becomes the new root (and the tree has become one level shorter than before).
