一、什么是 B-树和B+树？
B树即B-树
一个m阶（它的每个节点最多包含m个孩子，m就是B树的阶）的B树具有以下特征：
1. 根节点至少含有两个子女。
2. 每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <=m。
3. 每个叶子节点都包含k-1个元素，其中m/2 <= k <= m。
4. 所有的叶子节点都位于同一层，叶子节点不包含任何关键信息。
5. 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。
B+树
一个m阶的B+树具有以下特征：
1. 有k个子树的中间节点包含有k个元素（B树是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点中。
2. 所有的叶子节点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。（链表）
3. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。
4. B+树查找时是自上向下查找，B-树是从下向上查找（中序遍历）。
需要注意的是：根节点的最大元素就是整个B+树的最大元素，以后无论插入删除多少元素，始终要保持最大元素在根节点中。每个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。
二、B-树
1）B-树概述
B- 树是一种能够高效解决较大的、存放在外存储器上的文件的一种数据结构。
B-树是多路平衡查找树，它是一种特殊的多叉树，适合在磁盘等直接存取设备上组织动态的查找表。
在文件系统中，B-树已经成为索引文件的一种有效结构。
2）B-树定义
一颗m阶(m≥3)B-树，或为空树，或为满足下列特征的m叉树。
树中每个结点至多有m棵子树（分支）
若根节点不是叶子结点，则至少有2棵子树（分支）
所有的非终端结点中包含下列信息：(n,P0,K1,P1,K2,P2,...,Kn,Pn)
Ki ( 1 ≤ i ≤ n ) 为关键字，且Ki ＜ Ki+1 （每个结点关键字有序，从小大大）
Pj ( 1 ≤ j ≤ n ) 为指向子树根节点的指针，且Pj所指子树中所有结点的关键字值均小于Kj+1，Pn所指子树中所有结点的关键字值均大于Kn （例如：P0的子树的所有关键，都比K1小）
n ( ⌈m/2⌉-1 ≤ n ≤ m-1) 为关键字个数 ， 3阶关键字个数 1≤n≤2 ， 5阶关键字个数 2≤n≤4 (每一个子树都是通过分裂获得的，分裂出来子树结点个数，必然是一半减一 ⌈m/2⌉-1 )
每一个结点有n个关键字，必然包含 n + 1 为子树。
除根节点之外所有的非终端结点至少有 ⌈ m/2 ⌉ 棵子树（分支），即每个非根节点至少应有 ⌈ m/2 ⌉ -1个关键字
所有的叶子结点都出现在同一层次上，并且不带信息。
3阶B-树示意图如下：
4阶B-树示意图如下：
3）相关类
B-树中的结点类：
class Node<T> { //B-树结点 public int keyNum; //关键字个数域 public boolean isLeaf; //是否为树叶 public T[] key; //关键字数组 public Node[] child; //子树指针数组 public Node parent; //双亲结点地址 Node(int m) { //构造方法 keyNum = 0; isLeaf = true; key = (T[]) (new Object[ 2*m - 1]); child = new Node[ 2*m]; parent = null; } }
查找关键码时，返回的查找结果类
class Result { //B-树查找结果类型 public Node resultNode; //指向找到的结点 public int i; //在结点中的关键码序号 public boolean found; //true:找到 false:未找到 }
B树类：
public class BTree<T>{ private Node<T> root = null; //根结点 private int degree; public BTree(int t) { degree = t; } }
4) 基于B-树的查找：分析
从根节点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。
若查找成功，则返回指向被查关键字所在结点的地址和关键字在结点中的位置
若查找不成功，则返回null
假设指向B-树根节点的指针用root表示，待查找的关键字用于key表示，返回结果为Result(resultNode, i , found)
若找到，则fount=true，resultNode 结点汇总第i个关键字等于key
若未找到，则found=false，等于key的关键字应插入在resultNode所指向结点中第i和第i+1个关键字之间。
5）基于B-树的查找：算法
代码
/** * 在B-树t上搜索指定的关键码key * @param key 要搜索的关键码键值 * @param root 要搜索的B-树根结点 * @return 返回结果(resultNode,i,found) * @return 若找到，则found=true，resultNode结点中第i个关键码等于Key * @return 若未找到，则found=false,等于key的关键码应插入在resultNode所指结点中第i和第i+1个关键码之间 */ public Result searchBTree(Node<T> root, T key) { int i=0; Node<T> p=root,q=null; //p指向待查结点，q指向p的双亲结点 boolean found=false; Result rs = new Result(); //存放查找结果 Comparable<T> k = (Comparable<T>) key; while (p!= null && !found) { i=0; // 将i移动到关键字所在的分支 while(i < p.keyNum && k.compareTo((p.key)[i])>0) i++; if (i < p.keyNum && k.compareTo((p.key)[i])==0) found=true; //找到 else { q=p; //保存双亲结点 p=p.child[i]; //在子树中查找 } } if(found==false) p=q; rs.resultNode=p; rs.i=i; rs.found=found; return rs; }
6）基于B-树的插入运算
在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：
插入后，该结点的关键字个数 n ＜ m，不修改指针
==插入后==，该结点的关键字个数 n = m，则需进行“结点分裂”，令 ==s= ⌈ m/2 ⌉==，
在原结点中保留 (P0,K1,P1,...,Ks-1,Ps-1)，构建左子树 ，
在建新结点 (Ps,Ks+1,...,Kn,Pn) ，构建右子树，
最后将（Ks，p）插入双亲结点。
若双亲结点 n=m，继续进行第2步
若双亲为空，则建新的根结点。
构建：3阶B-树
构建：4阶B-树
构建：5阶B-树
7）基于B-树的删除运算
在B-树上删除一个关键字，首先找到该关键字所在结点的位置，具体可分下面两种情况：
被删除结点Ki是最下层的非终端结点（即叶子结点的上一层），则应删除Ki及它的右边的指针；删除后若结点中关键字个数不少于⌈ m/2 ⌉-1，则删除成功；否则要进行合并结点操作。
待删除结点是最下层的非终端结点以上某个层次的结点，根据B-树的特性，可以用Ki右边指针Pi所指子树中最小关键字Y代替K，然后在相应的结点中删除Y。
删除B-树中最下层的非终端结点的关键字，分为以下3种情况：
被删除关键字所在结点的关键字个数不小于⌈ m/2 ⌉，则只需从该结点中删除关键字Ki相应的指针Pi，树的其他部分保持不变。
被删除关键字所在结点的关键字个数等于⌈ m/2 ⌉-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字个数大于⌈ m/2 ⌉-1，则需将其右兄弟的最小关键字（或其左兄弟的最大关键字）上移到双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移到被删关键字所在的结点中。
被删除关键字所在结点的关键字个数和其相邻的兄弟结点中的关键字个数均等于⌈ m/2 ⌉-1，此时需将被删关键字的所在结点与其左或右兄弟合并。
3阶删除：
最下层非终端结点
最下层非终端结点以上：删除85
综合：删除70
4阶删除
最下层非终端结点
最下层非终端结点以上：删除9和85
综合：删除 70
5阶删除
最下层非终端结点
最下层非终端结点以上：删除 84
综合：删除 70
综合2：删除70
8）性能分析
在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。
由于除根节点外的每个非终端结点至少有⌈ m/2 ⌉棵子树 ，... ，第h+1层至少2×⌈ m/2 ⌉h-1个结点。
在含n个关键字的m阶B-树上最大深度不超过 log⌈ m/2 ⌉((n+1)/2) + 1
三、B+树
B+树是B-树的一种变型
每个叶子结点中含有n个关键字和n个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针向含最小关键字的结点；
每个非叶结点中的关键字Ki即为其相应指针Pi所指子树中关键字的最大值
所有叶子节点都处在同一层次上，每个叶子结点中关键字的个数均介于⌈ m/2 ⌉和m之间
在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找
1. 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束
2. 若在结点内查找时，给定值 ≤ Ki，则应该继续在Pi所指子树中进行查找
类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”
