AVL tree, Splay tree, B-tree

An AVL tree is identiacal to a binary search tree, except that for every
node in the, the height of the left and right subtree can differ by at most
1.
The basic idea of the splay tree is that after a node is accessed, it is
pushed to the root by a series of AVL tree rotation. By restructuring we can
make future accesses cheaper on all these nodes.
A B-tree of order m is a tree with the following structural propertires:
The root is either a leaf or has between 2 and m children.
All non-leaf nodes (except the root) have between [m/2] and m children.
All leaves are at the same depth.