23 tree
Idea: 


Advantages: 

Variations: 

Structure and balancing
In a 23 tree, every node stores either 1 or 2 keys and has either 2 or 3 children, respectively (unless it is a leaf). We call them accordingly, 2nodes and 3nodes:
All leaves must have the same depth  they have to be at the same level. This is achieved by splitting nodes that overflow and joining nodes that underflow.
Consequently, a 23 tree of height \(h\) stores at least \(2^h1\) keys (if all nodes are 2nodes) and at most \((3^h1)/2\) keys (if all nodes are 3nodes). This implies height between \(\log_3 (2n+1)\approx 0.631\log_2 n\) and \(\log_2(n+1)\).
Insertion
When we insert a new key into a 2node, we just get a 3node, which is OK.
However, when we insert a key into a 3node, it overflows and we need to split it:
The procedure continues by inserting \(y\) to the parent node. This may start a cascade of overflown 3nodes which ends either when the parent has enough capacity or we get to the top of the tree and create a new root (at this point the height of the whole tree increases by 1).
Deletion
Assume we are deleting a key from leaf. (If not, we replace the key by its successor, which is in a leaf  the same trick we used in BST). When we delete from a 3node, we just get a 2node, which is OK.
A problem occurs, when deleting from a 2node which only has a single key, so after deletion, the node is empty and this is not allowed. There are two cases:
If a sibling next to it is a 3node, we can borrow a key from it:
Otherwise the adjacent sibling is a 2node. We join it with a key from the parent node and recursively deal with deleting from the parent node (this may start a cascade of joins):
Thus, the entire delete
operation may involve a series of joins. It ends either with a share, or with join when parent is a 3node, or continues all the way up to the root. In that case the final join deletes root and height of the tree decreases by 1.