B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于
走右结点；
B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键
字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点
中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率
从1/2提高到2/3；
B树：
B树就是二叉搜索树，BST，但是，这个不能保证平衡性
AVL树：
AVL树就是平衡二叉树，是在二叉搜索树也就是B树的基础上，加了平衡的特性（也就是当高度之差大于1的时候，旋转），形成了AVL树
红黑树：
Red-Black Tree，红黑树，最主要的就是五个性质，当不满足性质的时候，则需要进行旋转
1、每个节点，要么是红要么是黑
2、根节点是黑的
3、每个叶节点，即空节点时黑的
4、如果一个节点时红的，那么他两个儿子都是黑的
5、对每一个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点（这个是最重要的性质，这个性质和第一性质，可以推断出，最长的树，比最短的树，多一半的结点，这样就几乎保持了树的平衡性）
Treap树：
树堆，
treap的结点排列成让关键字遵循二叉查找树性质，并且优先级遵循最小堆顺序性质：
1.如果v是u的左孩子，则key[v] < key[u].
2.如果v是u的右孩子，则key[v] > key[u].
3.如果v是u的孩子，则priority[v] > priority[u].
Trie树：
字典树，节省空间，复用
splay树：
伸展树，搜狗拼音，常使用的字就会出现在最上面，二八原则，百分之80的人只使用百分之20的资源。
原文：http://www.cnblogs.com/Study02/p/5203037.html