B+ 树 Java 代码

2016-08-01 11:31:52 暂无评论阳光倾城算法与数据结构 698

B+ 树 java 代码

/*
* BPlusTree.java
* Support class for Pyramid Technique
* Capable of doing insertion, search, but not deletion
* Modified from jwang01 's work as found @ https://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;

    while(leaf!=null){
        System.out.println(leaf.num);

        System.out.println("key = " + leaf.keys[j]);

            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);

        while(leaf.keys[idx] == key){
        result[n] = leaf.points[idx];
        n++;

        else{
            leaf = leaf.next;
            seek_time++;
            idx=0;
        }
        }
        //search for point in result array
        int valid = 0;

            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);

        int flag =0;

            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;

        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;

        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;

        int mj = min_leaf_keys + j;
        sibling.keys[j] = node.keys[mj];

            sibling.points[j][k] = node.points[mj][k];
        }
        node.num = 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];

        node.points[i][k] = node.points[i-1][k];
    }
    node.keys[idx] = key;

    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;

        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

        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;
    }
    }
}