B-树：解锁大数据存储和与快速存储的密码

在我们学习数据结构的过程中，我们会学习到二叉搜索树、二叉平衡树、红黑树。

这些无一例外，是以一个二叉树展开的，那么对于我们寻找其中存在树中的数据，这个也是一个不错的方法。

但是，如若是遇到了非常大的数据容量进行存储的时候，此时呢，无法一次性加载到内存当中，那么此时，这样的二叉结构的树就显得力不从心了。

这是因为，我们二叉树中，一个节点只保存了一个数据域，此时遇到非常大数据量的时候，导致树高变得很高，进行遍历查询树的时候，需要遍历树较深的地方，当然，查询的数据如若是在较浅树层，那么查询的时间还好，如若是非常深，那么此时查询的时间就会变得很耗时。

所以我们干脆在一个节点中存储多个数值域，以达到减少树高，从而获得高效率的查询效率。

而我们数据结构中，正好有一种符合此特征的，那就是B-树

B-树

那么又是B-树？

定义：一种适合外查找的树，它是一种平衡的多叉树

那么它具有什么性质呢？

一颗M阶（M > 2）的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1.根节点至少有两个孩子

2.每个非根节点的关键字至少有M/2-1(向上取整），至多有M-1个关键字，并以升序排列

比如当M=4，至少有（4/2-1=1）个关键字，至多有（4-1=3）个关键字.

3.每个非根节点的孩子至少有（M/2）向上取整，至多有M个孩子

比如当M=4，至少有（4/2=2）个孩子，至多有4个孩子

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

5.所有叶子节点都在同一层

由此可得出，

孩子节点会比关键字多出一个。

值得注意的是，为了使其关键字和孩子访问速度较快，所以使用的是数组进行存储。

节点图例：

这里值得注意的是，上述节点图例，是一般情况下的，为了后续插入操作简易进行，所以节点内部会进行修改。后面的插入操作进行解释。

修改后的节点：

现在小编来分享下插入操作，以三叉树作为例子

插入

根据此修改后的插入节点图例，此节点定义代码如下：

 //这里约定以三叉树作为实现public static int BT=3;//定义节点static class Node{//keys关键字数组public int [] keys;//孩子数组public Node [] subs;//有效数据大小public int Usize;//父亲节点public Node parent;//提供一个构造方法public Node(){//多给一个节点，利于后续分裂this.keys=new int[BT];//孩子域会比父亲域多一个this.subs=new Node[BT+1];}}

插入操作其实是大致可说为，插入按照某个插入算法进行插入，满了就进行分裂。

假设我们有以下的插入数据

序列：53, 139, 75, 49, 145, 36, 101

那么初始插入，因为我们关键字数组是中是有序的序列，所以我们需要选用一个插入算法进行插入，这里选择的是直接插入排序

初始状态如下：

注意，我们是初始情况，即根节点是为空的

所以如何插入53的呢？

显然，先新建一个节点，然后直接放到keys[0]，Usize++即可。

代码实例：

//定义一个头节点public Node root;public boolean insert(int key){//如若根节点为空if(root==null){root=new Node();root.keys[0]=key;root.Usize++;return true;}

那么此时如若不为空呢？
即我们插入75的数据，那么此时我们先要找到75是否是存在于树中。

那么接下来说说，如何实现查找的

查找

我们以一个实例说明（值得注意的是，数据有序是因为以直接插入排序进行的）

假设我们要寻找的是54这个节点

显然我们在根节点是寻找不到的，那么此时该去哪个数值的子树去寻找呢？

因为我们的49是比54小的，那么接着去下一个数值去比较，即75

那么54和75比较，那么此时的是大于54的，所以就结束我们的比较

所以我们得去75的孩子节点数组去找，

那么此时就到了53这棵树这里，此时显然，54也是不在这里的，那么此时我们按照逻辑，还是得去子树再找，那么这里呢，没有子树了，所以导致我们寻找节点变为null了

这里要保存其父亲节点，进行后续的操作。

那么就有一个问题了

如若我们找到了，那我们一般也是返回当前的节点，如若我们找不到了，也是返回此时的保存下来的父亲节点，那么怎么区分他们是找到还是没有找到呢？

这里提供一个方案：

新建一个泛型类，存储下当前的节点以及一个整数值，通过整数值去判断是否是找到了

泛型类代码：

public class Pair<k,v> {public k key;public v val;public Pair(k key,v val){this.key=key;this.val=val;}public void setKey(k key) {this.key = key;}public void setVal(v val) {this.val = val;}public v getVal() {return val;}public k getKey() {return key;}
}

接下来是寻找节点代码

寻找节点代码：

private Pair<Node,Integer> findNode(int key) {Node cur=root;Node parent=null;while (cur!=null){int i=0;while (i<cur.Usize){if(cur.keys[i]==key){return new Pair<>(cur,i);}else if(cur.keys[i]<key){i++;}else {break;}}parent=cur;cur=cur.subs[i];}return new Pair<>(parent,-1);}

此时，我们就可以判断返回值是不是负数即可。

  //当根节点不为空，那么此时找出这个key是否存在B树中Pair<Node,Integer> node=findNode(key);//根据返回值是否插入还是修改if(node.val!=-1){System.out.println("此key值已存在！");return false;}//没有找到，那么此时就要插入这个新节点，//此时的插入操作就是以直接插入方法进行Node parent=node.getKey();int i=parent.Usize-1;for (;i>=0;i--){if(parent.keys[i]>=key){parent.keys[i+1]=parent.keys[i];}else {break;}}//此时i变成负数，我们要把0下标的值放进去。parent.keys[i+1]=key;parent.Usize++;if(parent.Usize >= BT){//超出容量，此时进行分裂Split(parent);return true;}else {return true;}}

那么如若我们找不到的话，即这个数据是未曾插入的，所以我们要进行插入它。

那么插入的话选用了直接插入排序。

插入完成之后，我们还要判断下是否是大于了这个BT值，如若是大于了，此时我们就要进行分裂。

那么接下来就还有个分裂操作还没有分享。

分裂

这里的分裂分为根节点分裂，和孩子节点分裂

举例

根节点满时：

值得注意的是，我们把关键字移动的同时，也要把孩子数组对应到下标值，一一挪过去，挪过去的同时也要对subs[]数组中的值的父亲进行修改

然后呢，此时我们这里的举动是把同一层的孩子节点处理了，但是新出现的根节点

就比如现在的75，还没用进行处理，所以呢，我们要处理它，

比如keys[0]下标放的是75，subs[0]下标放的是53这个节点，sub[1]放的是139这个节点值

然后把53这个节点的父亲和139这个父亲，进行修改，然后还要修改对应的Usize。

  private void Split(Node cur) {Node parent=cur.parent;Node newNode=new Node();int mid=cur.Usize>>1;int j=0;int i=mid+1;for (;i<cur.Usize;i++){newNode.keys[j]=cur.keys[i];newNode.subs[j]=cur.subs[i];if(newNode.subs[i]!=null){//修改迁移过去的父亲节点newNode.subs[j].parent=newNode;}j++;}//由于分配多了一个节点，那么此时就要再次拷贝下孩子newNode.subs[j]=cur.subs[i];if(newNode.subs[i]!=null){newNode.subs[i].parent=newNode;}//此时进行修改Usize和新创建节点的父亲节点cur.Usize=cur.Usize-j-1;newNode.Usize=j;if(cur==root){root=new Node();root.keys[0]=cur.keys[mid];root.subs[0]=cur;root.subs[1]=newNode;root.Usize++;cur.parent=root;newNode.parent=root;return;}newNode.parent=parent;

这里是根节点的修改，还有孩子节点的分裂

孩子节点的分裂：

以下面例子举例：

显然，最左边的树，是满了，所以要进行分裂

孩子分裂出来的思路和刚刚根节点是差不多，

那么这里要说明的是下，对于孩子节点分裂完后，父亲节点的操作

即把49提到根节点后怎么操作。

插入49也是一个直接插入排序，所以不过多讲解。

如若我们定义一个endT=当前节点的.Usize-1，即是1-1=0，就是0下标。

那我们可以发现，没有分裂前，75这个节点subs[1]连接139这棵树。

那么如何把新增加53这棵树的节点插入到subs[1]呢？

显然，当我们把49和53排好序后，此时的endT=0

所以，subs[endT+2]的空间存储139这棵树节点即可。

等代码跳出循环后，再次把subs[1]的值赋值为53这棵树的节点值即可。

那么此时接着插入节点

可以注意到的是，101那边的这棵树也满了，继续分裂

再次注意到，出现了连续分裂，因为根节点这棵树也是满了，所以接着也要对根节点这棵树进行分裂，为了可以进行连续分裂，我们可以进行递归这样的方式

即判断下分裂完后，把139提到根节点后，当前的Usize值是否是满的，然后递归分裂

完整分裂代码：

 private void Split(Node cur) {Node parent=cur.parent;Node newNode=new Node();int mid=cur.Usize>>1;int j=0;int i=mid+1;for (;i<cur.Usize;i++){newNode.keys[j]=cur.keys[i];newNode.subs[j]=cur.subs[i];if(newNode.subs[i]!=null){//修改迁移过去的父亲节点newNode.subs[j].parent=newNode;}j++;}//由于分配多了一个节点，那么此时就要再次拷贝下孩子newNode.subs[j]=cur.subs[i];if(newNode.subs[i]!=null){newNode.subs[i].parent=newNode;}//此时进行修改Usize和新创建节点的父亲节点cur.Usize=cur.Usize-j-1;newNode.Usize=j;if(cur==root){root=new Node();root.keys[0]=cur.keys[mid];root.subs[0]=cur;root.subs[1]=newNode;root.Usize++;cur.parent=root;newNode.parent=root;return;}newNode.parent=parent;//此时开始对父亲节点开始操作int endT=parent.Usize-1;int midVal=cur.keys[mid];//采取的是直接插入for(;endT>=0;endT--){if (parent.keys[endT]>=midVal){parent.keys[endT+1]=parent.keys[endT];parent.subs[endT+2]=parent.subs[endT+1];}else {break;}}parent.keys[endT+1]=midVal;parent.subs[endT+2]=newNode;parent.Usize++;if(parent.Usize>=BT){Split(parent);}}

ok，B-树的整个插入操作就讲完啦

那么接下来的删除操作