index.java

java 数据库 功能强大 效率高 SmallSQL Database is a free DBMS library for the Java(tm) platform. It runs on

/* =============================================================
 * SmallSQL : a free Java DBMS library for the Java(tm) platform
 * =============================================================
 *
 * (C) Copyright 2004-2006, by Volker Berlin.
 *
 * Project Info:  http://www.smallsql.de/
 *
 * This library is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU Lesser General Public License as published by 
 * the Free Software Foundation; either version 2.1 of the License, or 
 * (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful, but 
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
 * USA.  
 *
 * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
 * in the United States and other countries.]
 *
 * ---------------
 * Index.java
 * ---------------
 * Author: Volker Berlin
 * 
 */
package smallsql.database;

import java.sql.SQLException;
import java.util.ArrayList;


/**
 * To index data there need to solv the follow problems
 * - change the values that need to save in the index to a value with sort order that is compatible
 *   with the index algorithmus.
 * - multiple column index need to support. There should no identical save with combinations of values.
 * - The data type for column should be const.
 * - the data need to save fast.
 * - the size of the index should be small (also with a small count of values)
 * - It should use for unique index and nor unique. The unique index can save only one rowOffset.
 *   The non unique can save multiple rowOffsets in a LongTreeList.
 * - Problem ORDER BY with Joins? There are more as one rowOffset per row.
 * 
 * 
 * Algorithmus:
 * - convert the values that the binary order is equals to the value order. We need to handle
 *   sign, floating numbers, case insensitive, different binary length (MutableNumeric).
 * - create a 256 byte large mask for the first byte.
 * - create a 256 byte large status mask
 * - create a 256 large Object array
 * 
 * 
 * @author Volker Berlin
 *
 */
class Index{

	final IndexNode rootPage;
	
	/**
	 * Create an Index in the memory. An Index is like a sorted list.
	 * @param unique true if there are no duplicated values allow.
	 */
	Index(boolean unique){
		rootPage = new IndexNode(unique, (char)-1);
	}
	
    
    Index(IndexNode rootPage){
        this.rootPage = rootPage;
    }
    
    
	IndexScrollStatus createScrollStatus(Expressions expressions){
		return new IndexScrollStatus(rootPage, expressions);
	}
	
	/**
	 * Returns a Long (unigue) or a LongTreeList with rowOffsets. If the value in expressions
	 * does not exist then it return a null.
	 * @param expressions The value that are search in the Index.
	 */
	final Object findRows( Expressions expressions, ArrayList nodeList ) throws Exception{
		IndexNode page = rootPage;
		int count = expressions.size();
		for(int i=0; i<count; i++){
			page = findRows( page, expressions.get(i), nodeList);		
			if(page == null)
				return null;
			if(i+1 == count)
				return page.getValue();
			else
				page = (IndexNode)page.getValue();			
		}
		throw new Error();
	}
	
	
	/**
	 * Returns a Long (unigue) or a LongTreeList with rowOffsets. If the value in expressions
	 * does not exist then it return a null.
	 * @param expressions The value that are search in the Index.
	 */
	final Object findRows( Expression[] expressions, ArrayList nodeList ) throws Exception{
		IndexNode page = rootPage;
		int count = expressions.length;
		for(int i=0; i<count; i++){
			page = findRows( page, expressions[i], nodeList);		
			if(page == null)
				return null;
			if(i+1 == count)
				return page.getValue();
			else
				page = (IndexNode)page.getValue();			
		}
		throw new Error();
	}
	
	
	/** Return the last IndexNode for the expression */
	final private IndexNode findRows(IndexNode page, Expression expr, ArrayList nodeList) throws Exception{
			if(expr.isNull()){
				page = findNull(page);
			}else{
				switch(expr.getDataType()){
					case SQLTokenizer.REAL:
						page = find( page, floatToBinarySortOrder( expr.getFloat()), 2, nodeList );
						break;
					case SQLTokenizer.DOUBLE:
					case SQLTokenizer.FLOAT:
						page = find( page, doubleToBinarySortOrder( expr.getDouble()), 4, nodeList );
						break;
					case SQLTokenizer.TINYINT:
						page = find( page, expr.getInt(), 1, nodeList );
						break;
					case SQLTokenizer.SMALLINT:
						page = find( page, shortToBinarySortOrder( expr.getInt()), 1, nodeList );
						break;
					case SQLTokenizer.INT:
						page = find( page, intToBinarySortOrder( expr.getInt()), 2, nodeList );
						break;
					case SQLTokenizer.BIGINT:
					case SQLTokenizer.DATE:
					case SQLTokenizer.TIME:
					case SQLTokenizer.TIMESTAMP:
					case SQLTokenizer.SMALLDATETIME:
					case SQLTokenizer.MONEY:
					case SQLTokenizer.SMALLMONEY:
						page = find( page, longToBinarySortOrder( expr.getLong()), 4, nodeList );
						break;
					case SQLTokenizer.VARCHAR:
					case SQLTokenizer.NVARCHAR:
					case SQLTokenizer.LONGVARCHAR:
					case SQLTokenizer.LONGNVARCHAR:
					case SQLTokenizer.CLOB:
						page = find( page, stringToBinarySortOrder( expr.getString(), false ), nodeList );
						break;
					case SQLTokenizer.NCHAR:
					case SQLTokenizer.CHAR:
						page = find( page, stringToBinarySortOrder( expr.getString(), true ), nodeList );
						break;
					case SQLTokenizer.VARBINARY:
					case SQLTokenizer.BINARY:
					case SQLTokenizer.LONGVARBINARY:
					case SQLTokenizer.BLOB:
					case SQLTokenizer.UNIQUEIDENTIFIER:
						page = find( page, bytesToBinarySortOrder( expr.getBytes()), nodeList );
						break;
					case SQLTokenizer.BIT:
					case SQLTokenizer.BOOLEAN:
						page = find( page, expr.getBoolean() ? 2 : 1, 1, nodeList );
						break;
					case SQLTokenizer.NUMERIC:
					case SQLTokenizer.DECIMAL:						
						page = find( page, numericToBinarySortOrder( expr.getNumeric() ), nodeList );
						break;
					default: 
						//TODO weitere Datentypen
						throw new Error(String.valueOf(expr.getDataType()));
				}
			}
			return page;
	}

	
	/**
	 * Add a value to the index.
	 * @param rowOffset Is the value that is save in the index. It is typical a row number or a rowOffset.
	 * @param expressions This is the list of ORDER BY columns and descript the position in the index.
	 */
	final void addValues( long rowOffset, Expressions expressions ) throws Exception{
		IndexNode page = this.rootPage;
		int count = expressions.size();
		for(int i=0; i<count; i++){
			Expression expr = expressions.get(i);
			boolean isLastValues = (i == count-1);
			if(expr.isNull()){
				page = addNull(page, rowOffset, isLastValues);
			}else{
				switch(expr.getDataType()){
					case SQLTokenizer.REAL:
						page = add( page, rowOffset, floatToBinarySortOrder( expr.getFloat()), isLastValues, 2 );
						break;
					case SQLTokenizer.DOUBLE:
					case SQLTokenizer.FLOAT:
						page = add( page, rowOffset, doubleToBinarySortOrder( expr.getDouble()), isLastValues, 4 );
						break;
					case SQLTokenizer.TINYINT:
						page = add( page, rowOffset, expr.getInt(), isLastValues, 1 );
						break;
					case SQLTokenizer.SMALLINT:
						page = add( page, rowOffset, shortToBinarySortOrder( expr.getInt()), isLastValues, 1 );
						break;
					case SQLTokenizer.INT:
						page = add( page, rowOffset, intToBinarySortOrder( expr.getInt()), isLastValues, 2 );
						break;
					case SQLTokenizer.BIGINT:
					case SQLTokenizer.DATE:
					case SQLTokenizer.TIME:
					case SQLTokenizer.TIMESTAMP:
					case SQLTokenizer.SMALLDATETIME:
					case SQLTokenizer.MONEY:
					case SQLTokenizer.SMALLMONEY:
						page = add( page, rowOffset, longToBinarySortOrder( expr.getLong()), isLastValues, 4 );
						break;
					case SQLTokenizer.VARCHAR:
					case SQLTokenizer.NVARCHAR:
					case SQLTokenizer.LONGVARCHAR:
					case SQLTokenizer.LONGNVARCHAR:
						page = add( page, rowOffset, stringToBinarySortOrder( expr.getString(), false ), isLastValues );
						break;
					case SQLTokenizer.NCHAR:
					case SQLTokenizer.CHAR:
						page = add( page, rowOffset, stringToBinarySortOrder( expr.getString(), true ), isLastValues );
						break;
					case SQLTokenizer.VARBINARY:
					case SQLTokenizer.BINARY:
					case SQLTokenizer.LONGVARBINARY:
					case SQLTokenizer.BLOB:
					case SQLTokenizer.UNIQUEIDENTIFIER:
						page = add( page, rowOffset, bytesToBinarySortOrder( expr.getBytes()), isLastValues );
						break;
					case SQLTokenizer.BIT:
					case SQLTokenizer.BOOLEAN:
						page = add( page, rowOffset, expr.getBoolean() ? 2 : 1, isLastValues, 1 );
						break;
					case SQLTokenizer.NUMERIC:
					case SQLTokenizer.DECIMAL:
						page = add( page, rowOffset, numericToBinarySortOrder( expr.getNumeric()), isLastValues );
						break;
					default: 
						//TODO weitere Datentypen
						throw new Error(String.valueOf(expr.getDataType()));
				}