objectbtree.java

开源的axion的数据库代码

                    pivotLoc + 1 < getChildIds().size()
                        && getChild(pivotLoc + 1).getKeys().size() >= _degree) {
                    _log.debug("Case 3a, right");
                    //Case 3a, borrow-right
                    borrowRight(pivotLoc);
                    getChild(pivotLoc).delete(key);
                } else {
                    _log.debug("Case 3b");
                    //Case 3b

                    // if the key is on the far right, then we need to merge the last two nodes
                    int mergeLoc;
                    if (pivotLoc < getKeys().size()) {
                        mergeLoc = pivotLoc;
                    } else {
                        mergeLoc = pivotLoc - 1;
                    }

                    if (_log.isDebugEnabled()) {
                        _log.debug("Tree before merge: " + this);
                        _log.debug("Merge location: " + mergeLoc);
                    }

                    mergeChildren(mergeLoc, getKeys().get(mergeLoc));

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

                    maybeCollapseTree();

                    delete(key);
                }
            } else {
                getChild(i + 1).delete(key);
            }
        } else {
            if (isLeaf()) {
                _log.debug("Case 1");
                //Case 1
                getKeys().remove(i);
                getValues().removeElementAt(i);
                if (_log.isDebugEnabled()) {
                    _log.debug("Node " + _fileId + " deleted key " + key);
                }
            } else {
                _log.debug("Case 2");
                //Case 2
                if (getChild(i).size() >= _degree) {
                    _log.debug("Case 2a");
                    //Case 2a, move predecessor up
                    Object[] keyParam = new Object[1];
                    int[] valueParam = new int[1];
                    if (_log.isDebugEnabled()) {
                        _log.debug("Left child: " + getChild(i));
                    }
                    getChild(i).getRightMost(keyParam, valueParam);
                    getKeys().set(i, keyParam[0]);
                    getValues().set(i, valueParam[0]);
                    getChild(i).delete(keyParam[0]);
                } else if (getChild(i + 1).size() >= _degree) {
                    _log.debug("Case 2b");
                    //Case 2b, move successor up
                    Object[] keyParam = new Object[1];
                    int[] valueParam = new int[1];
                    if (_log.isDebugEnabled()) {
                        _log.debug("Right child: " + getChild(i + 1));
                    }
                    getChild(i + 1).getLeftMost(keyParam, valueParam);
                    getKeys().set(i, keyParam[0]);
                    getValues().set(i, valueParam[0]);
                    getChild(i + 1).delete(keyParam[0]);
                } else {
                    _log.debug("Case 2c");
                    //Case 2c, merge nodes
                    mergeChildren(i, key);

                    //Now delete from the newly merged node
                    getChild(i).delete(key);

                    maybeCollapseTree();
                }
            }
        }
    }

    public void borrowLeft(int borrowLoc) throws IOException, ClassNotFoundException {
        ObjectBTree leftSibling = getChild(borrowLoc - 1);
        ObjectBTree 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, getKeys().get(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.getKeys().get(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().remove(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);
        }
    }

    public void borrowRight(int borrowLoc) throws IOException, ClassNotFoundException {
        ObjectBTree leftSibling = getChild(borrowLoc);
        ObjectBTree 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(getKeys().get(borrowLoc));
        leftSibling.getValues().add(getValues().get(borrowLoc));

        //Make the upper node's key the first key from the right sibling
        getKeys().set(borrowLoc, rightSibling.getKeys().get(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().remove(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);
        }
    }

    public void mergeChildren(int mergeLoc, Object key) throws IOException, ClassNotFoundException {
        if (_log.isDebugEnabled()) {
            _log.debug("Merging children at: " + mergeLoc);
        }
        ObjectBTree leftChild = getChild(mergeLoc);
        ObjectBTree 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().remove(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);
        }
    }

    public void maybeCollapseTree() throws IOException, ClassNotFoundException {
        if (!isLeaf() && getKeys().size() <= 0) {
            _log.debug("Collapsing tree");
            ObjectBTree 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.
     * 
     */
    public void getLeftMost(Object[] keyParam, int valueParam[])
        throws IOException, ClassNotFoundException {
        if (isLeaf()) {
            keyParam[0] = getKeys().get(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.
     * 
     */
    public void getRightMost(Object[] keyParam, int valueParam[])
        throws IOException, ClassNotFoundException {
        if (isLeaf()) {
            int max = size() - 1;
            keyParam[0] = getKeys().get(max);
            valueParam[0] = getValues().get(max);
        } else {
            int max = getChildIds().size() - 1;
            getChild(max).getRightMost(keyParam, valueParam);
        }
    }

    public void insertNotfull(Object key, int value)
        throws IOException, ClassNotFoundException {
        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++;
            ObjectBTree child = getChild(i);
            if (child.size() == _maxCap) {
                subdivideChild(i, child);
                if (isGreaterThan(key, getKeys().get(i))) {
                    i++;
                }
            }
            getChild(i).insertNotfull(key, value);
        }
    }
    
    public IntListIterator getAll(Object key) throws IOException, ClassNotFoundException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAll(key,chain);
        return chain;
    }

    private void getAll(Object key, IntListIteratorChain chain) throws IOException, ClassNotFoundException {
        int start = findNearestKeyAbove(key);
        if(isLeaf()) {
            int stop;
            for(stop = start; stop < size() && isEqual(key,getKeys().get(stop)); stop++) { };
            chain.addIterator(getValues().subList(start,stop).listIterator());
        } else {
            int i = start;
            for(; i < size() && isEqual(key,getKeys().get(i)); i++) {
                getChild(i).getAll(key,chain);
                chain.addIterator(getValues().get(i));
            }
            getChild(i).getAll(key,chain);
        }
    }

    public IntListIterator getAllTo(Object key) throws IOException, ClassNotFoundException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAllTo(key,chain);
        return chain;
    }

    private void getAllTo(Object key, IntListIteratorChain chain) throws IOException, ClassNotFoundException {
        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() && isGreaterThan(key,getKeys().get(i))) {
                    chain.addIterator(getValues().get(i));
                } else { 
                    break;
                }
            }
        }
    }

    public IntListIterator getAllFrom(Object key) throws IOException, ClassNotFoundException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAllFrom(key,chain);
        return chain;
    }

    private void getAllFrom(Object key, IntListIteratorChain chain) throws IOException, ClassNotFoundException {       
        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;
                }
            }
        }        
    }

    /**
     * Uses the shortest path to a matching entry and returns its
     * value. Not necessarily the least value, the first entered, or
     * the leftmost.
     */
    public Integer get(Object key) throws IOException, ClassNotFoundException {
        Integer result = null;
        int i = findNearestKeyAbove(key);
        if ((i < size()) && (isEqual(key, getKeys().get(i)))) {
            result = new Integer(getValues().get(i));
        } else if (!isLeaf()) {
            // recurse to children
            result = getChild(i).get(key);
        }
        return result;
    }

    public void subdivideChild(int pivot, ObjectBTree child)
        throws IOException, ClassNotFoundException {
        if (_log.isDebugEnabled()) {
            _log.debug("Parent keys: " + getKeys().toString());
            _log.debug("Child keys: " + child.getKeys().toString());
        }