bplustree.java

支持并发访问的B+树

			ch=chmanager.getChannel();//get channel
			lock=ch.lock(0L,Long.MAX_VALUE,false);//lock the hole file
			saveHead(ch);//save tree head
			//save root node
			buff=ByteBuffer.wrap(rootnode.getBytes());
			//prepare to save
			buff.position(0);
			buff.limit(buff.capacity());
			ch.position(root);//move file pointer to the position root node saved
			if(ch.write(buff)!=nodelength) throw new IOBufferSizeError();
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//recycle channel
		}
	}
	
	/**
	 * save the tree into file and close the tree
	 * @throws IOException
	 */
	public synchronized void close() throws IOException
	{
		int i;
		ByteBuffer buff;
		FileChannel ch=null;
		FileLock lock;
		
		try
		{
			//tree can not colse twice
			if(isclosed) throw new TreeHasBeenClosedException("the tree has been closed.");
			isclosed=true;//closed
			ch=chmanager.getChannel();//get channel
			lock=ch.lock(0L,Long.MAX_VALUE,false);//lock the hole file
			saveHead(ch);//save tree head
			//save root node
			buff=ByteBuffer.wrap(rootnode.getBytes());
			//prepare to save
			buff.position(0);
			buff.limit(buff.capacity());
			ch.position(root);//move file pointer to the position root node saved
			if(ch.write(buff)!=nodelength) throw new IOBufferSizeError();
			//write empty node index into the end of the file
			ch.position(ch.size());
			buff=ByteBuffer.allocate(INDEX_BUFFER_SIZE);
			for(i=0;i<spmanager.size();)
			{
				for(;i<spmanager.size()&&buff.position()<buff.capacity();i++) buff.putLong(spmanager.getPointer(i));
				buff.flip();
				if(ch.write(buff)!=buff.limit()) throw new IOBufferSizeError();
				buff.clear();
			}
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//recycle channel
		}
	}
	
	/**
	 * get B+ tree's rank
	 * @return
	 */
	public int getRank()
	{
		return rank;
	}
	
	/**
	 * get node length measured in byte
	 * @return
	 */
	public int getNodeLength()
	{
		return nodelength;
	}

	/**
	 * get keyword's length measured in byte
	 * @return
	 */
	public int getKeywordLength()
	{
		return keywordlength;
	}
	
	/**get keyword's data type
	 * @return
	 * the same meaning as data type in java.sql.Types
	 */
	public int getDataType()
	{
		return datatype;
	}
	
	/**
	 * get tree height
	 * @return
	 */
	public int getHeight()
	{
		return height;
	}
	
	/**
	 * get total node number
	 * @return
	 */
	public int getNodeNum()
	{
		return nodenum;
	}
	
	/**
	 * to see if this tree is open or not
	 * @return
	 * return true if this tree is open
	 */
	public boolean isOpen()
	{
		return !isclosed;
	}
	
	/**
	 * get all supported data type,the data type is equal to
	 * data type in java.sql.Types
	 * @return
	 */
	public static Enumeration getSupportedDataType()
	{
		return nodeclassname.keys();
	}
	
	/**
	 * get tree inforamtion
	 */
	public String toString()
	{
		int i;
		StringBuffer s;
		
		s=new StringBuffer();
		s.append("path: "+path+"\n");
		s.append("rank: "+rank+"\n");
		s.append("node length: "+nodelength+"\n");
		s.append("keyword length: "+keywordlength+"\n");
		s.append("data type: "+datatype+"\n");
		s.append("height: "+height+"\n");
		s.append("node number: "+nodenum+"\n");
		s.append("digest: ");
		for(i=0;i<digest.length;i++) s.append(digest[i]+" ");
		return s.toString();
	}
	
	/**
	 * to make sure that at last tree is
	 * closed
	 */
	protected void finalize()
	{
		if(!isclosed)
		{
			try
			{
				close();
			}
			catch(IOException exc)
			{
				exc.printStackTrace();
			}
		}
	}
	
	/**
	 * public linearSearch method call this to support
	 * keyword's Object form and byte array form
	 * @param keyword
	 * keyword need to search,it is Keyword form
	 * @return 
	 * return the file pointer of the keyword 
	 * or BPlusTree.NULL if not found
	 * @throws IOException
	 */
	private long linearSearch(Keyword key) throws IOException
	{
		int index;
		long pointer,res=BPlusTree.NULL;
		BPlusTreeNode leaf;
		FileChannel ch=null;
		
		try
		{
			if(isclosed) throw new TreeHasBeenClosedException("the tree has been closed.");
			ch=chmanager.getChannel();//allocate a channel
			/*
			 * here is the same reason with findNode method.
			 * when call linearSearch,it start with leaf node,but in
			 * insert and delete method,it start with root node,so if
			 * recommented this statement it will cause when insert and
			 * delete deal with lead node
			 */
			ch.lock(0,BPlusTree.HEAD_LENGTH,true);
			//search all leaf node
			for(pointer=firstleaf;pointer!=BPlusTree.NULL;)
			{
				ch.lock(pointer,nodelength,true);//add a shared lock to the leaf node
				leaf=loadNode(pointer,ch);//load a leaf
				index=leaf.indexOf(key);//search in a leaf,use the Keyword form
				if(index>=0) 
				{	
					res=leaf.getLeftPointer(index);//success
					break;//end search
				}
				else pointer=leaf.getLast();//field,prepare to search the next leaf
			}
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release all lock and close channel
		}
		return res;//return result
	}	
	
	/**
	 * do liner search
	 * @param keyword
	 * keyword need to search,it is Object form
	 * @return 
	 * return the file pointer of the keyword 
	 * or BPlusTree.NULL if not found
	 * @throws IOException
	 */
	public long linearSearch(Object keyword) throws IOException
	{
		Keyword key;
		
		key=nodeb.buildKeyword(keyword);
		return linearSearch(key);
	}
	
	/**
	 * do liner search
	 * @param keyword
	 * keyword need to search,it is byte array form.
	 * the data in the byte array is keyword's primtive
	 * form,for example: when keyword's Object form is 
	 * Integer,the byte array form is 4 byte's int value,
	 * @return 
	 * return the file pointer of the keyword 
	 * or BPlusTree.NULL if not found
	 * @throws IOException
	 */
	public long linearSearch(byte[] keyword) throws IOException
	{
		Keyword key;
		
		key=nodeb.buildKeyword(keyword);
		return linearSearch(key);
	}
	
	/**
	 * find the leaf node where the keyword in
	 * or may in
	 * @param keyword
	 * the Keyword form of the keyword
	 * @param relation
	 * the realtion list hold the node's relationship
	 * pass null means not record the node's relationship
	 * @param ch
	 * file channel
	 * @param shared
	 * true stands for lock the file with shared lock
	 * while false stands for lock the file with exclusive lock
	 * @return
	 * @throws IOException
	 */
	private BPlusTreeNode findNode(Keyword keyword,NodeRelation relation,FileChannel ch,boolean shared) throws IOException
	{
		int i;
		long pointer;
		BPlusTreeNode node;

		/*
		 *     after tree has been constructed,data in tree head will not
		 * read and write until colse the tree.through in search,insert,
		 * delete operation will not read head data,here still lock head
		 * to make sure bulty thread's synchronization.
		 *     if remarked this statement,it will cause exception in multy
		 * thread environment.for example:thread1 and thread2 do insert
		 * operation in a same tree,the steps in insert operation is:first
		 * call findNode method to find the leaf node which keyword/pointer
		 * pair should inserted in,second call insertEntry method to insert
		 * keyword/pointer pair recursivly.if recommented this statement,
		 * when thread1 call findNode method,it first lock root node,if this time
		 * thread1's time used up and thread2 begin to run,thread2 first call
		 * findNode method,but root node has been locked by thread1,so thread2
		 * suspend,thread1 go on.after thread1 inserted a keyword/pointer pair,
		 * thread1's insert operation finished,he release all lock and close channel,
		 * then thread2 begin to run.if when thread1 inserted a keyword/pointer
		 * pair root node splited,the varible root and rootnode changed,but when
		 * thread2 go no to run,it resume from "ch.lock(root,nodelength,shared);"
		 * but the varible here root is still value,and the varible root is new
		 * value,so it will cause exception or dead lock.
		 *     when add this statement,thread will suspend at "ch.lock(0,BPlusTree.HEAD_LENGTH,shared);",
		 * so when he resumed,varible root and rootnode is all updated,so it will
		 * not cause problem.
		 */
		ch.lock(0,BPlusTree.HEAD_LENGTH,shared);
		/*
		 * althrough root node is cached in memory,here
		 * still lock root node's space in desk.
		 */
		ch.lock(root,nodelength,shared);
		/*
		 * to increase the speed,at beginning root node is already cached in
		 * memory,so the first step is search in the root node
		 */
		node=rootnode;//start with root
		if(relation!=null) relation.addNode(node.getAddr());//record relationship
		//if root node is leaf,the keyword may be in this node
		if(node.isLeaf()) return node;
		else
		{
			/*
			 * move the keyword index to the first keyword which is bigger
			 * than the keyword need to search,if no one is bigger than the
			 * keyword need to search,i stop at the last pointer
			 */
			for(i=0;i<node.getValid()&&!(node.getKeyword(i).compareTo(keyword)>0);i++);
			/*
			 * the keyword need to search may in the node chain which
			 * i stopped keyword's left pointer point to,if the keyword need to
			 * search is bigger than every keyword in the node,the keyword need
			 * to search may in the node chain which the last pointer point to
			 */
			pointer=node.getPointer(i);
			//iterate the node chain until reach a leaf node
			for(;;)
			{
				ch.lock(pointer,nodelength,shared);//lock a node
				node=loadNode(pointer,ch);//load this node
				if(relation!=null) relation.addNode(node.getAddr());//record relationship
				/*
				 * if this node is a leaf,the keyword in or
				 * may in this node
				 */
				if(node.isLeaf()) return node;
				//a none leaf node
				else
				{
					/*
					 * move the keyword index to the first keyword which is bigger
					 * than the keyword need to search,if no one is bigger than the
					 * keyword need to search,i stop at the last pointer
					 */
					for(i=0;i<node.getValid()&&!(node.getKeyword(i).compareTo(keyword)>0);i++);
					/*
					 * the keyword need to search may in the node chain which
					 * i stopped keyword's left pointer point to,if the keyword need to
					 * search is bigger than every keyword in the node,the keyword need
					 * to search may in the node chain which the last pointer point to
					 */
					pointer=node.getPointer(i);
				}
			}
		}
	}
	
	/**
	 * public search method call this to support keyword's
	 * Object form and byte array form
	 * @param keyword
	 * the keyword need to search,it is Keyword form
	 * @return
	 * if found,return the file pointer of this keyword,
	 * if not found, return BPlusTree.NULL
	 * @throws IOException
	 */
	private long search(Keyword key) throws IOException
	{
		int i;
		long pointer,res=BPlusTree.NULL;
		BPlusTreeNode node;
		FileChannel ch=null;
		
		try
		{
			if(isclosed) throw new TreeHasBeenClosedException("the tree has been closed.");
			ch=chmanager.getChannel();//allocate a channel
			/*
			 * find the leaf node the keyword may in
			 * because read will not interfere other thread,so here add
			 * the shared lock
			 */
			node=findNode(key,null,ch,true);
			i=node.indexOf(key);
			if(i>=0) res=node.getPointer(i);//success
			else res=BPlusTree.NULL;//field
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and close channel
		}
		return res;//return result
	}	
	
	/**
	 * search a keyword in the tree
	 * @param keyword
	 * the keyword need to search,it is Object form
	 * @return
	 * if found,return the file pointer of this keyword,
	 * if not found, return BPlusTree.NULL
	 * @throws IOException
	 */
	public long search(Object keyword) throws IOException
	{
		Keyword key;

		key=nodeb.buildKeyword(keyword);//convert keyword's form to Keyword
		return search(key);
	}
	
	/**
	 * search a keyword in the tree
	 * @param keyword
	 * the keyword need to search,it is byte array form
	 * @return
	 * if found,return the file pointer of this keyword,
	 * if not found, return BPlusTree.NULL