B+ Trees are balanced search trees commonly used in databases and file systems. Unlike regular B-trees, all data is stored in leaf nodes, while internal nodes contain only keys for navigation. The key properties include: all leaves are at the same level, internal nodes store keys only, leaf nodes store key-value pairs, and leaves are linked together for efficient range queries.
The first step in B+ tree insertion is finding the correct leaf node. We start at the root and compare our key with the keys in each node. For inserting key 6, we start at the root with keys 10 and 20. Since 6 is less than 10, we follow the left pointer to the internal node with key 5. Since 6 is greater than 5, we follow the right pointer to reach the target leaf node containing keys 5 and 7.
Once we find the target leaf node, we insert the new key while maintaining sorted order. In our example, we insert key 6 into the leaf containing 5 and 7, resulting in 5, 6, 7. If this causes the node to exceed its maximum capacity, we must split it. We keep approximately half the keys in the original node and move the rest to a new node. Then we promote a copy of the smallest key from the new node up to the parent level.
After splitting a leaf node, we must update the parent internal node. The promoted key from the leaf split is inserted into the parent node, and a new pointer is added to reference the newly created leaf node. If the parent node becomes full after this insertion, it must also be split. This process continues recursively up the tree until we reach a node with available space or until we need to create a new root.
To summarize B+ tree insertion: we find the target leaf through tree traversal, insert the key while maintaining order, handle overflows by splitting nodes and promoting keys upward, and ensure the tree remains balanced. This process guarantees efficient search and range query operations while maintaining the fundamental B+ tree properties.