定义一个接口Bpackage bptree; // 先来定义一个接口 // 每一个树都应该具备下面的这三个功能 public interface B { // 查询 public Object get(Comparable key); // 移除节点 public void remove(Comparable key); // 插入或者更新节点， 如果节点已经存在就更新； 只有节点不存在的时候就插入这个节点 public void insertOrUpdate(Comparable key, Object obj); } 开始实现我的B+树 package bptree; import java.util.Random; // 这个是我的B+树，实现我自己定义的三个接口(接口一旦定义了， 实现类都必须要一一实现这个接口) public class IBPlusTree implements B{ // 定义B+树的一些节点属性 // 根节点 protected INode root; // 阶数：一个节点最多能够有多少个子节点(也就是M阶) protected int order; // 叶子结点的链表头 protected INode head; public INode getRoot() { return root; } public void setRoot(INode root) { this.root = root; } public int getOrder() { return order; } public void setOrder(int order) { this.order = order; } public INode getHead() { return head; } public void setHead(INode head) { this.head = head; } // 获得一个节点 @Override public Object get(Comparable key) { // TODO Auto-generated method stub return root.get(key); } // 删除节点的实现 @Override public void remove(Comparable key) { // TODO Auto-generated method stub // 删除这一颗树的节点key(直接删除即可) root.remove(key, this); } // 添加或者更新节点 @Override public void insertOrUpdate(Comparable key, Object obj) { // TODO Auto-generated method stub // 在这一颗树的key的位置添加一个新的节点obj root.insertOrUpdate(key, obj, this); } // 定义我的构造函数（B+树的构造函数） /\*\* \* 这是一个order(M阶)的B+树 \* @param order \*/ public IBPlusTree(int order){ // 要保证这个树的阶数大于2(也就是一个节点至少要有两个子节点) if (order < 3){ System.out.println("order (M阶数) must be greater than 2"); System.exit(0);; } // 当前的树的阶数设置进来 this.order = order; // 开始新建我的根节点 this.root = new INode(true, true); // 这个树的当前头结点就是自己本身 this.head = root; } // toString()函数的重写 @Override public String toString() { return "BPlusTree "; } } 我的节点 package bptree; import java.util.AbstractMap.SimpleEntry; import java.util.ArrayList; import java.util.List; import java.util.Map.Entry; /\*\* \* 这个是B+树的节点 \* @author Xiugang \* \*/ public class INode { // 添加树的节点的一些属性 // 这个节点是不是叶子节点 protected boolean isLeaf; // 这个节点是不是根节点 protected boolean isRoot; // 父节点 protected INode parent; // 叶子节点的前一个节点 protected INode previous; // 叶子节点的后一个节点 protected INode next; // 一个节点位置的关键字 protected List\> entries; // 孩子节点(一个节点有多个孩子节点， 这里需要使用List集合来存储孩子节点) protected List children; public boolean isLeaf() { return isLeaf; } public void setLeaf(boolean isLeaf) { this.isLeaf = isLeaf; } public boolean isRoot() { return isRoot; } public void setRoot(boolean isRoot) { this.isRoot = isRoot; } public INode getParent() { return parent; } public void setParent(INode parent) { this.parent = parent; } public INode getPrevious() { return previous; } public void setPrevious(INode previous) { this.previous = previous; } public INode getNext() { return next; } public void setNext(INode next) { this.next = next; } public List\> getEntries() { return entries; } public void setEntries(List\> entries) { this.entries = entries; } public List getChildren() { return children; } public void setChildren(List children) { this.children = children; } // 定义我的这个节点的构造函数 /\*\* \* 根据是不是叶子节点来进行构造 \* @param isLeaf \*/ public INode(boolean isLeaf){ // 每次生成一个节点都要看一下是不是叶子节点 this.isLeaf = isLeaf; // 设置这个节点位置的关键字 this.entries = new ArrayList\>(); // 如果不是叶子节点的话 if (!isLeaf){ // 只要不是叶子节点的话， 那么这个节点就有一个孩子节点 this.children = new ArrayList(); } } /\*\* \* 通过是不是叶子节点，是不是根节点来构造 \* @param isLeaf \* @param isRoot \*/ public INode(boolean isLeaf, boolean isRoot){ // 调用我上面的构造函数 this(isLeaf); // 根节点 this.isRoot = isRoot; } /\*\* \* 根据key值获得一个节点 \* @param key \* @return \*/ public Object get(Comparable key){ // 如果这个节点是叶子节点的话 if (this.isLeaf){ // 开始遍历我的所有的关键字集合 for (Entry entry : entries){ // 如果在这个集合里面找到了和我的这个key相等的key if (entry.getKey().compareTo(key) == 0){ // 就把这个对象返回出去 return entry.getValue(); } } // 如果没有找到，就返回空 return null; } // 如果当前的这个节点不是叶子节点的话 else { // 如果key小于等于节点最左边的key, 就沿着第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0){ return children.get(0).get(key); } // 如果key 大于节点最右边的key, 就沿着最后一个子节点继续搜索 else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { return children.get(children.size()-1).get(key); //否则沿比key大的前一个子节点继续搜索 } else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { return children.get(i).get(key); } } } } return null; } /\*\* \* 如果key不存在就添加， 如果存在了就更新 \* @param key \* @param obj \* @param tree \*/ public void insertOrUpdate(Comparable key, Object obj, IBPlusTree tree){ //如果是叶子节点 if (isLeaf){ //不需要分裂，直接插入或更新 if (contains(key) || entries.size() < tree.getOrder()){ insertOrUpdate(key, obj); if (parent != null) { //更新父节点 parent.updateInsert(tree); } //需要分裂 }else { //分裂成左右两个节点 INode left = new INode(true); INode right = new INode(true); //设置链接 if (previous != null){ previous.setNext(left); left.setPrevious(previous); } if (next != null) { next.setPrevious(right); right.setNext(next); } if (previous == null){ tree.setHead(left); } left.setNext(right); right.setPrevious(left); previous = null; next = null; //左右两个节点关键字长度 int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; int rightSize = (tree.getOrder() + 1) / 2; //复制原节点关键字到分裂出来的新节点 insertOrUpdate(key, obj); for (int i = 0; i < leftSize; i++){ left.getEntries().add(entries.get(i)); } for (int i = 0; i < rightSize; i++){ right.getEntries().add(entries.get(leftSize + i)); } //如果不是根节点 if (parent != null) { //调整父子节点关系 int index = parent.getChildren().indexOf(this); parent.getChildren().remove(this); left.setParent(parent); right.setParent(parent); parent.getChildren().add(index,left); parent.getChildren().add(index + 1, right); setEntries(null); setChildren(null); //父节点插入或更新关键字 parent.updateInsert(tree); setParent(null); //如果是根节点 }else { isRoot = false; INode parent = new INode(false, true); tree.setRoot(parent); left.setParent(parent); right.setParent(parent); parent.getChildren().add(left); parent.getChildren().add(right); setEntries(null); setChildren(null); //更新根节点 parent.updateInsert(tree); } } //如果不是叶子节点 }else { //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0) { children.get(0).insertOrUpdate(key, obj, tree); //如果key大于节点最右边的key，沿最后一个子节点继续搜索 }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { children.get(children.size()-1).insertOrUpdate(key, obj, tree); //否则沿比key大的前一个子节点继续搜索 }else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { children.get(i).insertOrUpdate(key, obj, tree); break; } } } } } /\*\* 插入节点后中间节点的更新 \*/ /\*\* \* 更新添加的操作 \* @param tree \*/ protected void updateInsert(IBPlusTree tree){ validate(this, tree); //如果子节点数超出阶数，则需要分裂该节点 if (children.size() > tree.getOrder()) { //分裂成左右两个节点 INode left = new INode(false); INode right = new INode(false); //左右两个节点关键字长度 int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2; int rightSize = (tree.getOrder() + 1) / 2; //复制子节点到分裂出来的新节点，并更新关键字 for (int i = 0; i < leftSize; i++){ left.getChildren().add(children.get(i)); left.getEntries().add(new SimpleEntry(children.get(i).getEntries().get(0).getKey(), null)); children.get(i).setParent(left); } for (int i = 0; i < rightSize; i++){ right.getChildren().add(children.get(leftSize + i)); right.getEntries().add(new SimpleEntry(children.get(leftSize + i).getEntries().get(0).getKey(), null)); children.get(leftSize + i).setParent(right); } //如果不是根节点 if (parent != null) { //调整父子节点关系 int index = parent.getChildren().indexOf(this); parent.getChildren().remove(this); left.setParent(parent); right.setParent(parent); parent.getChildren().add(index,left); parent.getChildren().add(index + 1, right); setEntries(null); setChildren(null); //父节点更新关键字 parent.updateInsert(tree); setParent(null); //如果是根节点 }else { isRoot = false; INode parent = new INode(false, true); tree.setRoot(parent); left.setParent(parent); right.setParent(parent); parent.getChildren().add(left); parent.getChildren().add(right); setEntries(null); setChildren(null); //更新根节点 parent.updateInsert(tree); } } } /\*\* 调整节点关键字\*/ /\*\* \* 检查节点的有效性 \* @param node \* @param tree \*/ protected static void validate(INode node, IBPlusTree tree) { // 如果关键字个数与子节点个数相同 if (node.getEntries().size() == node.getChildren().size()) { for (int i = 0; i < node.getEntries().size(); i++) { Comparable key = node.getChildren().get(i).getEntries().get(0).getKey(); if (node.getEntries().get(i).getKey().compareTo(key) != 0) { node.getEntries().remove(i); node.getEntries().add(i, new SimpleEntry(key, null)); if(!node.isRoot()){ validate(node.getParent(), tree); } } } // 如果子节点数不等于关键字个数但仍大于M / 2并且小于M，并且大于2 } else if (node.isRoot() && node.getChildren().size() >= 2 ||node.getChildren().size() >= tree.getOrder() / 2 && node.getChildren().size() <= tree.getOrder() && node.getChildren().size() >= 2) { node.getEntries().clear(); for (int i = 0; i < node.getChildren().size(); i++) { Comparable key = node.getChildren().get(i).getEntries().get(0).getKey(); node.getEntries().add(new SimpleEntry(key, null)); if (!node.isRoot()) { validate(node.getParent(), tree); } } } } /\*\* 删除节点后中间节点的更新\*/ /\*\* \* 删除节点之后的更新操作 \* @param tree \*/ protected void updateRemove(IBPlusTree tree) { validate(this, tree); // 如果子节点数小于M / 2或者小于2，则需要合并节点 if (children.size() < tree.getOrder() / 2 || children.size() < 2) { if (isRoot) { // 如果是根节点并且子节点数大于等于2，OK if (children.size() >= 2) { return; // 否则与子节点合并 } else { INode root = children.get(0); tree.setRoot(root); root.setParent(null); root.setRoot(true); setEntries(null); setChildren(null); } } else { //计算前后节点 int currIdx = parent.getChildren().indexOf(this); int prevIdx = currIdx - 1; int nextIdx = currIdx + 1; INode previous = null, next = null; if (prevIdx >= 0) { previous = parent.getChildren().get(prevIdx); } if (nextIdx < parent.getChildren().size()) { next = parent.getChildren().get(nextIdx); } // 如果前节点子节点数大于M / 2并且大于2，则从其处借补 if (previous != null && previous.getChildren().size() > tree.getOrder() / 2 && previous.getChildren().size() > 2) { //前叶子节点末尾节点添加到首位 int idx = previous.getChildren().size() - 1; INode borrow = previous.getChildren().get(idx); previous.getChildren().remove(idx); borrow.setParent(this); children.add(0, borrow); validate(previous, tree); validate(this, tree); parent.updateRemove(tree); // 如果后节点子节点数大于M / 2并且大于2，则从其处借补 } else if (next != null && next.getChildren().size() > tree.getOrder() / 2 && next.getChildren().size() > 2) { //后叶子节点首位添加到末尾 INode borrow = next.getChildren().get(0); next.getChildren().remove(0); borrow.setParent(this); children.add(borrow); validate(next, tree); validate(this, tree); parent.updateRemove(tree); // 否则需要合并节点 } else { // 同前面节点合并 if (previous != null && (previous.getChildren().size() <= tree.getOrder() / 2 || previous.getChildren().size() <= 2)) { for (int i = previous.getChildren().size() - 1; i >= 0; i--) { INode child = previous.getChildren().get(i); children.add(0, child); child.setParent(this); } previous.setChildren(null); previous.setEntries(null); previous.setParent(null); parent.getChildren().remove(previous); validate(this, tree); parent.updateRemove(tree); // 同后面节点合并 } else if (next != null && (next.getChildren().size() <= tree.getOrder() / 2 || next.getChildren().size() <= 2)) { for (int i = 0; i < next.getChildren().size(); i++) { INode child = next.getChildren().get(i); children.add(child); child.setParent(this); } next.setChildren(null); next.setEntries(null); next.setParent(null); parent.getChildren().remove(next); validate(this, tree); parent.updateRemove(tree); } } } } } /\*\* \* 删除一棵树上的key \* @param key \* @param tree \*/ public void remove(Comparable key, IBPlusTree tree){ //如果是叶子节点 if (isLeaf){ //如果不包含该关键字，则直接返回 if (!contains(key)){ return; } //如果既是叶子节点又是跟节点，直接删除 if (isRoot) { remove(key); }else { //如果关键字数大于M / 2，直接删除 if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) { remove(key); }else { //如果自身关键字数小于M / 2，并且前节点关键字数大于M / 2，则从其处借补 if (previous != null && previous.getEntries().size() > tree.getOrder() / 2 && previous.getEntries().size() > 2 && previous.getParent() == parent) { int size = previous.getEntries().size(); Entry entry = previous.getEntries().get(size - 1); previous.getEntries().remove(entry); //添加到首位 entries.add(0, entry); remove(key); //如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补 }else if (next != null && next.getEntries().size() > tree.getOrder() / 2 && next.getEntries().size() > 2 && next.getParent() == parent) { Entry entry = next.getEntries().get(0); next.getEntries().remove(entry); //添加到末尾 entries.add(entry); remove(key); //否则需要合并叶子节点 }else { //同前面节点合并 if (previous != null && (previous.getEntries().size() <= tree.getOrder() / 2 || previous.getEntries().size() <= 2) && previous.getParent() == parent) { for (int i = previous.getEntries().size() - 1; i >=0; i--) { //从末尾开始添加到首位 entries.add(0, previous.getEntries().get(i)); } remove(key); previous.setParent(null); previous.setEntries(null); parent.getChildren().remove(previous); //更新链表 if (previous.getPrevious() != null) { INode temp = previous; temp.getPrevious().setNext(this); previous = temp.getPrevious(); temp.setPrevious(null); temp.setNext(null); }else { tree.setHead(this); previous.setNext(null); previous = null; } //同后面节点合并 }else if(next != null && (next.getEntries().size() <= tree.getOrder() / 2 || next.getEntries().size() <= 2) && next.getParent() == parent){ for (int i = 0; i < next.getEntries().size(); i++) { //从首位开始添加到末尾 entries.add(next.getEntries().get(i)); } remove(key); next.setParent(null); next.setEntries(null); parent.getChildren().remove(next); //更新链表 if (next.getNext() != null) { INode temp = next; temp.getNext().setPrevious(this); next = temp.getNext(); temp.setPrevious(null); temp.setNext(null); }else { next.setPrevious(null); next = null; } } } } parent.updateRemove(tree); } //如果不是叶子节点 }else { //如果key小于等于节点最左边的key，沿第一个子节点继续搜索 if (key.compareTo(entries.get(0).getKey()) <= 0) { children.get(0).remove(key, tree); //如果key大于节点最右边的key，沿最后一个子节点继续搜索 }else if (key.compareTo(entries.get(entries.size()-1).getKey()) >= 0) { children.get(children.size()-1).remove(key, tree); //否则沿比key大的前一个子节点继续搜索 }else { for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i+1).getKey().compareTo(key) > 0) { children.get(i).remove(key, tree); break; } } } } } /\*\* 判断当前节点是否包含该关键字\*/ /\*\* \* \* @param key \* @return \*/ protected boolean contains(Comparable key) { for (Entry entry : entries) { if (entry.getKey().compareTo(key) == 0) { return true; } } return false; } /\*\* 插入到当前节点的关键字中\*/ /\*\* \* \* @param key \* @param obj \*/ protected void insertOrUpdate(Comparable key, Object obj){ Entry entry = new SimpleEntry(key, obj); //如果关键字列表长度为0，则直接插入 if (entries.size() == 0) { entries.add(entry); return; } //否则遍历列表 for (int i = 0; i < entries.size(); i++) { //如果该关键字键值已存在，则更新 if (entries.get(i).getKey().compareTo(key) == 0) { entries.get(i).setValue(obj); return; //否则插入 }else if (entries.get(i).getKey().compareTo(key) > 0){ //插入到链首 if (i == 0) { entries.add(0, entry); return; //插入到中间 }else { entries.add(i, entry); return; } } } //插入到末尾 entries.add(entries.size(), entry); } /\*\* 删除节点\*/ /\*\* \* 函数的重写：根据key来进行删除 \* @param key \*/ protected void remove(Comparable key){ int index = -1; for (int i = 0; i < entries.size(); i++) { if (entries.get(i).getKey().compareTo(key) == 0) { index = i; break; } } if (index != -1) { entries.remove(index); } } /\*\* \* 重写这个toString() 函数 \*/ public String toString(){ StringBuilder sb = new StringBuilder(); sb.append("isRoot: "); sb.append(isRoot); sb.append(", "); sb.append("isLeaf: "); sb.append(isLeaf); sb.append(", "); sb.append("keys: "); for (Entry entry : entries){ sb.append(entry.getKey()); sb.append(", "); } sb.append(", "); // 可以直接返回一个对象的属性 return sb.toString(); } }

【java进阶】利用Java实现B+树的添加和删除源码