The B+ tree is almost identical to the binary search tree. It is a balanced tree where the search is directed through internal nodes. The data entries are present in the leaf nodes of the B+ tree. B+ trees support both random and sequential access since the leaf nodes are interconnected with each other through links.

STRUCTURE OF B+ TREE

The general node structure of B+ node is as follows 

• It contains up to n – 1 search-key values K₁, K₂, . . ., K_n-1, and n pointers P₁, P₂, . . ., P_n.
• The search-key values within a node are kept in sorted order; thus, if i < j, then K_i < K_j.
• To retrieve all the leaf pages efficiently we have to link them using page pointers. 
• The sequence of leaf pages is also called a sequence set.
• In a B+ tree, the tree structure tends to grow on the insertion of new records and shrinks on the deletion of existing records. Hence it is called a dynamic tree.

CHARACTERISTICS OF B+ TREE

The following are the characteristics of the B+ tree:

• The B+ tree is a balanced tree and the operations such as insertion and deletion keep the tree balanced.
• Each node, except for the root node, must be compulsorily occupied with at least 50%.
• Searching becomes so simple because traversing from the root to the relevant leaf nodes results in the record.

INSERTION OPERATION

Algorithm for Insertion:

Step 1: Find correct leaf L.

Step 2: Put data entry onto L.

• If L has enough space, done!
• If there is no space, split L (into L and a new node L2)
• Allocate a new node
• Redistribute entries evenly
• Copy up the middle key.
• Insert index entry such that it points to L2 into the parent of L.

Step 3: This can happen recursively. To split the index node, redistribute entries evenly, but push up the middle key. (Contrast with leaf splits).

Step 4: Splits “grow” tree; splitting the root increases the height. The tree grows either wider or one level taller at the top.

DELETION OPERATION

Algorithm for deletion:

Step 1: Start from the root to find the leaf node L with the entry.

Step 2: Remove the entry,

• If L is at least half-full, done!
• If L has only d-1 entries,
• Try the redistribution technique by borrowing keys from the adjacent node (sibling) with the same parent node as L.
• If a failure occurs when tried to re-distribute, merge L and sibling.

Step 3: Whenever a merge occurs, entry (pointing to L or sibling) must be deleted from the parent of L.

Step 4: Merge could pass the entries to the root, reducing the height of the tree.

MERITS OF B+ INDEX TREE STRUCTURE

1. In the B+ tree the data is stored in the leaf node so searching of any data requires scanning only of leaf node alone.

2. Data is ordered in the linked list.

3. Any record can be fetched in an equal number of disk accesses.

4. Since the leaf nodes are linked, performing range queries is easy.

5. Since keys are used for indexing, the height of the tree is less.

6. Supports both random and sequential access.

DEMERITS OF B+ INDEX TREE STRUCTURE

1. Extra insertion of non-leaf nodes.

2. There is space overhead.