B tree

B+ tree data structures are the data structures most commonly found in databases and filesystems implementation. B+ enables amortized constant inserts and deletes.
B+ idea is that an inner node can have a variable number of sons within some pre-defined range. This leads to the relativly rear re-balancing of the tree, on contrary with AVL tree. The lower and upper watermarks are set ahead as for example, in B2-3 trees, where each node can have 2 or 3 sons.

Illegal state defined to be the state in which an inner node has illegal number of sons.

Inner node structures:
Each inner node has a separation values which divide between its sub-trees. For example, if some inner node has 3 sons (sub-trees) then it must have 2 separation values a1 and a2. All values less than a1 will be in the leftmost sub-tree, values between a1 and a2 will be found in the middle sub-tree, values greater than a2 will be in rightmost sub-tree.

Deletes:
If no inner node is in illegale state as a result of delete then finish.
If some inner node is in illegale state then one of two possible scenarios is true:

• Its "brother" (the son of the same parent node) can transfer one of its sons to it and return it into a legal state. In that case, after updating separation values in parent and two sons the operation ends.
• Its brother is on the lower bound too. In that case both these nodes are merged into one (with a number of sons on a upper bound) and the action is transferred to parent node, since now it lost one of its sons.
  

The action proceeds while either some node stays in legall state after delete or the root has one son, in which case its deleted.

Inserts:
If no inner node is in illegale state as a result of insert then finish
If some node has more than upper bound sons then split it into two nodes, each one with lower bound sons. And proceed the action recursivly in parent node.
The action stops when either a node is in legal state or root is split into two nodes and new root is inserted.

Searches:
Search is performed by following separation values to the tree leaves.

Notes:

• The root of the tree is a special node which can have from 2 to upper bound sons.
• Tarjan? has proved that amortized number of splits/merges is 2.