bptree.java

一个简单的数据库

        int currec = node.maxLE(rec.getSearchKey());
        if (node.isLeaf()) {
            tmp = new Pair(rec.getSearchKey(), rec);
        } else {
            tmp = insertHelp((BpNode) node.recArray[currec].pointer, rec);
            if (tmp == null) {
                return null;
            }
        }
        if (!node.isFull()) {
            node.addAfter(currec, tmp);
        } else {
            BpNode tp = node.split(currec, tmp);

            if (tp.isLeaf()) {
                return new Pair(tp.recArray[1].key, tp);
            } else {
                Pair maxP = node.recArray[--node.count];	//	删除了此Pair

                node.recArray[node.count] = null;
                tp.recArray[0].pointer = maxP.pointer;
                return new Pair(maxP.key, tp);
            }
        }
        return null;
    }
    public Bucket find(Comparable k) {
        int currec = root.maxLE(k);
        BpNode current = root;

        while (!current.isLeaf()) {
            current = (BpNode) current.recArray[currec].pointer;
            currec = current.maxLE(k);
        }
        if (!current.recArray[currec].key.equals(k)) {
            return null;
        }
        return (Bucket) current.recArray[currec].pointer;
    }
    BpNode getNode(Comparable k) {
        int currec = root.maxLE(k);
        BpNode current = root;

        while (!current.isLeaf()) {
            current = (BpNode) current.recArray[currec].pointer;
            currec = current.maxLE(k);
        }
        return current;
    }
    ArrayList getAE(BpNode bpn, int startIndex) {
        ArrayList recArr = new ArrayList();
        while (bpn != null) {
            for (int i = startIndex; i < bpn.count; i++) {
                Bucket ele = (Bucket) bpn.recArray[i].pointer;
                for (int j = 0; j < ele.m_pointers.size(); j++) {
                    recArr.add(ele.m_pointers.get(j));
                }
            }
            bpn = bpn.rightSibling;
        }
        return recArr;
    }
    ArrayList getBE(BpNode bpn, int endIndex) {
        ArrayList recArr = new ArrayList();
        BpNode firstNode = firstLeaf();
        while (firstNode != bpn) {
            for (int i = 1; i < firstNode.count; i++) {
                Bucket ele = (Bucket) firstNode.recArray[i].pointer;
                for (int j = 0; j < ele.m_pointers.size(); j++) {
                    recArr.add(ele.m_pointers.get(j));
                }
            }
            firstNode = firstNode.rightSibling;
        }
        for (int i = 1; i <= endIndex; i++) {
            Bucket ele = (Bucket) bpn.recArray[i].pointer;
            for (int j = 0; j < ele.m_pointers.size(); j++) {
                recArr.add(ele.m_pointers.get(j));
            }
        }
        return recArr;
    }
    public ArrayList findE(Comparable k) {
        Bucket ele = find(k);
        if (ele == null) {
            return null;
        }
        return ele.m_pointers;
    }
    public ArrayList findAE(Comparable k) {
        BpNode current = getNode(k);
        int currec = current.maxLE(k);
        if (!current.recArray[currec].key.equals(k)) {
            currec++;
            if (currec == current.count) {
                currec = 1;
                current = current.rightSibling;
                if (current == null) {
                    return null;
                }
            }
        }
        return getAE(current, currec);
    }
    public ArrayList findA(Comparable k) {
        BpNode current = getNode(k);
        int currec = current.maxLE(k);
        currec++;
        if (currec == current.count) {
            currec = 1;
            current = current.rightSibling;
            if (current == null) {
                return null;
            }
        }
        return getAE(current, currec);
    }
    public ArrayList findBE(Comparable k) {
        BpNode current = getNode(k);
        if (current == null) {
            return null;
        }
        int currec = current.maxLE(k);
        return getBE(current, currec);
    }
    public ArrayList findB(Comparable k) {
        BpNode current = getNode(k);
        int currec = current.maxLE(k);
        if (current.recArray[currec].key.equals(k)) {
            currec--;
            if (currec <= 0) {
                if (current == firstLeaf()) {
                    return null;
                }
                current = current.leftSibling;
                currec = current.recArray.length - 1;
            }
        }
        return getBE(current, currec);
    }
    BpNode firstLeaf() {
        BpNode curr = root;
        while (!curr.isLeaf()) {
            curr = (BpNode) curr.recArray[0].pointer;
        }
        return curr;
    }
    public boolean isFirstChild(BpNode node, Comparable k) {
        BpNode curr = root;

        int currec = curr.maxLE(k);
        while (curr.recArray[currec].pointer != node) {
            curr = (BpNode) curr.recArray[currec].pointer;
            currec = curr.maxLE(k);
        }
        return (currec == 0);

    }
    void print() {
        if (root == null) {
            System.out.println("Empty tree");
            return;
        }

        BpNode curr = firstLeaf();

        while (curr != null) {
            System.out.println(curr);
            curr = curr.rightSibling;
        }
        System.out.println("========================");
    }
    void printRev() {
        BpNode curr = firstLeaf();

        while (curr.rightSibling != null) {
            curr = curr.rightSibling;
        }
        while (curr != null) {
            System.out.println(curr);
            curr = curr.leftSibling;
        }
        System.out.println("===========");
    }
    public String toString() {
        if (root == null) {
            return "Empty Tree!";
        }
        String res = "";
        BpNode first = root;
        Object tmp = first;

        while (tmp instanceof BpNode) {
            first = (BpNode) tmp;
            res += first + "\t";
            BpNode curr = first.rightSibling;
            while (curr != null) {
                res += curr + "\t";
                curr = curr.rightSibling;
            }
            res += "\n";
            tmp = first.recArray[0].pointer;
        }
        return res;
    }
    static void f1() {
        int[] arr = {
            1, 2, 15, 7, 6, 3, 8, 10, 9, 11, 14, 16, 17,
        };
        BpTree tree = new BpTree();

        for (int i = 0; i < arr.length; i++) {
            tree.insert(arr[i]);
        }
        System.out.println(tree);


        for (int i = 0; i < 20; i++) {
            System.out.println(tree.find(i));
        }
    }
    static void f2() {
        BpTree tree = new BpTree();

        int[] arr = RandomArray.randomArr(20);

        for (int i = 0; i < arr.length; i++) {
            tree.insert(arr[i]);
        }
        tree.print();
        System.out.println("================");
        tree.printRev();
    }
    static void f3() {
        BpTree tree = new BpTree(7, "t", "em");

        int test = 1000;
        int[] arr1 = RandomArray.randomArr(test);
        int[] arr2 = RandomArray.randomArr(test);

        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + ",");
        }
        System.out.println();

        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + ",");
        }
        System.out.println();
        for (int i = 0; i < arr1.length; i++) {
            tree.insert(arr1[i]);
        }
        System.out.println(tree);
        for (int i = 0; i < arr2.length; i++) {
            tree.remove(arr2[i]);
        }
        System.out.println(tree);
    }
    static void f4() {
        BpTree tree = new BpTree();

        int[] arr1 = {34, 9, 43, 26, 12, 14, 31, 27, 37, 35, 23, 47, 19, 39, 22, 44, 16, 7, 18, 24, 40, 6, 11, 41, 21, 49, 32, 5, 28, 1, 17, 3, 45, 10, 42, 33, 25, 30, 15, 50, 36, 8, 38, 13, 4, 29, 46, 20, 48, 2};
        int[] arr2 = {31, 17, 35, 42, 7, 16, 33, 13, 19, 12, 4, 41, 50, 2, 21, 24, 23, 47, 14, 28, 25, 49, 38, 9, 18, 27, 22, 48, 8, 36, 44, 37, 30, 40, 39, 32, 46, 10, 45, 6, 11, 20, 15, 43, 1, 34, 3, 29, 26, 5};

        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + ",");
        }
        System.out.println();

        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + ",");
        }
        System.out.println();

        for (int i = 0; i < arr1.length; i++) {
            tree.insert(arr1[i]);
        }
        System.out.println(tree);

        for (int i = 0; i < arr2.length; i++) {
            tree.remove(arr2[i]);
            System.out.println(tree);
        }
        System.out.println(tree);
    }
    static void f5() {
        BpTree tree = new BpTree();

        int[] arr = RandomArray.randomArr(100);

        for (int i = 0; i < arr.length; i++) {
            tree.insert(arr[i]);
        }
        tree.print();
        System.out.println(tree);

    }
    static void f6() {
        BpTree tree = new BpTree(8, "te", "m");
        String[] arr1 = RandomArray.randomStrArr();
        String[] arr2 = RandomArray.randomStrArr();

        for (int i = 0; i < arr1.length; i++) {
            System.out.print(arr1[i] + "\t");
        }
        for (int i = 0; i < arr1.length; i++) {
            tree.insert(arr1[i]);
            System.out.println(tree);
        }
        for (int i = 0; i < arr2.length; i++) {
            Bucket tmp = tree.find(arr2[i]);
            System.out.println("" + i + ": " + tmp);
        }
    }
    public static void main(String[] args) {
        f6();
    }
}
class RandomArray implements Serializable {

    static String[] initArr1 = {
        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t",
        "u", "v", "w", "x", "y", "z"
    };
    static String[] initArr2 = {
        "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
    };
    static String[] initArr;
    static {
        initArr = new String[initArr1.length * initArr2.length];
        int k = 0;
        for (int i = 0; i < initArr1.length; i++) {
            for (int j = 0; j < initArr2.length; j++) {
                initArr[k++] = initArr1[i] + initArr2[j];
            }
        }
    }
    static int[] randomArr(int size) {
        int[] arr = new int[size];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
        for (int i = 0; i < size * 10; i++) {
            int r1 = (int) (Math.random() * size);
            int r2 = (int) (Math.random() * size);

            int tmp = arr[r1];
            arr[r1] = arr[r2];
            arr[r2] = tmp;
        }
        return arr;
    }
    static String[] randomStrArr() {
        String[] arr = initArr;
        for (int i = 0; i < arr.length * 10; i++) {
            int r1 = (int) (Math.random() * arr.length);
            int r2 = (int) (Math.random() * arr.length);

            String tmp = arr[r1];
            arr[r1] = arr[r2];
            arr[r2] = tmp;
        }
        return arr;
    }
}