B树（B-Tree）是一种多路搜索树，用于在磁盘上存储和查找数据。它具有以下特点： 1. 每个节点可以包含多个子节点，通常用于处理大量数据和磁盘存储。 2. 每个节点中的键值按照升序排列，子节点的范围也由这些键值决定。 3. B树的节点中至少包含 t-1 个键值（t 为树的最小度数），最多包含 2t-1 个键值。 4. 所有叶子节点都在同一层，且不包含数据，用于存储实际数据的节点为内部节点。

import java.util.ArrayList;
import java.util.List;public class BTree {private Node root;private int t; // 最小度数private static class Node {List<Integer> keys;List<Node> children;boolean leaf;public Node() {keys = new ArrayList<>();children = new ArrayList<>();leaf = true;}}public BTree(int t) {this.t = t;root = new Node();}// 插入操作public void insert(int key) {Node r = root;if (r.keys.size() == 2*t - 1) {Node s = new Node();root = s;s.children.add(r);splitChild(s, 0);insertNonFull(s, key);} else {insertNonFull(r, key);}}private void insertNonFull(Node x, int key) {int i = x.keys.size() - 1;if (x.leaf) {x.keys.add(0);while (i >= 0 && key < x.keys.get(i)) {x.keys.set(i+1, x.keys.get(i));i--;}x.keys.set(i+1, key);} else {while (i >= 0 && key < x.keys.get(i)) {i--;}i++;if (x.children.get(i).keys.size() == 2*t - 1) {splitChild(x, i);if (key > x.keys.get(i)) {i++;}}insertNonFull(x.children.get(i), key);}}private void splitChild(Node x, int i) {Node z = new Node();Node y = x.children.get(i);z.leaf = y.leaf;for (int j = 0; j < t - 1; j++) {z.keys.add(y.keys.get(j + t));}if (!y.leaf) {for (int j = 0; j < t; j++) {z.children.add(y.children.get(j + t));}}for (int j = x.keys.size(); j > i; j--) {x.children.add(j + 1, x.children.get(j));}x.children.add(i + 1, z);for (int j = x.keys.size()-1; j >= i; j--) {x.keys.add(j + 1, x.keys.get(j));}x.keys.add(i, y.keys.get(t - 1));y.keys.subList(t - 1, y.keys.size()).clear();if (!y.leaf) {y.children.subList(t, y.children.size()).clear();}}// 查询操作public boolean search(int key) {return searchNode(root, key);}private boolean searchNode(Node x, int key) {int i = 0;while (i < x.keys.size() && key > x.keys.get(i)) {i++;}if (i < x.keys.size() && key == x.keys.get(i)) {return true;}if (x.leaf) {return false;} else {return searchNode(x.children.get(i), key);}}// 修改操作public void modify(int oldKey, int newKey) {delete(oldKey);insert(newKey);}// 删除操作public void delete(int key) {deleteKey(root, key);if (root.keys.isEmpty() && !root.leaf) {root = root.children.get(0);}}private void deleteKey(Node x, int key) {int idx = x.keys.indexOf(key);if (idx != -1) {if (x.leaf) {x.keys.remove(idx);} else {Node pred = x.children.get(idx);Node succ = x.children.get(idx + 1);if (pred.keys.size() >= t) {int newKey = pred.keys.get(pred.keys.size() - 1);deleteKey(pred, newKey);x.keys.set(idx, newKey);} else if (succ.keys.size() >= t) {int newKey = succ.keys.get(0);deleteKey(succ, newKey);x.keys.set(idx, newKey);} else {pred.keys.add(key);pred.keys.addAll(succ.keys);pred.children.addAll(succ.children);x.keys.remove(idx);x.children.remove(idx + 1);deleteKey(pred, key);}}} else {int i = 0;while (i < x.keys.size() && key > x.keys.get(i)) {i++;}Node child = x.children.get(i);if (child.keys.size() == t - 1) {Node leftSibling = (i > 0) ? x.children.get(i - 1) : null;Node rightSibling = (i < x.children.size() - 1) ? x.children.get(i + 1) : null;if (leftSibling != null && leftSibling.keys.size() >= t) {child.keys.add(0, x.keys.get(i - 1));x.keys.set(i - 1, leftSibling.keys.remove(leftSibling.keys.size() - 1));if (!leftSibling.leaf) {child.children.add(0, leftSibling.children.remove(leftSibling.children.size() - 1));}} else if (rightSibling != null && rightSibling.keys.size() >= t) {child.keys.add(x.keys.get(i));x.keys.set(i, rightSibling.keys.remove(0));if (!rightSibling.leaf) {child.children.add(rightSibling.children.remove(0));}} else {if (leftSibling != null) {leftSibling.keys.add(x.keys.remove(i - 1));leftSibling.keys.addAll(child.keys);leftSibling.children.addAll(child.children);x.children.remove(i);} else {child.keys.addAll(rightSibling.keys);child.children.addAll(rightSibling.children);x.keys.remove(i);x.children.remove(i + 1);}deleteKey(child, key);}} else {deleteKey(child, key);}}}// 中序遍历public void inorder() {inorderTraversal(root);}private void inorderTraversal(Node node) {if (node != null) {int i = 0;for (i = 0; i < node.keys.size(); i++) {if (!node.leaf) {inorderTraversal(node.children.get(i));}System.out.print(node.keys.get(i) + " ");}if (!node.leaf) {inorderTraversal(node.children.get(i));}}}
}

        实战代码：

import java.util.ArrayList;
import java.util.List;/*** BTree类* * @author lingfeng**/
public class BTree {/**BTree 基础参数信息配置最小度数    t=2时，称作2-3-4数，表示只能存在2、3、4子女数**/private int t = 2;  /**非根节点最小关键字数**/private int minKeys = t-1;/**内节点最大关键字数**/private int maxKeys = 2*t - 1;/**树根节点**/private BTreeNode root;/**构造函数**/public BTree(){//初始化root = new BTreeNode();root.setLeaf(true);}/**构造函数  t 最小度数**/public BTree(int t){this();this.t  = t;minKeys = t - 1;maxKeys = 2*t - 1;}/**插入元素* * 1.元素存在，插入元素* 2.元素不存在，插入元素* * **/public void insertNode(Integer key){if(root.size() == maxKeys){   //根节点已满//进行根节点分割BTreeNode tmpNode = new BTreeNode();tmpNode.setLeaf(false);tmpNode.getChildrens().add(root);btreeSplitChild(tmpNode, 0, root);root = tmpNode;}insertRootNotFull(root, key);}public void insertRootNotFull(BTreeNode node, int key){//如果该节点为叶子节点if(node.isLeaf()){//寻找当前节点所有关键字ResultSearch result = divideSearch(node.getKeys(), key);//查询结果：成功  返回已经存在关键字位置if(result.result == true){}else{    //查询结果：失败   返回插入位置node.insertKey(key, result.index);}}else{//寻找当前节点所有关键字ResultSearch result = divideSearch(node.getKeys(), key);//查询结果：成功  返回已经存在关键字位置if(result.result == true){}else{    //查询结果：失败   返回插入子女节点的位置//判断子女状态BTreeNode childNode = node.childAt(result.index);if(node.childAt(result.index).size() == (2*t - 1)){btreeSplitChild(node, result.index, childNode);if(key > node.keyAt(result.index)){   //判断key落在 前半部分 或 后半部分childNode = node.childAt(result.index + 1);}}insertRootNotFull(childNode, key);}}}/**查询元素 (BTree查询)* * 1.先查询节点的关键字列表* 2.失败则，查询子女节点；成功则，返回值* 3.递归搜索* * **/public Integer search(BTreeNode node,Integer key){List<Integer> keys_tmp = node.getKeys();ResultSearch result = divideSearch(keys_tmp, key);if(result.result){return result.index;}else{return search(node.childAt(result.index), key);}}/**二分查询* 参数 元素列表、所需要查询元素的值* * **/public ResultSearch divideSearch(List<Integer> elements, int key){int start = 0;    //扫描起始位置int end   = 0;    //扫描结束位置end = elements.size() - 1;int mid = 0; while(start<=end){mid   = (start + end)/2;if(elements.get(mid) == key){ //满足等值条件break;}else if(elements.get(mid) > key){ //在列表前半部分//改变扫描结束位置end = mid - 1;}else if(elements.get(mid) <= key){//改变扫描开始位置start = mid + 1;}}boolean result = false;Integer index = 0;if(start<=end){  //二分查找成功result = true;index = mid;}else{    //查找失败，不存在元素result = false;index = start;}return new ResultSearch(result,index);}/*** 节点分割函数* @param parentNode  被分割节点的父节点* @param index  被分割节点在父节点的第index个子女索引位置* @param Node   被分割节点*/public void btreeSplitChild(BTreeNode parentNode, int index, BTreeNode node){//新建一个节点，保存分割后[t+1 2t-1]数据BTreeNode subNode = new BTreeNode();//必须加上subNode.setLeaf(node.isLeaf());for(int i=1; i<=minKeys ; i++){subNode.getKeys().add(node.keyAt(t + i -1));}//保存分割点值[t]Integer key = node.keyAt(t - 1);//删除被分割节点的[t 2t-1]数据for(int i= maxKeys - 1; i>=minKeys; --i){node.getKeys().remove(i);}if(!node.isLeaf()){ //如果满节点不是叶节点，关键字分割后，需要将其子女进行操作//subNode应该拥有后半部分的子女for(int i=0 ; i<minKeys+1 ; ++i){subNode.getChildrens().add(node.childAt(i+t));}//并删除node后半部分的子女for(int i=maxKeys ; i>=minKeys+1; --i){node.getChildrens().remove(i);}}else{}//将[t]数据加入父节点中去parentNode.insertKey(key, index);//将新节点关联到父节点index+1子女中parentNode.insertChild(subNode, index+1);}public void delete(Integer key){delete(root, key);}public void delete(BTreeNode node, Integer key){//删除关键字时，必须保证关键字大于等于tassert node.size() >=t || node == root;//对当前节点进行二分查找ResultSearch resultSearch = divideSearch(node.getKeys(), key);//成功if(resultSearch.result){//如果当前节点属于叶子节点，可以直接进行删除if(node.isLeaf()){node.getKeys().remove(resultSearch.index.intValue());}else{//如果不是叶子节点 ，判断前于key子节点状态BTreeNode leftChildNode = node.childAt(resultSearch.index);if(leftChildNode.size() >= t){//从leftChildNode进行借值 代替当前需要删除的关键字//删除当前节点关键字node.getKeys().remove(resultSearch.index.intValue());node.insertKey(leftChildNode.keyAt(leftChildNode.size()-1), resultSearch.index);delete(leftChildNode, leftChildNode.keyAt(leftChildNode.size()-1));}else{BTreeNode rightChildNode = node.childAt(resultSearch.index + 1);if(rightChildNode.size() >= t){//从rightChildNode进行借值 代替当前需要删除的关键字node.getKeys().remove(resultSearch.index.intValue());node.insertKey(rightChildNode.keyAt(0), resultSearch.index);delete(rightChildNode, rightChildNode.keyAt(0));}else{//对于索引的左右子节点的数量都等于t-1//合适进行合并//1.将父节点删除  将节点右子节点删除node.getKeys().remove(resultSearch.index.intValue());node.getChildrens().remove(resultSearch.index.intValue() + 1);//2.将父节点添加到左子节点上leftChildNode.getKeys().add(key);//3.将删除的右子节点添加到左子节点上for(int i=0 ; i<rightChildNode.size() ; i++){leftChildNode.getKeys().add(rightChildNode.getKeys().get(i));}//如果右子节点非叶子节点，需要将其子女继承到左节点之下if(!rightChildNode.isLeaf()){for(int k=0 ; k<=rightChildNode.size() ; k++){leftChildNode.getChildrens().add(rightChildNode.childAt(k));}}//递归删除delete(leftChildNode, key);}}}}else{ //失败if(node.isLeaf()){//不存在删除的对象System.out.println("不存在删除的对象");return ;}//获取子节点BTreeNode childNode = node.childAt(resultSearch.index);if(root == node && node.size()==0){root = childNode;}if(childNode.size() >= t){   //如果满足递归条件delete(childNode, key);}else{//不满足size == t//采取借关键字手段BTreeNode subNode = null;int subIndex = 0;//先检测右兄弟节点if(resultSearch.index < node.size()){if(node.childAt(resultSearch.index+1).size() >=t){subNode  = node.childAt(resultSearch.index+1);subIndex = resultSearch.index + 1;}}//测试左兄弟节点if(subNode == null){if(resultSearch.index > 0){if(node.childAt(resultSearch.index-1).size() >= t){subNode  = node.childAt(resultSearch.index-1);subIndex = resultSearch.index - 1;}}}//测试完成后if(subNode != null){  //存在兄弟节点大于等于t情况//判断节点if(subIndex > resultSearch.index){ //右兄弟//将右关键字插入自身childNode.insertKey(node.keyAt(subIndex - 1), childNode.size());node.getKeys().remove(subIndex - 1);node.insertKey(subNode.keyAt(0), subIndex - 1);subNode.getKeys().remove(0);//右兄弟非子叶节点，则带有孩子节点if(!subNode.isLeaf()){childNode.getChildrens().add(subNode.getChildrens().get(0));subNode.getChildrens().remove(0);}}else{  //左兄弟//将左关键字插入自身最前位置childNode.insertKey(node.keyAt(subIndex), 0);node.getKeys().remove(subIndex);node.insertKey(subNode.keyAt(subNode.size()-1), subIndex);subNode.getKeys().remove(subNode.size()-1);//如果左兄弟非子叶节点if(!subNode.isLeaf()){childNode.insertChild(subNode.childAt(subNode.size()), 0);subNode.getChildrens().remove(subNode.size()-1);}    }delete(childNode, key);}else{//该节点的左右兄弟节点关键字都为t-1//选择合并方案if(resultSearch.index < node.size()){   //右兄弟存在subNode = node.childAt(resultSearch.index + 1);//childNode.getKeys().add(node.keyAt(resultSearch.index + 1));childNode.getKeys().add(node.keyAt(resultSearch.index));node.getKeys().remove(resultSearch.index.intValue());node.getChildrens().remove(resultSearch.index.intValue());for(int i=0 ; i<subNode.size() ; i++){childNode.getKeys().add(subNode.keyAt(i));}if(!subNode.isLeaf()){for(int k=0 ; k<=subNode.size(); k++){childNode.getChildrens().add(subNode.childAt(k));}}}else{      //左兄弟存在subNode = node.childAt(resultSearch.index - 1);childNode.insertKey(node.keyAt(resultSearch.index-1), 0);node.getKeys().remove(resultSearch.index - 1);node.getChildrens().remove(resultSearch.index-1);for(int i=subNode.size()-1 ; i>=0 ; --i){childNode.insertKey(subNode.keyAt(i), 0);}if(!subNode.isLeaf()){for(int k=subNode.size() ; k>=0 ; --k){childNode.insertChild(subNode.childAt(k),0);}}}if(root == node && node.size() == 0){root = childNode;}delete(childNode, key);}}}}}
class BTreeNode{/**当前节点keys列表**/private List<Integer> keys; /**当前节点的child列表**/private List<BTreeNode> childrens;/**是否是叶子节点**/private boolean leaf;public BTreeNode(){keys      = new ArrayList<Integer>();childrens = new ArrayList<BTreeNode>();leaf = true;}/*** set and get methods* * **/public List<Integer> getKeys() {return keys;}public void setKeys(List<Integer> keys) {this.keys = keys;}public List<BTreeNode> getChildrens() {return childrens;}public void setChildrens(List<BTreeNode> childrens) {this.childrens = childrens;}public boolean isLeaf() {return leaf;}public void setLeaf(boolean leaf) {this.leaf = leaf;}/*** 获取子女节点* @param index* @return*/public BTreeNode childAt(int index){return childrens.get(index);}/*** 获取关键字* @param index* @return*/public Integer keyAt(int index){return keys.get(index);}/*** 获取节点关键字数量* @return*/public int size(){return keys.size();}/*** 插入key到指定的index中去* @param key* @param index*/public void insertKey(Integer key, int index){//插入key到指定的索引位置//保存索引前的所有关键字List<Integer> newlist = new ArrayList<Integer>();for(int i=0; i<index ; i++){newlist.add(keys.get(i));}//插入关键字newlist.add(key);//保存索引后多关键字for(int i=index ; i<keys.size() ; i++){newlist.add(keys.get(i));}//将新的关键字集合设置为节点关键字集合对象keys = newlist;}/*** 插入node子女到指定的index位置* @param node* @param index*/public void insertChild(BTreeNode node, int index){//插入childList<BTreeNode> newlist = new ArrayList<BTreeNode>();for(int i=0 ; i< index ; i++){newlist.add(childrens.get(i));}newlist.add(node);for(int i=index ; i<childrens.size() ; i++){newlist.add(childrens.get(i));}childrens = newlist;}
}
/*** 查询结果类* result 标识成功的状态 true or false* index 成功后返回元素的索引*       失败后返回元素的插入位置 * @author lingfeng*/
class ResultSearch{public Integer index;public boolean result;public ResultSearch(boolean rs, Integer i){index  = i;result = rs;}
}