*989*

Table of Contents

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 −**

- 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.