btree.java

开源的axion的数据库代码

        _log.debug("Create new child to take excess data");
        BTree fetus = new BTree(_idxDir, getName(), _degree, _root, true);
        addChild(pivot + 1, fetus);

        _log.debug("Transfer (t-1) vals from existing child to new child");
        IntList sub = child.getKeys().subList(_degree, _maxCap);
        if (_log.isDebugEnabled()) {
            _log.debug("Moving keys " + sub.toString());
        }
        fetus.getKeys().addAll(sub);
        sub = child.getValues().subList(_degree, _maxCap);
        fetus.getValues().addAll(sub);
        if (!child.isLeaf()) {
            _log.debug("Transfer t children from existing child to new child");
            sub = child.getChildIds().subList(_degree, _maxCap + 1);
            fetus.addChildren(sub, child.getLoadedChildren());
            for (i = _maxCap; i >= _degree; i--) {
                child.getChildIds().removeElementAt(i);
            }
        }

        _log.debug("Add new pivot key that divides children");
        int pivotKey = child.getKey(_degree - 1);
        if (_log.isDebugEnabled()) {
            _log.debug("Pivot key: " + pivotKey);
        }
        int pivotVal = child.getValues().get(_degree - 1);
        getKeys().add(pivot, pivotKey);
        getValues().add(pivot, pivotVal);

        _log.debug("Trim child to new size");
        for (i = (_maxCap - 1); i > (_degree - 2); i--) {
            child.getKeys().removeElementAt(i);
            child.getValues().removeElementAt(i);
        }
    }

    /**
     * Writes the node file out.  This is differentiated from save in
     * that it doesn't save the entire tree or the counter file.
     */
    private void write() throws IOException {
        File idxFile = getFileById(getFileId());
        if (idxFile == null) {
            throw new NullPointerException("BTree must be allocated before writing out to disk");
        }
        if (!idxFile.exists()) {
            idxFile.createNewFile();
        }
        if (_log.isDebugEnabled()) {
            _log.debug("Writing out file " + idxFile);
            _log.debug(toString());
        }
        FileOutputStream fout = new FileOutputStream(idxFile);
        ObjectOutputStream out = new ObjectOutputStream(fout);
        out.writeInt(size());
        for (int i = 0; i < size(); i++) {
            out.writeInt(getKey(i));
            out.writeInt(getValues().get(i));
        }
        out.writeInt(getChildIds().size());
        for (int i = 0; i < getChildIds().size(); i++) {
            out.writeInt(getChildIds().get(i));
        }
        out.flush();
        out.close();
        fout.close();
    }

    /**
     * Reads in the node.  This doesn't read in the entire subtree,
     * which happens incrementally as files are needed.
     */
    private void read() throws IOException {
        File idxFile = getFileById(getFileId());
        if (_log.isDebugEnabled()) {
            _log.debug("Reading in file " + idxFile);
        }
        FileInputStream fin = new FileInputStream(idxFile);
        ObjectInputStream in = new ObjectInputStream(fin);
        int size = in.readInt();
        for (int i = 0; i < size; i++) {
            getKeys().add(in.readInt());
            getValues().add(in.readInt());
        }
        size = in.readInt();
        for (int i = 0; i < size; i++) {
            getChildIds().add(in.readInt());
        }
        in.close();
        fin.close();
    }

    boolean hasChild(int index) throws IOException {
        return (null != getChildOrNull(index));
    }

    private BTree getChildOrNull(int index) throws IOException {
        if (index >= getChildIds().size()) {
            return null;
        } else {
            Integer fileid = new Integer(getChildIds().get(index));
            if (_loadedChildren.get(fileid) == null) {
                _loadedChildren.put(
                    fileid,
                    new BTree(_idxDir, getName(), _degree, fileid.intValue(), _root));
            }
            return (BTree)_loadedChildren.get(fileid);
        }
    }

    /** @deprecated */
    BTree getChild(int index) throws IOException {
        BTree value = getChildOrNull(index);
        if(null == value) {
            throw new IOException("Node " + _fileId + " has no child at index " + index);
        } else {
            return value;
        }
    }

    private void addChild(BTree child) {
        getChildIds().add(child.getFileId());
        _loadedChildren.put(new Integer(child.getFileId()), child);
    }

    private void addChild(int index, BTree child) {
        getChildIds().add(index, child.getFileId());
        _loadedChildren.put(new Integer(child.getFileId()), child);
    }

    private void addChildrenFrom(BTree tree) {
        addChildren(tree.getChildIds(), tree.getLoadedChildren());
    }

    private void addChildren(IntList childIds, Map children) {
        IntIterator iter = childIds.iterator();
        while (iter.hasNext()) {
            int fileid = iter.next();
            addChild((BTree)children.get(new Integer(fileid)));
        }
    }

    boolean isValid() throws IOException {
        return isValid(true);
    }

    private boolean isValid(boolean isRoot) throws IOException {
        //Check to make sure that the node isn't an empty branch
        if (!isLeaf() && (size() == 0)) {
            _log.warn("INVALID: " + this.toString());
            _log.warn("Node has no keys and " + getChildIds().size() + " children");
            return false;
        }
        //Check to make sure that the node has enough children
        if (!isRoot && getKeys().size() < _degree - 1) {
            _log.warn("INVALID: " + this.toString());
            _log.warn(
                "Node has only " + getKeys().size() + " keys for a degree of " + _degree);
            return false;
        }
        //Check to make sure that there aren't too many children for the number of entries
        if (!isLeaf()
            && (getChildIds().size() != getKeys().size() + 1
                || getKeys().size() != getValues().size())) {
            _log.warn("INVALID: " + this.toString());
            _log.warn("child ids: " + getChildIds().size());
            _log.warn("keys: " + getKeys().size());
            _log.warn("values: " + getValues().size());
            return false;
        }
        //Check all of the children
        if (!isLeaf()) {
            for (int i = 0; i < getChildIds().size(); i++) {
                if (!getChild(i).isValid(false)) {
                    return false;
                }
            }
        }
        return true;
    }

    private int findNearestKeyBelow(int key) {
        //Short circuit
        if (size() == 0) {
            return -1;
        } else if (getKey(size() - 1) <= key) {
            return size() - 1;
        } else if (getKey(0) > key) {
            return -1;
        }

        // do a binary search for the key
        // on exit from this loop, cur will either be:
        // (a) the rightmost index of the given key within this
        // node, or 
        // (b) the position in which the given key would be inserted
        //     in this list if it was present
        //  
        int cur = 0;
        {
            int high = size();
            int low = 0;

            while (low < high) {
                cur = (high + low) / 2;
                if (getKey(cur) == key) {
                    //We found it now move to the last
                    for (;(cur < size()) && (key == getKey(cur)); cur++);
                    break;
                } else if (getKey(cur) < key) {
                    if (low == cur) {
                        low++;
                    } else {
                        low = cur;
                    }
                } else { // if(getKey(cur) > key)
                    high = cur;
                }
            }
        }

        //Now go to the nearest if there are multiple entries
        for (;(cur >= 0) && key < getKey(cur); cur--);

        return cur;
    }

    private int getKey(int pos) {
        return getKeys().get(pos);
    }

    private int findNearestKeyAbove(int key) {
        int high = size();
        int low = 0;
        int cur = 0;

        //Short circuit
        if (size() == 0) {
            return 0;
        } else if (getKey(size() - 1) < key) {
            return size();
        } else if (getKey(0) >= key) {
            return 0;
        }

        while (low < high) {
            cur = (high + low) / 2;
            if (high == low) {
                cur = low;
                break;
            } else if (getKey(cur) == key) {
                //We found it now move to the first
                for (;(cur > 0) && (key == getKey(cur)); cur--);
                break;
            } else if (high - low == 1) {
                cur = high;
                break;
            } else if (getKey(cur) < key) {
                if (low == cur) {
                    low++;
                } else {
                    low = cur;
                }
            } else { // if(getKey(cur) > key)
                high = cur;
            }
        }

        //Now go to the nearest if there are multiple entries
        for (;(cur < size()) && (key > getKey(cur)); cur++);

        return cur;
    }
    
    // attributes
    // ------------------------------------------------------------------------
    private static Log _log = LogFactory.getLog(BTree.class);
    private int _degree = 1000;
    private int _maxCap = (2 * _degree) - 1;
    private int _counter = 0; //Only used if object is root
    private int _fileId = 0; //The id that will be used for the file that is written
    private IntList _keys = null;
    private IntList _vals = null;
    private IntList _childIds = null;
    private Map _loadedChildren = null;
    private File _idxDir = null;
    private BTree _root = null;
    private String _idxName = null;


    // inner classes
    // ------------------------------------------------------------------------
    
    private static class BTreeValueIterator implements IntIterator {
        
        BTreeValueIterator(BTree node) throws IOException {
            _stack = new StateStack();
            _stack.push(node,false,0);            
        }
        
        BTreeValueIterator(StateStack stack) throws IOException {
            _stack = stack;
        }
        
        public boolean hasNext() {
            while(true) {
                if(_stack.isEmpty()) {
                    return false;
                } else {
                    State state = _stack.peek();
                    if((state.node.isLeaf() || state.visitedChildren) && state.position >= state.node.size()) {
                        _stack.pop();
                    } else {
                        return true;
                    }
                }
            }
        }

        public int next() {
            try {
                while(true) {
                    if(_stack.isEmpty()) {
                        throw new NoSuchElementException();
                    } else {
                        State state = _stack.pop();
                        if(!state.visitedChildren) {
                            state.visitedChildren = true;
                            _stack.push(state);
                            if(state.node.hasChild(state.position)) {
                                _stack.push(state.node.getChild(state.position),false,0);                    
                            }
                        } else if(state.position < state.node.size()) {
                            int value = state.node.getValue(state.position);
                            state.position++;
                            state.visitedChildren = false;
                            _stack.push(state);
                            return value; 
                        } else {
                            // do nothing, I've already popped
                        }
                    }
                }
            } catch(IOException e) {
                // @TODO: do something smarter
                throw new RuntimeException(e.toString());
            }
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        private StateStack _stack = null;
    }

    private static class StateStack {
        StateStack() {
        }

        boolean isEmpty() {
            return _nodes.isEmpty();
        }
        
        void push(State state) {
            _nodes.add(state);
        }

        void push(BTree tree, boolean visitedChildren, int position) {
            push(new State(tree,visitedChildren,position));
        }
        
        State pop() {
            return (State)(_nodes.remove(_nodes.size()-1));
        }

        State peek() {
            return (State)_nodes.get(_nodes.size()-1);
        }

        public String toString() {
            return _nodes.toString();
        }
        
        private List _nodes = new ArrayList();
         
    }

    private static class State {
        State(BTree n, boolean visited, int pos) {
            node = n;
            visitedChildren = visited;
            position = pos;
        }
        
        public String toString() {
            return "<" + node.getFileId() + "," + visitedChildren + "," + position + ">";    
        }
        
        BTree node = null;
        boolean visitedChildren = false;
        int position = 0;
    }

}