定义一个接口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();
}
}
评论
填写昵称与邮箱即可评论，无需登录。