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){
//删除关键字时，必须保证关键字大于等于t
assert 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){
//插入child
List<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;
}
}