bplustree.java

支持并发访问的B+树

/*
 * Created on Nov 19, 2004
 *
 * TODO To change the template for this generated file go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
package com.nay0648.ds.bplustree;
import java.io.*;
import java.nio.*;
import java.nio.channels.*;
import java.util.*;
import java.sql.*;

/**
 * Description:<br>
 * &nbsp&nbsp this is the B+ tree implemention,use this class can build a
 * concurrent B+ tree index.<br>
 * &nbsp&nbsp B+ tree is a kind of file index used in database and file system,
 * it will give a high performance when there are millions of records need to
 * be indexed.common operation to a B+ tree are:search,linear search,insert and
 * delete.the deference between search and linear search is:search operation
 * starts from root node to leaf node,but linear search operation search leaf
 * node in order.<br>
 * &nbsp&nbsp the underlying mechainism of this implemention is java.nio package,
 * this approach use FileChannel and ByteBuffer as basic i/o to file system,
 * and use FileLock to make sure multy thread's concurrenty.the java.nio package 
 * is greatly depend underlying operation system,when use FileLock in Windows,it
 * is no problem,but when in Linux,it is not work.so when use this implemention in
 * Linux,it's just support single thread.
 * @abstract
 * a B+ tree implemention,use this class can build a concurrent B+ tree index.
 * @keywords
 * B+ tree,index,concurrent
 * @author nay0648<br>
 * if you have any questions,advices,suggests,or find any
 * bugs,please mail me: <a href="mailto:">[e-mail]</a>
 * @version last modified:Aug 1, 2004
 */
public class BPlusTree
{
public static final long NULL=-1;//the file pointer's null value
public static final int FILE_POINTER_LENGTH=8;//a file pointer's length
/*
 * tree file's fixed head length.the B+ tree's head contain these data:
 * rank(4B),node length(4B),keyword length(4B),data type(4B)
 * tree height(4B),node number(4B),empty node space index head pointer(8B)
 * root pointer(8B),the first leaf's pointer(8B)
 * digest(16B)
 * the sum of these data is 64 Bytes.
 */
private static final int HEAD_LENGTH=64;
private static final int DIGEST_LENGTH=16;//digest length with MD5
/*
 * buffer size used to read and write empty node space index
 * it must the integer times of 8
 */
private static final int INDEX_BUFFER_SIZE=4096;
/*
 * these are B+ tree properties,the properties' key is in int String form
 * refer to data type,the data type's int value is equal to the data type
 * value in java.sql.Types,in datalength Properties,the value is the data
 * type's byte length,in nodeclassname Properties,the value is the specified
 * data type node's class name.the are used to support to multy data type.
 */
private static Properties datalength;
private static Properties nodeclassname;
private boolean isclosed=true;//if the tree is closed,all i/o operation is illegal
private String path;//tree file path
private int rank;//B+ tree's rank
private int nodelength;// a tree node's length
private int keywordlength;//a keyword's length
private int datatype;//keyword's data type
private int height;//B+ tree's height
private int nodenum;//the number of the node
private long root;//root node
private long firstleaf;//the file pointer point to the firse leaf
private byte[] digest;//digest
/*
 * channel manager.it is used to allocate and recycle file channel
 */
private ChannelManager chmanager;
/*
 * space manager,used to allocate and recycle space for tree node
 */
private NodeSpaceManager spmanager;
/*
 * tree node builder,used to build new tree node and rebuild node
 * from a byte array read from tree file
 */
private BPlusTreeNode nodeb;
/*
 * the tree's root node,because root node is the first node need to
 * visit in most operations,so it is cached in memory,also because
 * memory's limit,we just cache root node
 */
private BPlusTreeNode rootnode;

	//init Properties when class loaded
	static
	{
		initProperties();
	}
	
	/**
	 * set static properties of a B+ tree,include data length
	 * and node class name,this is used when build tree
	 */
	private static void initProperties()
	{
		//set data length
		datalength=new Properties();
		datalength.setProperty(Integer.toString(Types.INTEGER),"4");
		//set node class name
		nodeclassname=new Properties();
		nodeclassname.setProperty(Integer.toString(Types.INTEGER),"com.nay0648.ds.bplustree.IntNode");
		nodeclassname.setProperty(Integer.toString(Types.CHAR),"com.nay0648.ds.bplustree.CharNode");
	}
	
	/**
	 * get the specified data type node builder
	 * @param datatype
	 * data type
	 * @return return null if field
	 */
	private BPlusTreeNode getNodeBuilder(int datatype)
	{
		String nodeclass;
		BPlusTreeNode node=null;
		
		nodeclass=BPlusTree.nodeclassname.getProperty(Integer.toString(datatype));
		if(nodeclass==null) throw new IllegalArgumentException("data type not found: "+datatype);
		try
		{
			node=(BPlusTreeNode)Class.forName(nodeclass).newInstance();
		}
		catch(ClassNotFoundException exc1)
		{
			exc1.printStackTrace();
		}
		catch(IllegalAccessException exc2)
		{
			exc2.printStackTrace();
		}
		catch(InstantiationException exc3)
		{
			exc3.printStackTrace();
		}
		return node;
	}
	
	/**
	 * it is used to save tree head when
	 * a tree is first build.it is not close
	 * the channel when finished
	 * @param ch
	 * tree file's channel
	 * @throws IOException
	 */
	private void saveHead(FileChannel ch) throws IOException
	{
		ByteBuffer buff;
		
		buff=ByteBuffer.allocate(BPlusTree.HEAD_LENGTH);
		//put head data into buffer in order
		buff.putInt(rank);//rank
		buff.putInt(nodelength);//node length
		buff.putInt(keywordlength);//keyword length
		buff.putInt(datatype);//data type
		buff.putInt(height);//tree height
		buff.putInt(nodenum);//node number
		buff.putLong(ch.size());//empty node index
		buff.putLong(root);//root node
		buff.putLong(firstleaf);//the first leaf's pointer
		buff.put(digest);//digest
		buff.flip();
		if(ch.write(buff)!=BPlusTree.HEAD_LENGTH) throw new IOBufferSizeError();//write init data into file
	}

	/**
	 * load a node from file
	 * @param addr
	 * the file pointer point to the node
	 * @param ch
	 * file channel
	 * @return
	 * @throws IOException
	 */
	private BPlusTreeNode loadNode(long addr,FileChannel ch) throws IOException
	{
		ByteBuffer buff;
		
		buff=ByteBuffer.allocate(nodelength);
		ch.position(addr);//seek position to the node's address
		if(ch.read(buff)!=nodelength) throw new IOBufferSizeError();
		return nodeb.getInstance(addr,buff.array());//rebuild node from byte array
	}

	/**
	 * save a node into file
	 * @param node
	 * node need to save
	 * @param addr
	 * file pointer where the node save to
	 * @param ch
	 * file channle
	 * @throws IOException
	 */
	private void saveNode(BPlusTreeNode node,long addr,FileChannel ch) throws IOException
	{
		ByteBuffer buff;

		buff=ByteBuffer.wrap(node.getBytes());
		//prepare to read data from buffer
		buff.position(0);
		buff.limit(buff.capacity());
		ch.position(addr);//seek to the node's address
		if(ch.write(buff)!=nodelength) throw new IOBufferSizeError();//save
	}

	/**
	 * construct a new tree,it is used when the tree build first time
	 * @param rank
	 * tree rank
	 * @param datatype
	 * data type with fixed data length,such as integer,float etc.
	 * the argument's meaning is the same as data type in java.sql.Types
	 * @param path
	 * tree file path
	 * @throws IOException
	 */
	public BPlusTree(int rank,int datatype,String path) throws IOException
	{
		ByteBuffer buff;
		FileChannel ch=null;
		FileLock lock;
	
		if(rank<2) throw new IllegalArgumentException("rank must bigger or equal than 2. rank: "+rank);
		nodeb=getNodeBuilder(datatype);//get node builder
		//init meta data
		this.rank=rank;
		this.datatype=datatype;
		this.path=path;
		//get keyword length from Properties
		keywordlength=Integer.valueOf(BPlusTree.datalength.getProperty(Integer.toString(datatype))).intValue();
		/*
		 * calcolate node length
		 * nodelength=headlength+(rank-1)(8+keywordlength)+8
		 */
		nodelength=BPlusTreeNode.HEAD_LENGTH+(rank-1)*(BPlusTree.FILE_POINTER_LENGTH+keywordlength)+BPlusTree.FILE_POINTER_LENGTH;
		height=1;//contain one empty root node
		nodenum=1;//first contain root node
		digest=new byte[DIGEST_LENGTH];
		//init the manager
		chmanager=new ChannelManager(path);
		spmanager=new NodeSpaceManager(path,nodelength);
		/*
		 * init tree node,node must initialized before
		 * build node instance
		 */
		BPlusTreeNode.init(rank,nodelength,keywordlength,datatype);
		//save data into file
		try
		{
			ch=chmanager.getChannel();
			lock=ch.lock(0L,Long.MAX_VALUE,false);//lock the hole file
			//save root node
			/*
			 * build a new node as root,leave space for tree head,
			 * when the node is first build,it set this node is leaf
			 * as default
			 */
			root=spmanager.allocate(ch,BPlusTree.HEAD_LENGTH);
			firstleaf=root;//the only root node is also the first leaf
			rootnode=nodeb.getInstance(root);//construct a new empty root node,and cache it
			buff=ByteBuffer.wrap(rootnode.getBytes());//convert root node into byte array
			//prepare to get data from buffer
			buff.position(0);
			buff.limit(buff.capacity());
			ch.position(root);//seek pointer to the address where root node should be save
			if(ch.write(buff)!=nodelength) throw new IOBufferSizeError();
			//save head
			ch.position(0);
			saveHead(ch);
			isclosed=false;//allow to visit this tree
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and colse channel
		}
	}
	
	/**
	 * this constructor is used to construct a B+ tree of varible
	 * keyword type,such as CHAR,BIGINTEGER and so on
	 * @param rank
	 * tree rank
	 * @param datatype
	 * data type with varible data length,such as char,big integer etc.
	 * the argument's meaning is the same as data type in java.sql.Types
	 * @param keywordlength
	 * keywrod length
	 * @param path
	 * tree file path
	 * @throws IOException
	 */
	public BPlusTree(int rank,int datatype,int keywordlength,String path) throws IOException
	{
		ByteBuffer buff;
		FileChannel ch=null;
		FileLock lock;
	
		if(rank<2) throw new IllegalArgumentException("rank must bigger or equal than 2. rank: "+rank);
		nodeb=getNodeBuilder(datatype);//get node builder
		//init meta data
		this.rank=rank;
		this.datatype=datatype;
		this.keywordlength=keywordlength;
		this.path=path;
		/*
		 * calcolate node length
		 * nodelength=headlength+(rank-1)(8+keywordlength)+8
		 */
		nodelength=BPlusTreeNode.HEAD_LENGTH+(rank-1)*(BPlusTree.FILE_POINTER_LENGTH+keywordlength)+BPlusTree.FILE_POINTER_LENGTH;
		height=1;//contain one empty root node
		nodenum=1;//first contain root node
		digest=new byte[DIGEST_LENGTH];
		//init the manager
		chmanager=new ChannelManager(path);
		spmanager=new NodeSpaceManager(path,nodelength);
		/*
		 * init tree node,node must initialized before
		 * build node instance
		 */
		BPlusTreeNode.init(rank,nodelength,keywordlength,datatype);
		//save data into file
		try
		{
			ch=chmanager.getChannel();
			lock=ch.lock(0L,Long.MAX_VALUE,false);//lock the hole file
			//save root node
			/*
			 * build a new node as root,leave space for tree head,
			 * when the node is first build,it set this node is leaf
			 * as default
			 */
			root=spmanager.allocate(ch,BPlusTree.HEAD_LENGTH);
			firstleaf=root;//the only root node is also the first leaf
			rootnode=nodeb.getInstance(root);//construct a new empty root node,and cache it
			buff=ByteBuffer.wrap(rootnode.getBytes());//convert root node into byte array
			//prepare to get data from buffer
			buff.position(0);
			buff.limit(buff.capacity());
			ch.position(root);//seek pointer to the address where root node should be save
			if(ch.write(buff)!=nodelength) throw new IOBufferSizeError();
			//save head
			ch.position(0);
			saveHead(ch);
			isclosed=false;//allow to visit this tree
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and colse channel
		}
	}
	
	/**
	 * load a alreadt exists tree from a file
	 * @param path tree file path
	 * @throws IOException
	 */
	public BPlusTree(String path) throws IOException
	{
		int len;
		long emptyindex;
		FileChannel ch=null;
		FileLock lock=null;
		ByteBuffer buff;
		
		this.path=path;
		digest=new byte[DIGEST_LENGTH];
		chmanager=new ChannelManager(path);
		try
		{
			//prepare to read tree head
			buff=ByteBuffer.allocate(BPlusTree.HEAD_LENGTH);
			ch=chmanager.getChannel();
			lock=ch.lock(0L,Long.MAX_VALUE,false);//lock the hole file
			if(ch.read(buff)!=BPlusTree.HEAD_LENGTH) throw new IOBufferSizeError();//read tree head into buffer
			buff.flip();
			//get all meta data in order
			rank=buff.getInt();//rank
			nodelength=buff.getInt();//node length
			keywordlength=buff.getInt();//keyword length
			datatype=buff.getInt();//datatype
			height=buff.getInt();//tree height
			nodenum=buff.getInt();//node number
			emptyindex=buff.getLong();//empty node index
			root=buff.getLong();//root index
			firstleaf=buff.getLong();//the first leaf's pointer
			buff.get(digest);//digest
			nodeb=getNodeBuilder(datatype);//construct node builder according data type
			BPlusTreeNode.init(rank,nodelength,keywordlength,datatype);//init tree node
			//read root node
			buff=ByteBuffer.allocate(nodelength);
			ch.position(root);
			if(ch.read(buff)!=nodelength) throw new IOBufferSizeError();
			rootnode=nodeb.getInstance(root,buff.array());//rebuild root node
			//read all empty node index
			spmanager=new NodeSpaceManager(path,nodelength);
			buff=ByteBuffer.allocate(INDEX_BUFFER_SIZE);
			ch.position(emptyindex);//seek to the empty node index
			for(;ch.read(buff)>0;)
			{	
				buff.flip();
				for(;buff.position()<buff.limit();) spmanager.recycle(buff.getLong());//add all index to the space manager
				buff.clear();
			}
			ch.truncate(emptyindex);//cut the index
			isclosed=false;//allow to visit this tree;
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and recycle channel
		}
	}
	
	/**
	 * save a tree but not close it
	 * @throws IOException
	 */
	public void save() throws IOException
	{
		int i;
		ByteBuffer buff;
		FileChannel ch=null;
		FileLock lock;
		
		try
		{