我的问题:用java实现一个B+树
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));}}}
}
改天有时间试一试代码对不对。