# B+ Tree

A B+ tree follows a multi-level index format and is a balanced binary search tree. A B+ tree’s leaf nodes denote actual data pointers. The B+ tree ensures that all leaf nodes stay balanced at the same height. In addition, a link list connects the leaf nodes; a B+ tree can therefore allow both random access and sequential access.

## Structure of B+ Tree

Each node on the leaf is the same distance from the root node. For any B+ tree, a B+ tree is of the order n where n is fixed.

Internal nodes −

• Internal (non-leaf) nodes, except the root node, contain at least of [ n/2 ] pointers
• At most, n pointers may contain an internal nod

Leaf nodes −

You Might Be Interested In
• At least [ n/2 ] record pointers and [n/2] key values are stored in Leaf nodes.
• At most, n record pointers and n key values will contain a leaf node.
• Each node of the leaf contains a block pointer P to point to the next node of the leaf and forms a linked list.

## B+ Tree Insertion

• From the bottom, B+ trees are filled and every entry is done at the leaf node.
• If a leaf node overflows −
• Split node into two parts.
• Partition at i = ⌊(m+1)/2⌋.
• First i entries are stored in one node.
• Rest of the entries (i+1 onwards) are moved to a new node.
• ith key is duplicated at the parent of the leaf.
• if a non-leaf node overflows −
• Split node into two parts.
• Partition the node at i = ⌈(m+1)/2⌉.
• Entries up to i are kept in one node.
• Rest of the entries are moved to a new node.

## B+ Tree Deletion

• At the leaf nodes, B+ tree entries are deleted.
• The entry for the goal is searched and deleted.
• If it is an internal node, delete it from the left position and replace it with an entry.
• The underflow is tested after deletion,
• If there is an underflow, allocate the entries from the nodes left over.
• If distribution from the left is not possible, then
• Distributing right to it from the nodes.
• If distribution from the left or from the right is not feasible, then
• Merge to the left and right of the node.