Binary Search Tree（二叉查找树、二叉排序树、二叉搜索树）

指一棵空树或者具有下列性质的 二叉树 ：

1. 1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 2）任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 3）任意节点的左、右子树也分别为二叉查找树。
4. 4）没有键值相等的节点（no duplicate nodes）。

Balanced Binary Search Tree（平衡二叉查找树、AVL树）

1. 在AVL树中任何节点的两个 子树 的高度最大差别为一，所以它也被称为 高度平衡树 。查找、插入和删除在平均和最坏情况下都是 O （log  n ）。增加和删除可能需要通过一次或多次 树旋转 来重新平衡这个树。
2. 平衡二叉树是一个重要的数据结构，它有很均衡的插入、删除以及查询性能（时间复杂度都是O(logn)）。Linux2.4以前的内核中，虚拟内存管理中用的容器就是AVL Tree。AVL Tree对平衡的要求是比较严格的，它要求左右子数之间的长度差不能大于1。

红黑树

1. 红黑树是每个节点都带有 颜色 属性的 二叉查找树 ，颜色为 红色 或 黑色 。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

   性质1. 节点是红色或黑色。

   性质2. 根是黑色。

   性质3. 所有叶子都是黑色（叶子是NIL节点）。

   性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

   性质5. 从任一节点到其每个叶子的所有 简单路径 都包含相同数目的黑色节点。

   二叉查找树但若是一棵具有n个结点的线性链，则此些操作最坏情况运行时间为O（n），但是 红黑树，能保证在最坏情况下，基本的动态几何操作的时间均为O（lgn）。

   从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

   详细介绍可以参考： http://blog.csdn.net/v_JULY_v/article/details/6105630 等的详细介绍。

   平衡二叉树和红黑树比较：

   AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多；

   红黑是用非严格的平衡来换取增删节点时候旋转次数的降低；

   所以简单说，如果你的应用中，搜索的次数远远大于插入和删除，那么选择AVL，如果搜索，插入删除次数几乎差不多，或者插入更多，应该选择RB

B树

     是一个节点可以拥有多于2个子节点的 二叉查找树 。

1. 

   就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于 树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下 （为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用 多叉树 结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

   在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入块(block)中某数据时，首先需要定位到磁盘中的某块，如何有效地查找磁盘中的数据，需要一种合理高效的外存数据结构，就是B-tree结构。

   B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。

B＋树

      B ⁺ -tree ：是应文件系统所需而产生的一种 B-tree的变形树。

     一棵m阶的B+树和m阶的B树的异同点在于：

1.  有n棵子树的结点中含有n-1 个关键字； (与B 树n棵子树有n-1个关键字 保持一致，参照： http://en.wikipedia.org/wiki/B%2B_tree#Overview ，而下面 B+树的图可能有问题 ，请读者注意)

         2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)

         3. 所有的非终端结点可以看成是索引部分 ，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

   a) 为什么说 B ⁺ -tree 比B 树更适合实际应用中操作系统的文件索引和数据库索引？

   1) B ⁺ -tree的磁盘读写代价更低

   B ⁺ -tree 的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

   举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶 B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而 B ⁺  树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比 B ⁺  树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

   

   2) B ⁺ -tree的查询效率更加稳定

   由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

   数据库索引采用B+树的主要原因是 B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题，B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。

B ^* -tree

1. B*-tree是 B ⁺ -tree 的变体，在 B ⁺ 树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）。给出了一个简单实例，如下图所示：

   B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。

   B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针。

   所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

   现在一般主流的数据库索引一般都是用的B/B+树系列，包括MySQL及NoSQL中的MongoDB。

LSM－tree（Log Structured merge －tree）

           详细参考： http://duanple.blog.163.com/blog/static/7097176720120391321283/