红黑树rbtree 二叉排序树
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树，因此，红黑树在很多地方都有应用。
在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
Trie树
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
B-树
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树，其定义如下：
一棵m阶的B-树满足下列条件：
⑴ 树中每个结点至多有m个孩子；
⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；
⑶ 若根结点不是叶子结点，则至少有2个孩子；
⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；
⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字。
B树索引是数据库中存取和查找文件(称为记录或键值)的一种方法。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。
典型例子就是硬盘中的结点。与内存相比，硬盘必须花成倍的时间来存取一个数据元素，这是因为硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。
B+树
B+树可以看作是B树的变形，对于存放在外存贮器上的字典，B+树比B树更为常用。
一个m阶的B+树满足下列条件∶
(1) 每个结点至多有m棵子树。
(2) 除根结点外，其它每个分支至少有m/2棵子树。
(3) 非叶结点的根结点至少有两棵子树。
(4) 有n棵子树的结点有n个关键码，叶结点中至少包含n/2个关键码。
(5) 叶结点都在同一层中，其中存放数据文件中记录的关键码及指向该记录的指针，或存放数据文件分块后每块的最大关键码及指向该块的指针。叶结点按关键码值大小顺序链接。可以把每个叶结点看成是一个基本索引块(直接指向数据文件中的记录)。
(6) 所有分支结点可看成是索引的索引。使结点中仅包含它的各个子结点中最大(或最小)关键码的分界值及指向子结点的指针。
通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。