btree.java

开源的axion的数据库代码

/*
 * $Id: BTree.java,v 1.22 2003/05/16 20:22:59 rwald Exp $
 * =======================================================================
 * Copyright (c) 2002-2003 Axion Development Team.  All rights reserved.
 *  
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions 
 * are met:
 * 
 * 1. Redistributions of source code must retain the above 
 *    copyright notice, this list of conditions and the following 
 *    disclaimer. 
 *   
 * 2. Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in 
 *    the documentation and/or other materials provided with the 
 *    distribution. 
 *   
 * 3. The names "Tigris", "Axion", nor the names of its contributors may 
 *    not be used to endorse or promote products derived from this 
 *    software without specific prior written permission. 
 *  
 * 4. Products derived from this software may not be called "Axion", nor 
 *    may "Tigris" or "Axion" appear in their names without specific prior
 *    written permission.
 *   
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * =======================================================================
 */

package org.axiondb.util;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;

import org.apache.commons.collections.primitives.ArrayIntList;
import org.apache.commons.collections.primitives.IntIterator;
import org.apache.commons.collections.primitives.IntList;
import org.apache.commons.collections.primitives.IntListIterator;
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * A B-Tree for integers, based on the implementation described
 * in "Introduction to Algorithms" by Cormen, Leiserson and Rivest (CLR).
 * 
 * @version $Revision: 1.22 $ $Date: 2003/05/16 20:22:59 $
 * @author Chuck Burdick
 * @author Dave Pekarek Krohn
 */
public class BTree {

    // constructors
    // ------------------------------------------------------------------------

    /**
     * Create or load a new root node
     */
    public BTree(File idxDir, String idxName, int degree) throws IOException {
        this(idxDir, idxName, degree, null);
    }

    /**
     * Create or load a node
     */
    public BTree(File idxDir, String idxName, int degree, BTree root) throws IOException {
        _idxDir = idxDir;
        _idxName = idxName;
        _degree = degree; // t
        _maxCap = (2 * _degree) - 1;
        _keys = new ArrayIntList(_maxCap);
        _vals = new ArrayIntList(_maxCap);
        _childIds = new ArrayIntList(_maxCap + 1);
        _loadedChildren = new HashMap();

        if (root != null) {
            //Child node need to allocate the next in the sequence
            _root = root;
        } else {
            //Root node need to load the counter file
            _root = this;

            boolean treeExists = (null != idxDir) && getCounterFile().exists();
            if (treeExists) {
                setCounter(0);
                setFileId(getCounter());

                loadIdxCtr();
                read();
            } else {
                allocate();
            }
        }
    }

    /**
     * Create or load a new node
     */
    public BTree(File idxDir, String idxName, int degree, BTree root, boolean shouldCreate) throws IOException {
        this(idxDir, idxName, degree, root);
        if (shouldCreate) {
            allocate();
        }
    }

    /**
     * Read in an existing node file
     */
    public BTree(File idxDir, String idxName, int degree, int fileId, BTree root)
        throws IOException {
        this(idxDir, idxName, degree, root);
        setFileId(fileId);
        read();
    }

    // public methods
    // ------------------------------------------------------------------------

    public IntListIterator valueIterator() throws IOException {
        return new IntIteratorIntListIterator(new BTreeValueIterator(this));
    }

    public IntListIterator valueIteratorGreaterThanOrEqualTo(int fromkey) throws IOException {
        StateStack stack = new StateStack();
        for(BTree node = this; null != node;) {            
            int i = 0;
            while(i < node.size() && fromkey > node.getKey(i)) {
                i++;                
            }
            stack.push(node,true,i);
            node = node.getChildOrNull(i);
        }
        return new IntIteratorIntListIterator(new BTreeValueIterator(stack));
    }

    public IntListIterator valueIteratorGreaterThan(int fromkey) throws IOException {
        return valueIteratorGreaterThanOrEqualTo(fromkey + 1);
    }

    // -----------------------------------------------------------------------------------------------

    public int size() {
        return getKeys().size();
    }

    public void insert(int key, int value) throws IOException {
        if (size() == _maxCap) {
            // grow and rotate tree
            if (_log.isDebugEnabled()) {
                _log.debug(
                    "Node " + _fileId + " reached max capacity. Splitting and rotating.");
            }

            _log.debug("Creating new child node");
            BTree child = new BTree(_idxDir, getName(), _degree, _root, true);

            _log.debug("Transferring all data to child");
            child.getKeys().addAll(_keys);
            child.getValues().addAll(_vals);
            if (getChildIds().size() > 0) {
                child.addChildrenFrom(this);
                _log.debug("Transferred children to child");
            }

            _log.debug("Emptying my data");
            getKeys().clear();
            getValues().clear();
            getChildIds().clear();

            _log.debug("Attaching new child");
            addChild(0, child);

            _log.debug("Subdividing child into 2 children");
            subdivideChild(0, child);
        }
        insertNotfull(key, value);
    }

    public void delete(int key) throws IOException {
        //Comments refer to the cases described in CLR (19.3)
        if (_log.isDebugEnabled()) {
            _log.debug("Deleting: " + key);
        }
        if (size() <= 0) {
            _log.warn("keys: " + getKeys());
            _log.warn("values: " + getValues());
            _log.warn("childids: " + getChildIds());
            _log.warn("Tree is empty: " + this);
            return;
        }
        int i = findNearestKeyBelow(key);
        if ((i < 0 && getKey(i + 1) != key) || getKey(i) != key) {
            _log.debug("Case 3");
            //Case 3           
            int pivotLoc = i + 1;
            if (!isLeaf() && getChild(pivotLoc).getKeys().size() < _degree) {
                if (pivotLoc > 0 && getChild(pivotLoc - 1).getKeys().size() >= _degree) {
                    _log.debug("Case 3a, left");
                    //Case 3a, borrow-left
                    borrowLeft(pivotLoc);
                    getChild(pivotLoc).delete(key);
                } else if (
                    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, getKey(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().removeElementAt(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
                    int[] keyParam = new int[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
                    int[] keyParam = new int[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 IntListIterator getAll(int key) throws IOException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAll(key,chain);
        return chain;
    }

    public IntListIterator getAllTo(int key) throws IOException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAllTo(key,chain);
        return chain;
    }
    
    /**
     * 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(int key) throws IOException {
        int i = findNearestKeyAbove(key);
        if ((i < size()) && (key == getKey(i))) {
            return new Integer(getValues().get(i));
        } else if (!isLeaf()) {
            // recurse to children
            return getChild(i).get(key);
        } else {
            return null;
        }
    }

    public IntListIterator getAllFrom(int key) throws IOException {
        IntListIteratorChain chain = new IntListIteratorChain();
        getAllFrom(key,chain);
        return chain;
    }
    
    /**
     * Saves the tree.  It saves the counter file, writes out the node
     * and then calls save recursively through the tree.
     */
    public void save(File dataDirectory) throws IOException {
        _idxDir = dataDirectory;
        save();
    }

    public void save() throws IOException {
        if (isRoot()) {
            saveIdxCtr();
        }
        write();
        for (int i = 0; i < getChildIds().size(); i++) {
            getChild(i).save(_idxDir);
        }
    }

    public void replaceId(int key, int oldId, int newId) throws IOException {
        int i = findNearestKeyAbove(key);
        boolean valSet = false;
        while ((i < size()) && key == getKey(i)) {
            if (!isLeaf()) {
                getChild(i).replaceId(key, oldId, newId);
            }
            if (getValue(i) == oldId) {
                setValue(i, newId);
                valSet = true;
                break;
            }
            i++;
        }
        if (!valSet && !isLeaf()) {
            getChild(i).replaceId(key, oldId, newId);
        }
    }

    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("(id");
        buf.append(_fileId);
        buf.append(",");
        buf.append("(");
        for (int i = 0; i < size() + 1; i++) {
            if (!isLeaf()) {
                try {
                    buf.append(getChild(i).toString());
                } catch (IOException e) {
                    _log.error("Cannot retrieve child", e);
                }
                if (i < size()) {
                    buf.append(",");
                }
            }
            if (i < size()) {
                buf.append(getKey(i));
                buf.append("->");
                buf.append(getValues().get(i));
                if (!isLeaf() || i < (size() - 1)) {
                    buf.append(",");
                }
            }
        }
        buf.append(")");
        buf.append(")");