目录
一.概念
B树是一颗多叉平衡树，空树也是多叉平衡树。
一颗M阶的B树要满足以下条件：
1.根节点至少有两个孩子；
2.每个非根节点至少有(上取整)个关键字，至多有
个关键字，并且以升序排列；
3.每个非根节点至少有(上取整)个孩子，至多有
个孩子；
4.key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间；
5.所有的叶子节点都在同一层。
解读一下上面的条件：一颗M阶树的意思是一个节点可以存储多个值，最多存储M-1个，像二叉树使用right和left来存储子树的位置，B树用sub来存储位置，不过这个要存储很多个，最多是M个。就是说每一个存在节点的值都有一个左孩子和右孩子，他们遵从条件4。像下面这个图，连起来的黑线表示是父子关系。
二.节点定义
B树与二叉树不同的是其有多个值，且有多个孩子，这些要开一个数组储存；同时我们还要记录节点的父节点是那个；我们还需要存储数组已使用的空间的数量，方便我们后序操作。
关于数组大小的定义，正常来说一个根能存储的关键字（值）是M-1个的，能存储的地址是M个，这里为什么都多出一个呢？这里是为了后面的分裂操作做准备。等到了后面的分裂操作大家就能感受到这么设计的巧妙之处了。
补充：flag是用于后面判断是否找到要插入位置时使用的，m是M阶B树的M
static class TreeNode{
public int[] key;
public TreeNode[] sub;
public TreeNode parent;
public int usedSize;
public TreeNode(){
this.key=new int[m];
this.sub=new TreeNode[m+1];
usedSize=0;
}
}
TreeNode root;
boolean flag=false;
public static final int m=3;三.插入操作
1.查找位置
要正确插入首先要找到位置。
B树的查找与二叉树还是相似的。先找当前节点内的值，如果我们要插入的val值比数组中的某个值大，那么我们要继续往后比较；如果val比数组中的某个值小，那么我们就进入它的左子树中继续比较；如果val等于数组中的某个值，那么就无法插入。
总结：1.val<key[i] 循环继续；2.val>key[i] 循环结束进入子树；3. val=key[i] 直接返回。
在定义节点的时候我们定义了一个flag，当我们在遇到情况3时，可以让flag=true。这个技巧在很多地方能够用到，如算法题。
public TreeNode find(int val){
TreeNode cur=root;
TreeNode parent = null;
flag=false;
while(cur!=null){
int i=0;
while(i< cur.usedSize){
if(cur.key[i]>val){
break;
}else if(cur.key[i]<val){
i++;
}else{
flag=true;
return null;
}
}
parent=cur;
cur=cur.sub[i];
}
return parent;
}为什么cur=cur.sub[i]呢？下图可以解释：
比如我们要插入4，4<5，我们在i=1时要停下来进入左子树了，刚好sub[i]是5的左子树。
2.插入
找到位置后我们就要进行插入操作了。
首先我们先判断根节点是不是空的，如果是空的我们要先插在根上。
如果我们定义的flag是true的话，说明这个点已经有了无法插入，直接返回即可。
插入操作比较简单，就是一个直接插入排序，插入完不要忘记更新usedSize值（重要）。
插入完我们要判断usedSize是不是已经满了，如果满了我们要进行分裂操作。
public boolean insert(int val){
//如果根节点是空的
if(root==null){
root=new TreeNode();
root.key[0]=val;
root.usedSize++;
return true;
}
TreeNode parent=find(val);
if(flag==true){
//已经有这个点了
return false;
}
//开始插入
int i = parent.usedSize-1;
for (; i >= 0;i--) {
if(parent.key[i] >= val) {
parent.key[i+1] = parent.key[i];
}else {
break;
}
}
parent.key[i+1] = val;
parent.usedSize++;
if(parent.usedSize<m){
//没满
return true;
}else{
split(parent);
return true;
}
}3.分裂
先说一下怎么分裂：
我们先找到中间位置，中间位置的坐标是mid=M/2。这个中间位置的节点就是要上提的，这个节点的左面数组部分就变成了它的左子树，这个节点右面数组部分就变成了它的右子树。
例子：一颗4阶B树，下图
我们可以将分裂分为两步，先单独建立一个节点，将中间值右面部分复制到新节点里；再将中间值上提到原来数组里的父节点里。
第一步，复制右半部分，不仅要复制值，还要复制孩子的地址。这里要记住，复制了孩子的地址仅仅只是父节点连接上了孩子，孩子的parent也要进行更改。还要注意一点是，孩子地址的数组比值的数组多一个，最后还要加上。复制完不要忘记更新数据。
第二步，上提。这里分为两种情况：是根，不是根。
先说是根，如果当前节点是根节点，那么上提的话要新建一个根，如果再进行复制更新。
如果不是根，将中间值插入到数组后，然后进行直接插入排序。
最后都处理完判断上提到的数组是不是满了，如果满了要继续进行分裂。
public void split(TreeNode cur){
//处理右半部分
TreeNode node=new TreeNode();
int mid= cur.usedSize/2;
int i=mid+1;
int j=0;
for(;i<cur.usedSize;i++){
node.key[j]=cur.key[i];
node.sub[j]=cur.sub[i];
if(node.sub[j]!=null){
node.sub[j].parent=node;
}
j++;
}
node.sub[j]=cur.sub[i];
if(node.sub[j]!=null){
node.sub[j].parent=node;
}
//更新数据
node.usedSize=j;
cur.usedSize= cur.usedSize-j-1;
node.parent=cur.parent;
//特判：cur是根节点
if(cur==root){
root=new TreeNode();
root.key[0]=cur.key[mid];
root.sub[0]=cur;
root.sub[1]=node;
node.parent=root;
cur.parent=root;
root.usedSize++;
return;
}
//上提
TreeNode parent=cur.parent;
int end=parent.usedSize-1;
int val=cur.key[mid];
for (; end >= 0;end--) {
if(parent.key[end] >= val) {
parent.key[end+1] = parent.key[end];
parent.sub[end+2] = parent.sub[end+1];
}else {
break;
}
}
parent.key[end+1] = val;
parent.sub[end+2] = node;
parent.usedSize++;
if(parent.usedSize>=m){
split(parent);
}
}四.B+树和B*树
1.B+树
B+树的B树的变种，再B树的基础上加入新的规则：
1.关键字的数量和孩子的数量相同；
2.非叶子节点的子树指针p[i]，指向关键字值属于[ k[i]，k[i+1] ）的子树（都是右子树）；
3.为所有叶子节点增加一个链指针；
4.所有关键字都在叶子节点出现。
2.B*树
B*树的B+树的变种，在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
标签：Java,val,parent,实现,usedSize,通俗易懂,key,TreeNode,节点 From： https://blog.csdn.net/lllsure/article/details/141182492