几种树
二叉搜索树(基础) ==> AVL(需要左右旋以保持平衡) ==> B/B+(多叉树,自平衡) ==> 红黑树(平衡)
B 树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。 阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数 http://www.cnblogs.com/nullzx/p/8729425.html 一颗m阶的B树定义如下：
1）每个结点最多有m-1个关键字。
2）根结点最少可以只有1个关键字。
3）非根结点至少有Math.ceil(m/2)-1个关键字。
4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。 在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小
B+树是对B树的一种变形树，它与B树的差异在于：
- 有k个子结点的结点必然有k个关键码；
- 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
- 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+ 树的优点在于：
- 由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
- B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
我们计算机的主存基本都是随机访问存储器(Random-Access Memory，RAM)，他分为两类：静态随机访问存储器（SRAM）和动态随机访问存储器（DRAM）。SRAM比DRAM快，但是也贵的多，一般作为CPU的高速缓存，DRAM通常作为内存。这类存储器他们的结构和存储原理比较复杂，基本是使用电信号来保存信息的，不存在机器操作，所以访问速度非常快
对磁盘的访问时间分为 寻道时间，旋转时间，以及传送时间. 页大小通常为4K 所以B及B+树比较适合与文件系统的数据结构. 一个节点就是一页．B/B+树也经常用做数据库的索引 此时B树中的key就表示键，而data表示了这个键对应的条目在硬盘上的逻辑地址
文件系统和数据库系统中常用的B/B+ 树，他通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中，如：
- Windows：HPFS文件系统
- Mac：HFS，HFS+文件系统
- Linux：ResiserFS，XFS，Ext3FS，JFS文件系统
- 数据库：ORACLE，MYSQL，SQLSERVER等中
B树的插入
2-3树指节点最多有两个key, 三个子节点 如果插入节点之后为三个key, 且父节点只有一个key, 则提升中间的key, 若父节点有两个key, 则不断向上递归提升中间的key
B树的删除
先看本节点的关键字是否个数足够 再看兄弟节点. 若兄弟有,则父节点匀给本节点,兄弟节点匀给父节点 最后看父节点.父节点给本节点,合并本节点和兄弟节点
1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。
3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。
否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。
B+树的插入和删除
插入
分割的左右子树不平均. 索引节点(父节点关键字)的值为右子树最左的值
删除
- 对于叶子节点, 三种方式,和B树不同的是要更新父节点的值或删除父节点的值,而不是下移
- 对于上移到索引节点时,和B树一样
注意，通过B+树的删除操作后，索引结点中存在的key，不一定在叶子结点中存在对应的记录。
红黑树
自平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题