用java实现一个B+树
时间: 2023-05-28 11:02:59 浏览: 209
B树是一种平衡查找树,它可以在O(log n)时间内完成插入、删除和查询操作。下面是用Java实现B树的示例代码:
```java
public class BTree {
private int t;
private Node root;
private class Node {
private int n;
private boolean leaf;
private int[] keys;
private Node[] children;
public Node(boolean leafNode) {
this.n = 0;
this.leaf = leafNode;
this.keys = new int[2 * t - 1];
this.children = new Node[2 * t];
}
public int getKey(int index) {
return keys[index];
}
public void setKey(int index, int key) {
keys[index] = key;
}
public Node getChild(int index) {
return children[index];
}
public void setChild(int index, Node child) {
children[index] = child;
}
public int getNumKeys() {
return n;
}
public void setNumKeys(int numKeys) {
this.n = numKeys;
}
public boolean isLeaf() {
return leaf;
}
public void setLeaf(boolean leaf) {
this.leaf = leaf;
}
}
public BTree(int degree) {
t = degree;
root = new Node(true);
}
public void insert(int key) {
Node r = root;
if (r.getNumKeys() == 2 * t - 1) {
Node s = new Node(false);
root = s;
s.setChild(0, r);
splitChild(s, 0, r);
insertNonFull(s, key);
} else {
insertNonFull(r, key);
}
}
private void splitChild(Node node, int index, Node child) {
Node z = new Node(child.isLeaf());
z.setNumKeys(t - 1);
for (int j = 0; j < t - 1; j++) {
z.setKey(j, child.getKey(j + t));
}
if (!child.isLeaf()) {
for (int j = 0; j < t; j++) {
z.setChild(j, child.getChild(j + t));
}
}
child.setNumKeys(t - 1);
for (int j = node.getNumKeys(); j > index; j--) {
node.setChild(j + 1, node.getChild(j));
}
node.setChild(index + 1, z);
for (int j = node.getNumKeys() - 1; j >= index; j--) {
node.setKey(j + 1, node.getKey(j));
}
node.setKey(index, child.getKey(t - 1));
node.setNumKeys(node.getNumKeys() + 1);
}
private void insertNonFull(Node node, int key) {
int i = node.getNumKeys() - 1;
if (node.isLeaf()) {
while (i >= 0 && key < node.getKey(i)) {
node.setKey(i + 1, node.getKey(i));
i--;
}
node.setKey(i + 1, key);
node.setNumKeys(node.getNumKeys() + 1);
} else {
while (i >= 0 && key < node.getKey(i)) {
i--;
}
i++;
if (node.getChild(i).getNumKeys() == 2 * t - 1) {
splitChild(node, i, node.getChild(i));
if (key > node.getKey(i)) {
i++;
}
}
insertNonFull(node.getChild(i), key);
}
}
public void print() {
print(root);
}
private void print(Node node) {
for (int i = 0; i < node.getNumKeys(); i++) {
System.out.print(node.getKey(i) + " ");
}
if (!node.isLeaf()) {
for (int i = 0; i <= node.getNumKeys(); i++) {
print(node.getChild(i));
}
}
}
}
```
上述代码中,BTree类包含一个Node类,Node类中包含了节点的关键字、孩子节点和相关方法。BTree类中的insert方法用于向B树中插入一个元素,insertNonFull方法用于向非满节点中插入元素,splitChild方法用于分裂子节点,print方法用于输出B树的内容。在BTree类的构造函数中,需要指定B树的度数t。