# B+ tree Index Files

A B^{+} tree is a balanced binary search tree that follows a multi-level index format. The leaf nodes of a B^{+} tree denote actual data pointers. B^{+} tree ensures that all leaf nodes remain at the same height, thus balanced. Additionally, the leaf nodes are linked using a link list; therefore, a B^{+} tree can support random access as well as sequential access.

### Structure of B^{+} Tree

Every leaf node is at equal distance from the root node. A B^{+} tree is of the order **n** where **n**is fixed for every B^{+} tree.

**Internal nodes** −

- Internal (non-leaf) nodes contain at least ⌈n/2⌉ pointers, except the root node.
- At most, an internal node can contain
**n**pointers.

**Leaf nodes** −

- Leaf nodes contain at least ⌈n/2⌉ record pointers and ⌈n/2⌉ key values.
- At most, a leaf node can contain
**n**record pointers and**n**key values. - Every leaf node contains one block pointer
**P**to point to next leaf node and forms a linked list.

### B^{+} Tree Insertion

- B
^{+}trees are filled from bottom and each 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.
**i**key is duplicated at the parent of the leaf.^{th}

- 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

- B
^{+}tree entries are deleted at the leaf nodes. - The target entry is searched and deleted.
- If it is an internal node, delete and replace with the entry from the left position.

- After deletion, underflow is tested,
- If underflow occurs, distribute the entries from the nodes left to it.

- If distribution is not possible from left, then
- Distribute from the nodes right to it.

- If distribution is not possible from left or from right, then
- Merge the node with left and right to it.