B+ Tree

The B-tree structure is the standard organization for indexes in a database System. There are several variations of the B-tree and the most well-known is the B+ tree. The B-tree guarantees at least 50% storage utilization. The B+ tree is a slightly different data structure which in addition to indexed access also allows sequential data processing and stores all data in the lowest level of the tree.

One of the major drawbacks of the B-tree is the difficulty of traversing the keys sequentially. B+ tree retains the rapid random access property of the B-tree, while also allowing rapid sequential access. 

In the B+ tree all keys are maintained in leaves and keys are replicated in non-leaf nodes to define paths for locating individual records. The leaves are linked together to provide a sequential path for traversing the keys in the tree.

The B+ tree is called a balanced tree because every path from the root node to a leaf node is the same length. A balanced tree means that all searches for individual values require the same number of nodes to be read from the disk.

A B+ tree of order M (where M > 3) is an M-ary tree with the following properties:

1. The data items are stored in leaves.
2. The root is either a leaf or has between two and M children.
3. The internal node stores up to M-1 keys to guide the search.
4. All nodes except the root have between ⌊ M/2 ⌋ and M children
5. A leaf has between ⌊ L/2 ⌋ and L data items. All leaves are at same depth.
6. B+ tree provides faster sequential access of data.

---

Insertion in B+ Tree

---

In order to insert a key into a B+ tree, first a B+ tree search is performed to find the correct location for the key.

1. The search operation is used to find the leaf node in which the key value of the node has to be inserted.
2. If the key value already exists in a leaf node no more insertion is needed. Else if the said key value does not exist insert the value in the leaf node in an ordered fashion.
3. When a node is split the middle key is retained in the left half-node as well as being promoted to the further.

How insertion is done is given in the following Fig 1.

---

Deletion In B+ Tree

---

1. Search the B+ tree for the key value. 
2. If the key value is in the B+ tree remove it from the tree. 
3.  When a key value is deleted from a leaf there is no need to delete the key from the index set of the key. The key value still can direct searches to proper leaves since it is still a valid separator between the keys in the nodes below.

How we delete the nodes we will see in the following Figure

Happy Exploring!