B-Tree及其建立过程

B树

B树在查找、访问、插入、删除操作上时间复杂度为O（log2（n））
在大规模数据存储方面，大量数据存储在外存磁盘中，而在外存磁盘中读取/写入数据时，通过IO操作要花费大量的时间，因此需减少树的深度，来减少IO操作，以此来提升效率。
B树通常在数据库和文件系统中被使用

特性（m阶）

①树中每个结点至多有m个孩子
②有n个孩子的非终端结点恰好包含n-1个关键字
③除根和叶子结点外，其它每个结点至少有m/2（向上取整）个孩子
④若根结点不是叶子结点，则至少有两个孩子
⑤所有叶子结点都出现在同一层，叶子结点不包含关键字

B树的分裂

当树中某个结点的数据量大于最大值时，以该结点中央数据为界限，分为三部分数据。将中央数据上升到其父结点中，新建一个结点和原结点分别存储分离后两端的数据，并将其作为上升数据的左右两个子树。
当根结点中的数据量也大于最大值时，向上分裂，会产生一个新的根，致使整个数的高度加一。

B树的建立

由两个结构体对B树进行存储

①存储树的结点信息

class BNode{
 	//关键字个数
	 public int num;
	 //数据，需存储一个溢出结点
 	public int[] data;
 	//子节点,需存储一个溢出结点的右子结点
 	public BNode[] childNodes;
 	//父结点（分裂时需用到）
 	public BNode dadNode;
 }

②存储B树的基本信息和根

class Btree{
  	//每个结点最大存储数据数
  	public int max;
  	//最小存储数据数
  	public int min;
  	//树根结点、
  	public BNode rootNode;
 }

具体建立过程（以文件为数据来源）

①提取文件信息，初始化树

/**
  * 从文件中读取数据，构建一棵B树
  * @param file 文件名
  * @param m  阶数(m>=2)
  */
 public void creBTree(String file, int m) {
  	BufferedReader bReader;
  	try {
   		bReader = new BufferedReader(new FileReader(file));
   		String data = bReader.readLine();
   		if(btree == null) {
    			btree = new Btree(m, Integer.parseInt(data));
   		}
   		while((data = bReader.readLine()) != null) {
    			BNode addNode = seekLocate(this.btree.rootNode, Integer.parseInt(data));   
    			//判断结点是否溢出，若溢出，则进行分裂
    			if(addNode.num > this.btree.max) {
     					System.out.println("加入"+Integer.parseInt(data)+"时，结点溢出"+"\t");
     					spiltNode(this.btree, addNode);
     					System.out.println();
    			}
   		}
   		bReader.close();
  	} catch (Exception e) {
   		e.printStackTrace();
  	}
 }

②加入新的数据，从树根开始进行查找定位

/**
  * 定位数据位置
  * @param node 查找结点
  * @param data 数据
  * @return  添加结点
  */
 private BNode seekLocate(BNode node,int data) {
  	int locate = 0;
  	while(data > node.data[locate] && locate < node.num) {
   		locate++;
  	}
  	if(node.childNodes[locate] != null) {
   		return seekLocate(node.childNodes[locate], data);
  	}else {
   		//后移数据
   		for(int i=node.num-1; i>=locate; i--) {
    			node.data[i+1] = node.data[i];
   		}
   		node.data[locate] = data;
   		node.num++;
  	}
  	return node;
 }

③对溢出结点进行分裂

/**
  * 对结点进行分裂，更新树结构
  * @param node 溢出的结点
  */
 private void spiltNode(Btree bTree, BNode node) {
  	int mid = node.num/2;   //需要上升到父结点的结点
  	int midData = node.data[mid];
  	BNode faNode = node.dadNode;       //取出父结点
  	//若为空，即根结点溢出，新建根结点
  	if(faNode == null) {
   		System.out.print("层数加一"+"\t");
   		faNode = new BNode(bTree, null);
   		this.btree.rootNode = faNode;
  	}
  	//构建一个分裂所得的新结点,更新之前结点(数据、子结点、子节点的父结点）
  	BNode spiNode = new BNode(bTree,faNode);
  	spiNode.num = node.num - 1 - mid;
  	int locate = 0;
  	for(int i = mid+1; i<= node.num - 1; i++) {
   		spiNode.data[locate] = node.data[i];
   		node.data[i] = 0;
   		spiNode.childNodes[locate] = node.childNodes[i];
   		//防止访问内存越界
   		if(spiNode.childNodes[locate] != null) {
    			spiNode.childNodes[locate].dadNode = spiNode;
   		}
   		node.childNodes[i] = null;
   		locate++;
  	}
  	//最后一个孩子
  	spiNode.childNodes[locate] = node.childNodes[node.num];
  	if(spiNode.childNodes[locate] != null) {
   		spiNode.childNodes[locate].dadNode = spiNode;
   		node.childNodes[node.num] = null;
  	}
  	node.num = mid;
  	node.data[mid] = 0;
	
	//更新父结点
  	System.out.print("并入父结点"+"\t");
  	int i = faNode.num;
  	//后移数据和孩子指针
  	while(i > 0 && faNode.data[i-1] > midData) {
   		faNode.data[i] = faNode.data[i-1];
   		faNode.childNodes[i+1] = faNode.childNodes[i];
   		i--;
  	}
   
  	faNode.data[i] = midData;
  	faNode.childNodes[i] = node;
  	faNode.childNodes[i+1] = spiNode;
  	spiNode.dadNode = node.dadNode = faNode;
  	faNode.num++;
    
  	//若父结点溢出，则继续分裂
  	if(faNode.num > bTree.max) {
   		System.out.print("父结点溢出"+"\t");
   		spiltNode(bTree, faNode);
  	}
 }

将三个函数合并进行测试

public static void main(String[] args) {
  	B_Tree myTree = new B_Tree();
  	myTree.creBTree("Test/B_Tree.txt", 3);
 }

结果