btree.java

开源的axion的数据库代码

        return buf.toString();
    }


    // private methods
    // ------------------------------------------------------------------------

    /**
     * Sets the fileId.
     */
    private void allocate() {
        setFileId(getRoot().getCounter());
        getRoot().setCounter(getFileId() + 1);
    }

    /**
     * Loads the counter file if it exists.
     * This sets the counter.  Only the root
     * should ever call this.
     */
    private void loadIdxCtr() throws IOException {
        File idxCtr = getCounterFile();
        if (!isRoot()) {
            //If this isn't the root, then there is a problem.
            _log.warn("Non root attempting to load counter file");
            return;
        }
        FileInputStream fin = null;
        ObjectInputStream in = null;
        try {
            fin = new FileInputStream(idxCtr);
            in = new ObjectInputStream(fin);
            setCounter(in.readInt());
        } catch (IOException e) {
            throw e;
        } finally {
            try {
                in.close();
            } catch (Exception e) {}
            try {
                fin.close();
            } catch (Exception e) {}
        }
    }

    /**
     * Saves out the counter file.  This should only
     * ever be called by the root.
     */
    private void saveIdxCtr() throws IOException {
        File idxCtr = getCounterFile();
        if (!isRoot()) {
            //If this isn't the root, then there is a problem.
            _log.warn("Non root attempting to save counter file");
            return;
        }
        FileOutputStream fout = null;
        ObjectOutputStream out = null;
        if (!idxCtr.exists()) {
            idxCtr.createNewFile();
        }
        // increment counter
        try {
            fout = new FileOutputStream(idxCtr);
            out = new ObjectOutputStream(fout);
            out.writeInt(getCounter());
        } catch (IOException e) {
            throw e;
        } finally {
            try {
                out.close();
            } catch (Exception e) {}
            try {
                fout.close();
            } catch (Exception e) {}
        }
    }

    private File getFileById(int fileid) {
        return new File(_idxDir, getName() + "." + fileid);
    }

    private File getCounterFile() {
        return new File(_idxDir, _idxName + ".ctr");
    }

    String getName() {
        return _idxName;
    }

    private IntList getKeys() {
        return _keys;
    }

    private void setKeys(IntList keys) {
        _keys = keys;
    }

    private IntList getValues() {
        return _vals;
    }

    private void setValues(IntList vals) {
        _vals = vals;
    }

    int getValue(int index) {
        return _vals.get(index);
    }

    private void setValue(int index, int val) {
        _vals.set(index, val);
    }

    private IntList getChildIds() {
        return _childIds;
    }

    private Map getLoadedChildren() {
        return _loadedChildren;
    }

    private int getCounter() {
        if (isRoot()) {
            return _counter;
        } else {
            return getRoot().getCounter();
        }
    }

    private void setCounter(int counter) {
        if (isRoot()) {
            _counter = counter;
        } else {
            getRoot().setCounter(counter);
        }
    }

    int getFileId() {
        return _fileId;
    }

    private void setFileId(int fileId) {
        _fileId = fileId;
    }

    private BTree getRoot() {
        return _root;
    }

    boolean isLeaf() {
        return (getChildIds().size() == 0);
    }

    private boolean isRoot() {
        return (getRoot() == this);
    }

    private void borrowLeft(int borrowLoc) throws IOException {
        BTree leftSibling = getChild(borrowLoc - 1);
        BTree rightSibling = getChild(borrowLoc);

        if (_log.isDebugEnabled()) {
            _log.debug("Doing borrow left at: " + borrowLoc);
            _log.debug("Left sibling: " + leftSibling);
            _log.debug("Right sibling: " + rightSibling);
        }

        //Add the upper key to as the first entry of the right sibling
        rightSibling.getKeys().add(0, getKey(borrowLoc - 1));
        rightSibling.getValues().add(0, getValues().get(borrowLoc - 1));

        //Make the upper node's key the last key from the left sibling
        getKeys().set(
            borrowLoc - 1,
            leftSibling.getKey(leftSibling.getKeys().size() - 1));
        getValues().set(
            borrowLoc - 1,
            leftSibling.getValues().get(leftSibling.getValues().size() - 1));

        //If the siblings aren't leaves, move the last child from the left to be the first on the right
        if (!leftSibling.isLeaf()) {
            rightSibling.addChild(
                0,
                leftSibling.getChild(leftSibling.getChildIds().size() - 1));
        }

        //Remove the last entry of the left sibling (now moved to upper node)
        leftSibling.getKeys().removeElementAt(leftSibling.getKeys().size() - 1);
        leftSibling.getValues().removeElementAt(leftSibling.getValues().size() - 1);
        if (!leftSibling.isLeaf()) {
            leftSibling.getChildIds().removeElementAt(
                leftSibling.getChildIds().size() - 1);
        }

        if (_log.isDebugEnabled()) {
            _log.debug("Left sibling after: " + leftSibling);
            _log.debug("Right sibling after: " + rightSibling);
        }
    }

    private void borrowRight(int borrowLoc) throws IOException {
        BTree leftSibling = getChild(borrowLoc);
        BTree rightSibling = getChild(borrowLoc + 1);

        if (_log.isDebugEnabled()) {
            _log.debug("Doing borrow right at: " + borrowLoc);
            _log.debug("Left sibling: " + leftSibling);
            _log.debug("Right sibling: " + rightSibling);
        }

        //Add the upper key to as the last entry of the left sibling
        leftSibling.getKeys().add(getKey(borrowLoc));
        leftSibling.getValues().add(getValues().get(borrowLoc));

        //Make the upper node's key the first key from the right sibling
        getKeys().set(borrowLoc, rightSibling.getKey(0));
        getValues().set(borrowLoc, rightSibling.getValues().get(0));

        //If the siblings aren't leaves, move the first child from the right to be the last on the left
        if (!leftSibling.isLeaf()) {
            leftSibling.addChild(rightSibling.getChild(0));
        }

        //Remove the first entry of the right sibling (now moved to upper node)
        rightSibling.getKeys().removeElementAt(0);
        rightSibling.getValues().removeElementAt(0);
        if (!rightSibling.isLeaf()) {
            rightSibling.getChildIds().removeElementAt(0);
        }

        if (_log.isDebugEnabled()) {
            _log.debug("Left sibling after: " + leftSibling);
            _log.debug("Right sibling after: " + rightSibling);
        }
    }

    private void mergeChildren(int mergeLoc, int key) throws IOException {
        if (_log.isDebugEnabled()) {
            _log.debug("Merging children at: " + mergeLoc);
        }
        BTree leftChild = getChild(mergeLoc);
        BTree rightChild = getChild(mergeLoc + 1);
        if (_log.isDebugEnabled()) {
            _log.debug("Left child: " + leftChild);
            _log.debug("Right child: " + rightChild);
        }

        //Move the key down to the left child
        leftChild.getKeys().add(key);
        leftChild.getValues().add(getValues().get(mergeLoc));

        //Copy the keys and values from the right to the left
        leftChild.getKeys().addAll(rightChild.getKeys());
        leftChild.getValues().addAll(rightChild.getValues());

        //If not a leaf copy the child pointers from right to left
        if (!leftChild.isLeaf()) {
            leftChild.addChildrenFrom(rightChild);
        }

        //Now remove the item from the upper node (since it's been put in left child)
        getKeys().removeElementAt(mergeLoc);
        getValues().removeElementAt(mergeLoc);
        getChildIds().removeElementAt(mergeLoc + 1);

        rightChild.getKeys().clear();
        rightChild.getValues().clear();
        rightChild.getChildIds().clear();

        if (_log.isDebugEnabled()) {
            _log.debug("Left child after: " + leftChild);
            _log.debug("Right child after: " + rightChild);
        }
    }

    private void maybeCollapseTree() throws IOException {
        if (!isLeaf() && getKeys().size() <= 0) {
            _log.debug("Collapsing tree");
            BTree nodeToPromote = getChild(0);
            setKeys(nodeToPromote.getKeys());
            setValues(nodeToPromote.getValues());
            getChildIds().clear();
            addChildrenFrom(nodeToPromote);

            if (_log.isDebugEnabled()) {
                _log.debug("Tree after collapse: " + this);
            }
        }
    }

    /**
     * Finds and deletes the left most value from this subtree.
     * The key and value for the node is returned in the
     * parameters.  This also does the replacement as it unwraps.
     * 
     */
    private void getLeftMost(int[] keyParam, int valueParam[]) throws IOException {
        if (isLeaf()) {
            keyParam[0] = getKey(0);
            valueParam[0] = getValues().get(0);
        } else {
            getChild(0).getLeftMost(keyParam, valueParam);
        }
    }

    /**
     * Finds and deletes the right most value from this subtree.
     * The key and value for the node is returned in the
     * parameters.  This also does the replacement as it unwraps.
     * 
     */
    private void getRightMost(int[] keyParam, int valueParam[]) throws IOException {
        if (isLeaf()) {
            int max = size() - 1;
            keyParam[0] = getKey(max);
            valueParam[0] = getValues().get(max);
        } else {
            int max = getChildIds().size() - 1;
            getChild(max).getRightMost(keyParam, valueParam);
        }
    }

    private void insertNotfull(int key, int value) throws IOException {
        int i = findNearestKeyBelow(key);
        if (isLeaf()) {
            if (_log.isDebugEnabled()) {
                _log.debug("Node " + _fileId + " adding key " + key);
            }
            getKeys().add(i + 1, key);
            getValues().add(i + 1, value);
        } else {
            // recurse
            if (_log.isDebugEnabled()) {
                _log.debug("Node " + _fileId + " is internal so adding to child");
            }
            i++;
            BTree child = getChild(i);
            if (child.size() == _maxCap) {
                subdivideChild(i, child);
                if (key > getKey(i)) {
                    i++;
                }
            }
            getChild(i).insertNotfull(key, value);
        }
    }
    
    private void getAll(int key, IntListIteratorChain chain) throws IOException {
        int start = findNearestKeyAbove(key);
        if(isLeaf()) {
            int stop;
            for(stop = start; stop < size() && key == getKey(stop); stop++) { };
            chain.addIterator(getValues().subList(start,stop).listIterator());
        } else {
            int i = start;
            for(; i < size() && key == getKey(i); i++) {
                getChild(i).getAll(key,chain);
                chain.addIterator(getValues().get(i));
            }
            getChild(i).getAll(key,chain);
        }
    }

    private void getAllTo(int key, IntListIteratorChain chain) throws IOException {
        if(isLeaf()) {
            int endpoint = getKeys().indexOf(key);
            if(-1 != endpoint) {
                chain.addIterator(getValues().subList(0,endpoint).listIterator());
            } else {
                chain.addIterator(getValues().listIterator());
            }
        } else {
            // else we need to interleave my child nodes as well
            for(int i = 0; i < size() + 1; i++) {
                getChild(i).getAllTo(key,chain);
                if (i < size() && key > getKey(i)) {
                    chain.addIterator(getValues().get(i));
                } else { 
                    break;
                }
            }
        }
    }

    private void getAllFrom(int key, IntListIteratorChain chain) throws IOException {       
        int start = findNearestKeyAbove(key);
        if(isLeaf()) {
            chain.addIterator(getValues().subList(start,size()).listIterator());
        } else {
            for(int i = start; i < size() + 1; i++) {
                getChild(i).getAllFrom(key,chain);
                if(i < size()) {
                    chain.addIterator(getValues().get(i));
                } else {
                    break;
                }
            }
        }        
    }

    private void subdivideChild(int pivot, BTree child) throws IOException {
        if (_log.isDebugEnabled()) {
            _log.debug("Parent keys: " + getKeys().toString());
            _log.debug("Child keys: " + child.getKeys().toString());
        }
        int i = 0; // prepare index for loops below