/* BPlusTree.java
* Support class for Pyramid Technique
* Capable of doing insertion, search, but not deletion
* Modified from jwang01 's work as found @ http://en.wikibooks.org/wiki/Transwiki:B+_Tree_Java_Implementation
* Fay Pan 2007
* Computer Science, University of Otago
*/
public class BPlusTree{
private Node root;
private int h = 0; // height of the tree
private final int order;
private final int max_inner_keys;
private final int min_inner_keys;
private final int max_inner_pointers;
private final int min_inner_pointers;
private final int max_leaf_keys;
private final int min_leaf_keys;
private final int max_leaf_points;
private final int min_leaf_points;
private final int dim;
private int counter =0;//count how many nodes in the tree and link
private int seek_time;
private static int total=0;
/*constructor*/
// t is the order of the tree
public BPlusTree(int t, int d){
dim =d;
h = 0;
order = t;
min_inner_keys = min_leaf_keys = min_leaf_points = t;
max_inner_keys = max_leaf_keys = max_leaf_points = 2*t;
min_inner_pointers = t+1;
max_inner_pointers = 2*t +1;
/*
min_keys = t;
min_points = 2*t;
max_keys = 2*t;
max_points = 2*t + 1;*/
root = new LNode();
}
public BPlusTree(int l, int i, int d){
dim = d;
h=0;
order = i;
min_inner_keys = i;
max_inner_keys = 2*i;
min_inner_pointers = i+1;
max_inner_pointers = 2*i +1;
min_leaf_points = min_leaf_keys = l;
max_leaf_points = max_leaf_keys = 2*l;
root = new LNode();
}
public void print(){
Node node = root;
int d=h, idx=0;
while( d-- != 0 ) {//need to traverse down to the leaf
INode inner = (INode) node;
node = inner.children[idx];
}
System.out.println(d);
//We are @ leaf after while loop
LNode leaf= (LNode) node;
//for(int i =0; i< max_points; i++){
while(leaf!=null){
System.out.println(leaf.num);
for(int j = 0; j < leaf.num; j++){//print the keys and points in one leaf node
System.out.println("key = " + leaf.keys[j]);
for(int k = 0; k < dim; k++){
System.out.print(leaf.points[j][k]+ " ");
}
}
if(leaf.next!=null) {
leaf=leaf.next;
//System.out.println("link to a new leaf");
}else break;
//System.out.println(leaf.num);
}
}
public void insert(double key, double[] point){
//System.out.println("insert key=" + key);
InsertResult result = new InsertResult();
boolean split;
if(h==0){// The root is a leaf node
split= insertLeaf((LNode)root, key, point, result);
} else {// The root is an inner node
split= insertInner((INode)root, h, key, point, result);
}
if(split) {
// The old root was splitted in two parts.
// We have to create a new root pointing to them
total = total +2;
h++;
root= new INode();
INode _root = (INode) root;
_root.num = 1;
_root.keys[0] = result.key;
_root.children[0] = result.left;
_root.children[1] = result.right;
}
//id++;
}
public static int getTotal(){
return total;
}
/*
* Looks for the given key. If it is not found, it returns false,
* if it is found, it returns true and copies the associated value
* unless the pointer is null.
*/
public boolean find(double key, double[] point) {
seek_time = 0;
double[][] result=new double[100][dim];
Node node = root;
int d=h, idx, n=0;
while( d-- != 0 ) {//need to traverse down to the leaf
INode inner = (INode) node;
idx = getInnerLoc(key, inner.keys, inner.num);
node = inner.children[idx];
seek_time++;
}
//We are @ leaf after while loop
LNode leaf= (LNode) node;
idx = getLeafLoc(key, leaf.keys, leaf.num);
if(idx<leaf.num && leaf.keys[idx] == key) {
while(leaf.keys[idx] == key){
result[n] = leaf.points[idx];
n++;
if(idx<=leaf.num) idx++;
else{
leaf = leaf.next;
seek_time++;
idx=0;
}
}
//search for point in result array
int valid = 0;
for(int i = 0; i < result.length; i++){
for(int j =0; j < dim; j++){
if(result[i][j] == point[j]) valid ++;
}
if (valid==3) return true;
valid=0;
}
}else{
return false;
}
return false;
}
public int getTime(){
return seek_time;
}
/*
* Looks for the given key. If it is not found, it returns false,
* if it is found, it returns true and copies the associated value
* unless the pointer is null.
*/
public ResultList findRange(double key, double high) {
seek_time=0;
ResultNode no;
ResultList r = new ResultList();
ResultNode pos = new ResultNode();
//double[][] result=new double[1300][dim];
Node node = root;
int d=h, idx, n=0;
while( d-- != 0 ) {//need to traverse down to the leaf
INode inner = (INode) node;
idx = getInnerLoc(key, inner.keys, inner.num);
node = inner.children[idx];
seek_time++;
}
//We are @ leaf after while loop
LNode leaf= (LNode) node;
idx = getLeafLoc(key, leaf.keys, leaf.num);
if(idx<leaf.num && leaf.keys[idx] >= key) {//start from the low key
int flag =0;
while(leaf.keys[idx] <= high){//end with high key
if(idx<leaf.num-1 && flag==0){//if it is in the middle of a bucket
no = new ResultNode(leaf.keys[idx], leaf.points[idx]);
if(r.header.k==0) {
//System.out.println("Start");
r = new ResultList(no);
r.inc();
pos = r.header;
} else {
r.inc();
pos.next = no;
pos = pos.next;
}
n++;
idx++;
}
else if(idx==leaf.num-1 && flag ==0){// if it reaches the end of a bucket
//System.out.println("last");
no = new ResultNode(leaf.keys[idx], leaf.points[idx]);
if(r.header.p==null) {
r = new ResultList(no);
r.inc();
pos = r.header;
} else {
r.inc();
pos.next = no;
pos = pos.next;
}
n++;
flag = 1;
} else {//go to the next bucket
if(leaf.next!=null){
//System.out.println("Jump");
leaf = leaf.next;
seek_time++;
idx=0;
flag = 0;
} else {
break;
}
}
}
return r;
}else{
return null;
}
}
//return the position where the 'key' should be inserted in a leaf node
private static int getLeafLoc(double key, double[] keys, int num){
//linear search
int i = 0;
while((i < num) && (keys[i] < key)){
i++;
}
return i;
}
//return the position where the 'key' should be inserted in an inner node
private static int getInnerLoc(double key, double[] keys, int num){
int i = 0;
while((i < num) && (keys[i] <= key)){
i++;
}
return i;
}
protected boolean insertLeaf(LNode node, double key, double[] point, InsertResult result){
boolean split = false;
//linear search
int idx = getLeafLoc(key, node.keys, node.num);
if(node.num == max_leaf_keys){//the node was full, we must split it
LNode sibling = new LNode();
sibling.num = node.num - min_leaf_keys;
int sNum = sibling.num;
for(int j = 0; j < sNum; j++){
int mj = min_leaf_keys + j;
sibling.keys[j] = node.keys[mj];
for(int k = 0; k < dim; k++)
sibling.points[j][k] = node.points[mj][k];
}
node.num = min_leaf_keys;
if(idx < min_leaf_keys){
//inserted element goes to left sibling
insertLeafNonfull(node, key, point, idx);
} else {
//inserted element goes to right sibling
insertLeafNonfull(sibling, key, point, idx - min_leaf_keys);
}
//nitofy the parent about the split
split = true;
result.key = sibling.keys[0];
//System.out.println(result.key);
result.left = node;
result.right = sibling;
sibling.next = node.next;
node.next = sibling;
//System.out.println(node.next.num+ " " +sibling.num);
//verified the linked list works fine
total ++; //increment total number of nodes by 1
} else {// the node is not full
insertLeafNonfull(node, key, point, idx);
}
return split;
}
private void insertLeafNonfull(LNode node, double key, double[] point, int idx){
for(int i = node.num; i > idx; i--){
node.keys[i] = node.keys[i-1];
for(int k = 0; k < dim; k++)
node.points[i][k] = node.points[i-1][k];
}
node.keys[idx] = key;
for(int k = 0; k < dim; k++) node.points[idx][k] = point[k];
node.num++;
}
protected boolean insertInner(INode node, int height, double key, double[] point, InsertResult result){
//early split if node is full
boolean split = false;
if(node.num == max_inner_keys){//split
INode sibling = new INode();
int sNum = sibling.num = node.num - min_inner_keys;
for(int i = 0; i < sNum; i++){
sibling.keys[i] = node.keys[min_inner_keys + i];
sibling.children[i] = node.children[min_inner_keys + i];
}
sibling.children[sNum] = node.children[node.num];
node.num = min_inner_keys - 1; //inner node's key doesn't repeat itself
split = true;
result.key = node.keys[min_inner_keys - 1];
result.left = node;
result.right = sibling;
//insert into the appropriate sibling
if(key < result.key){
insertInnerNonfull(node, height, key, point);
} else {
insertInnerNonfull(sibling, height, key, point);
}
total ++; //increment total number of nodes by 1
} else { //no split
insertInnerNonfull(node, height, key, point);
}
return split;
}
private void insertInnerNonfull(INode node, int height, double key, double[] point){
//linear search
int idx = getInnerLoc(key, node.keys, node.num);
InsertResult result = new InsertResult();
boolean split;
if(height -1 == 0){ //the children are leaf
split = insertLeaf((LNode)node.children[idx], key, point, result);
} else { //the children are inner
INode child = (INode) node.children[idx];
split = insertInner(child, height-1, key, point, result);
}
if(split){
if(idx == node.num){
//insertion at the rightmost key
node.keys[idx] = result.key;
node.children[idx] = result.left;
node.children[idx+1] = result.right;
node.num++;
} else {
//insertion not at the rightmost key
node.children[node.num+1] = node.children[node.num];
for(int i = node.num; i>idx; i--){
node.children[i] = node.children[i-1];
node.keys[i] = node.keys[i-1];
}
node.children[idx] = result.left;
node.children[idx+1] = result.right;
node.keys[idx] = result.key;
node.num++;
}
}
}
class LNode extends Node{
double[][] points= null;
LNode next;
public LNode(){
type = LEAF;
keys = new double[max_leaf_keys];
points = new double[max_leaf_points][dim];
next = null;
}
}
class INode extends Node{
Node[] children = null;
public INode(){
type = INNER;
keys = new double[max_inner_keys];
children = new Node[max_inner_pointers];
}
};
class InsertResult{
double key;
Node left;
Node right;
public InsertResult(){
}
public InsertResult(double k, Node l, Node r){
key = k;
left = l;
right = r;
}
}
}
posted on 2007-10-17 15:20
Fay 閱讀(1540)
評論(5) 編輯 收藏