bptree.java

一个简单的数据库

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package indexManager;

/**
 *
 * @author outlaw
 */
import java.io.Serializable;
import java.util.*;

class Pair implements Serializable {
    Comparable key;
    Object pointer;
    public Pair(Comparable k, Object p) {
        key = k;
        pointer = p;
    }
    public String toString() {
        return "[" + key + ", " + pointer + "]";
    }
}
class BpNode implements Serializable {
    private boolean isLeaf;
    public static boolean LEAF = true;
    public static boolean NONLEAF = false;
    private final int MAXREC;
    public int count;
    Pair[] recArray;
    public BpNode leftSibling,  rightSibling;

    public BpNode(boolean leaf, int max) //	leaf == 1:leaf node ; leaf == 0:non_leaf node
    {
        MAXREC = max;
        recArray = new Pair[MAXREC];
        recArray[0] = new Pair(Integer.MIN_VALUE, null);
        count = 1;
        leftSibling = rightSibling = null;
        
        if (leaf == LEAF) {
            isLeaf = true;
        } else {
            isLeaf = false;
        }
    }
    public int maxLE(Comparable tar) {
        int result;
        for (result = 1; result < count; result++) {
            if (recArray[result].key.compareTo(tar) > 0) {
                break;
            }
        }
        return result - 1;
    }
    public void merge(BpNode other) {
        if (isLeaf) {
            for (int i = 0; i < other.count - 1; i++) {
                this.recArray[count + i] = other.recArray[i + 1];
            }
            this.count = this.count + other.count - 1;
            other.count = 1;
            this.rightSibling = other.rightSibling;
            if (other.rightSibling != null) {
                other.rightSibling.leftSibling = this;
            }
        } else {
            BpNode first = (BpNode) other.recArray[0].pointer;
            BpNode current = first;
            while (!current.isLeaf) //	找到other节点一下最小的key值
            {
                current = (BpNode) current.recArray[0].pointer;
            }
            Pair tmp = new Pair(current.recArray[1].key, first);
            this.recArray[count] = tmp;
            for (int i = 0; i < other.count - 1; i++) {
                this.recArray[count + i + 1] = other.recArray[i + 1];
            }
            this.count = this.count + other.count;
            other.count = 1;
            this.rightSibling = other.rightSibling;
            if (other.rightSibling != null) {
                other.rightSibling.leftSibling = this;
            }
        }
    }
    public void shuffle(BpNode other) {
        if (isLeaf) {
            Pair[] bigArr = new Pair[2 * MAXREC];
            int i;
            for (i = 0; i < this.count - 1; i++) {
                bigArr[i] = this.recArray[i + 1];
            }
            for (int j = 0; j < other.count - 1; j++) {
                bigArr[j + i] = other.recArray[j + 1];
            }
            int max = this.count + other.count - 2;
            BpNode new1 = new BpNode(this.isLeaf, this.MAXREC);
            BpNode new2 = new BpNode(this.isLeaf, this.MAXREC);
            int k;
            for (k = 0; k < (max + 1) / 2; k++) {
                new1.recArray[k + 1] = bigArr[k];
                new1.count++;
            }
            for (int l = 0; l < max / 2; l++) {
                new2.recArray[l + 1] = bigArr[l + k];
                new2.count++;
            }
            this.count = new1.count;
            this.recArray = new1.recArray;
            other.count = new2.count;
            other.recArray = new2.recArray;
        } else {
            Pair[] bigArr = new Pair[2 * MAXREC];
            for (int i = 0; i < this.count; i++) {
                bigArr[i] = this.recArray[i];
            }
            BpNode first = (BpNode) other.recArray[0].pointer;
            BpNode current = first;
            while (!current.isLeaf) {
                current = (BpNode) current.recArray[0].pointer;
            }
            Pair tmp = new Pair(current.recArray[1].key, first);
            bigArr[this.count] = tmp;
            for (int i = 0; i < other.count - 1; i++) {
                bigArr[this.count + 1 + i] = other.recArray[i + 1];
           }
            int max = this.count + other.count;
            BpNode new1 = new BpNode(this.isLeaf, this.MAXREC);
            BpNode new2 = new BpNode(this.isLeaf, this.MAXREC);
            int i;
            new1.count--;
            for (i = 0; i < (max + 1) / 2; i++) {
                new1.recArray[i] = bigArr[i];
                new1.count++;
            }
            for (int l = 0; l < max / 2; l++) {
                new2.recArray[l + 1] = bigArr[l + i];
                new2.count++;
            }
            Pair temp = new1.recArray[--new1.count];
            new1.recArray[new1.count] = null;
            new2.recArray[0].pointer = temp.pointer;
            this.count = new1.count;
            this.recArray = new1.recArray;
            other.count = new2.count;
            other.recArray = new2.recArray;
        }
    }
    public void addAfter(int currec, Pair p) {
        for (int i = count; i > currec + 1; i--) {
            recArray[i] = recArray[i - 1];
        }
        recArray[currec + 1] = p;
        count++;
    }
    public void deleteAt(int index) {
        for (int i = index; i < count - 1; i++) {
            recArray[i] = recArray[i + 1];
        }
        recArray[--count] = null;
    }
    public BpNode split(int index, Pair tar) {
        Pair[] bigArr = new Pair[2 * MAXREC];
        int i;
        for (i = 0; i < count - 1; i++) {
            if (i == index) {
                break;
            } else {
                bigArr[i] = recArray[i + 1];
            }
        }
        bigArr[i] = tar;
        for (int j = i + 1; j < recArray.length; j++) {
            bigArr[j] = recArray[j];
        }
        BpNode new1 = new BpNode(this.isLeaf, this.MAXREC);
        BpNode new2 = new BpNode(this.isLeaf, this.MAXREC);
        int k;
        for (k = 0; k < MAXREC / 2; k++) {
            new1.recArray[k + 1] = bigArr[k];
            new1.count++;
        }
        for (int l = k; l < MAXREC; l++) {
            new2.recArray[l - k + 1] = bigArr[l];
            new2.count++;
        }
        new1.recArray[0].pointer = this.recArray[0].pointer;
        new2.leftSibling = this;
        new2.rightSibling = this.rightSibling;
        if (this.rightSibling != null) {
            this.rightSibling.leftSibling = new2;
        }
        this.rightSibling = new2;
        this.count = new1.count;
        this.recArray = new1.recArray;
        return new2;
    }
    public String toString() {
        String res = "";
        for (int i = 1; i < count; i++) {
            res += recArray[i].key + ",";
        }
        return "『" + res.substring(0, res.lastIndexOf(',')) + "』";
    }
    public boolean canMerge(BpNode other) {
        if (isLeaf) {
            return (this.count + other.count - 1) <= MAXREC;
        } else {
            return (this.count + other.count) <= MAXREC;
        }
    }
    public boolean isLeaf() {
        return isLeaf;
    }
    public boolean isFull() {
        return count == MAXREC;
    }
    public boolean isBigEnough() {
        if (isLeaf) {
            return ((count - 1) >= MAXREC / 2);
        } else {
            return (count >= (MAXREC + 1) / 2);
        }
    }
}
public class BpTree implements Serializable {
    private BpNode root;
    final int DEGREE;
    String m_attr;
    String m_holder;
    public boolean m_dirty;

    public BpTree() {
        root = null;
        DEGREE = 4;
        m_dirty = true;
    }
    public BpTree(int degree, String n_attr, String n_holder) {
        root = null;
        DEGREE = degree;
        m_attr = n_attr;
        m_holder = n_holder;
        m_dirty = true;
    }
    public String getHolder() {
        return m_holder;
    }
    public String getAttr() {
        return m_attr;
    }
    public boolean isRootNull() {
        if (root == null) {
            return true;
        }
        return false;
    }
    public void insert(Comparable key) {
        Bucket tmp = new Bucket(key, null);
        insert(tmp);
    }
    public void insert(Bucket rec) {
        m_dirty = true;
        if (root == null) {
            root = new BpNode(BpNode.LEAF, DEGREE);
            Pair newP = new Pair(rec.getSearchKey(), rec);
            root.recArray[1] = newP;
            root.count++;
        } else {
            Pair p = insertHelp(root, rec);
            if (p != null) {
                BpNode tmp = new BpNode(BpNode.NONLEAF, DEGREE);
                tmp.recArray[0].pointer = root;
                tmp.recArray[1] = p;
                tmp.count++;
                root = tmp;
            }
        }
    }
    public void remove(Comparable k) {
        m_dirty = true;
        int currec = root.maxLE(k);
        if (root.isLeaf()) {
            if (root.recArray[currec].key.equals(k)) {
                root.deleteAt(currec);
            }
            if (root.count == 1) {
                root = null;			
            }
        } else {
            currec = removeHelp((BpNode) root.recArray[currec].pointer, k, currec);

            if (currec == -1) {
                return;
            } else if (((BpNode) root.recArray[currec].pointer).count > 1) {	
                BpNode current = (BpNode) root.recArray[currec].pointer;
                while (!current.isLeaf()) {
                    current = (BpNode) current.recArray[0].pointer;
                }
                root.recArray[currec].key =
                        current.recArray[1].key;
                return;
            }
            root.deleteAt(currec);
            if (root.count > 1) {
                return;
            } else 
            {
                root = (BpNode) root.recArray[0].pointer;
                return;
            }

        }
    }
    private int removeHelp(BpNode node, Comparable k, int thispos) {
        int currec = node.maxLE(k);
        if (node.isLeaf()) {
            if (!node.recArray[currec].key.equals(k)) {
                return -1;
            }
        } else {
            currec = removeHelp((BpNode) node.recArray[currec].pointer, k, currec);
            if (currec == -1) {
                return -1;
            } else if (((BpNode) node.recArray[currec].pointer).count > 1) {
                /*				
                node.recArray[currec].key =
                ((BpNode)node.recArray[currec].pointer).recArray[1].key;
                 */

                BpNode current = (BpNode) node.recArray[currec].pointer;

                while (!current.isLeaf()) {
                    current = (BpNode) current.recArray[0].pointer;
                }
                node.recArray[currec].key =
                        current.recArray[1].key;

                return -1;
            }
        }
        Comparable key = node.recArray[1].key;
        node.deleteAt(currec);
        if (node.isBigEnough()) {
            return -1;
        } else {
            if (isFirstChild(node, key)) {
                if (node.canMerge(node.rightSibling)) {
                    node.merge(node.rightSibling);
                    return thispos + 1;
                } else {
                    node.shuffle(node.rightSibling);
                    return thispos + 1;
                }

            } else if (node.canMerge(node.leftSibling)) {
                node.leftSibling.merge(node);
                return thispos;
            } else {
                node.leftSibling.shuffle(node);
                return thispos;
            }
        }
    }
    private Pair insertHelp(BpNode node, Bucket rec) {
        Pair tmp;	//	存放一个 key/pointer 对