bplustree.java

支持并发访问的B+树

	 * @throws IOException
	 */
	public long search(byte[] keyword) throws IOException
	{
		Keyword key;

		key=nodeb.buildKeyword(keyword);//convert keyword's form to Keyword
		return search(key);
	}
	
	/**
	 * public insert method call this to support keyword's
	 * Object form and byte array form
	 * @param keyword
	 * keyword,it is Keyword form
	 * @param pointer
	 * keyowrd's pointer
	 * @throws IOException
	 */
	private void insert(Keyword key,long pointer) throws IOException
	{
		FileChannel ch=null;
		BPlusTreeNode node;
		NodeRelation relation;
		
		try
		{
			if(isclosed) throw new TreeHasBeenClosedException("the tree has been closed.");
			if(pointer==BPlusTree.NULL) throw new IllegalArgumentException("can not use BPlusTree.NULL as a keyword's pointer");
			ch=chmanager.getChannel();
			relation=new NodeRelation();//realtion list
			/*
			 * find the leaf node the key word should be
			 * insert into,here add the exclusive lock
			 */
			node=findNode(key,relation,ch,false);
			insertEntry(node,relation,key,pointer,ch);//call insertEntry resurcive
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and close channel
		}
	}
	
	/**
	 * insert a keyword/pointer pair into the tree
	 * @param keyword
	 * keyword,it is Object form
	 * @param pointer
	 * keyowrd's pointer
	 * @throws IOException
	 */
	public void insert(Object keyword,long pointer) throws IOException
	{
		Keyword key;

		key=nodeb.buildKeyword(keyword);
		insert(key,pointer);
	}
	
	/**
	 * insert a keyword/pointer pair into the tree
	 * @param keyword
	 * keyword,it is byte array form
	 * @param pointer
	 * keyowrd's pointer
	 * @throws IOException
	 */
	public void insert(byte[] keyword,long pointer) throws IOException
	{
		Keyword key;

		key=nodeb.buildKeyword(keyword);
		insert(key,pointer);
	}
	
	/**
	 * this is the method that insert call resurcively
	 * @param node
	 * tree node need to deal with
	 * @param relation
	 * the relationship among nodes
	 * @param keyword
	 * keyword need to insert
	 * @param pointer
	 * keyword's pointer
	 * @param ch
	 * file channel
	 * @throws IOException
	 */
	private void insertEntry(BPlusTreeNode node,NodeRelation relation,Keyword keyword,long pointer,FileChannel ch) throws IOException
	{
		int i,m;
		long node2p,node3p;
		Keyword vp=null;
		BPlusTreeNode node2,node3;
		
		/*
		 * if node still have space to hole new keyword,
		 * insert the keywrod and the pointer into this node,
		 * it is not need to split node
		 */
		if(node.haveSpace())
		{
			/*
			 * in a leaf node,a keyword's pointer
			 * is the keyword's left pointer,so use insertLeaf method,
			 * while in a none leaf node,the keyword's pointer
			 * is the keyword's right pointer,so use insertNoneLeaf
			 * method to add keyword and pointer into the node
			 */
			if(node.isLeaf()) node.insertLeaf(keyword,pointer);
			else node.insertNoneLeaf(keyword,pointer);
			saveNode(node,node.getAddr(),ch);
		}
		//split node
		else
		{
			//create a new node
			node2p=spmanager.allocate(ch);//allocate space
			ch.lock(node2p,nodelength,false);//lock this space with exclusive lock
			node2=nodeb.getInstance(node2p);//build node instance,it is a leaf node by default
			//split in leaf
			if(node.isLeaf())
			{
				vp=node.splitLeaf(keyword,node2);//split
				/*
				 * if the keyword need to insert small than vp,insert it in the
				 * old node,else insert it in the new node
				 */
				if(keyword.compareTo(vp)<0) node.insertLeaf(keyword,pointer);
				else node2.insertLeaf(keyword,pointer);
			}
			//split a none leaf node
			else
			{
				node2.isLeaf(false);//it's not a leaf
				vp=node.splitNoneLeaf(keyword,node2);//split a none leaf node
				/*
				 * if the keyword need to insert small than vp,insert it in the
				 * old node,else insert it in the new node
				 */
				if(keyword.compareTo(vp)<0) node.insertNoneLeaf(keyword,pointer);
				else node2.insertNoneLeaf(keyword,pointer);
				node2.deleteLeaf(vp);//here use deleteLeaf method to delete vp and its left pointer
			}
			if(node.getAddr()!=root)
			{
				//get node's parent
				node3p=relation.getParent(node.getAddr());
				if(node3p==root) node3=rootnode;//if this node's parent is root node,need not to load
				/*
				 * because the node space is already locked when find leaf
				 * node,so here need not to lock this node space
				 */
				else node3=loadNode(node3p,ch);
				insertEntry(node3,relation,vp,node2.getAddr(),ch);//resurcively
			}
			//create a new node as root
			else
			{
				//create a new node
				node3p=spmanager.allocate(ch);
				ch.lock(node3p,nodelength,false);
				node3=nodeb.getInstance(node3p);
				node3.isLeaf(false);//the new root node is not leaf node any more
				/*
				 * the new root's only keyword is vp,vp's left pointer point to
				 * the old node while vp's right pointer point to the new node
				 */
				node3.insertNoneLeaf(vp,node2.getAddr());
				node3.setFirst(node.getAddr());
				//new root
				root=node3p;
				rootnode=node3;
				saveNode(rootnode,rootnode.getAddr(),ch);//save the new root node
				nodenum++;//the total node number increased by one
				height++;//the tree's height increased by one
			}
			//join the new node to the leaf chain
			if(node.isLeaf())
			{
				node2.setLast(node.getLast());
				node.setLast(node2.getAddr());
			}
			//save two node
			saveNode(node,node.getAddr(),ch);
			saveNode(node2,node2.getAddr(),ch);
			nodenum++;//the total node number increased by one
		}
	}
	
	/**
	 * public delete method call this to support keyword's
	 * Object form and byte array form
	 * @param keyword,it is Keyword form
	 * keyword need to delete
	 * @return
	 * the keyword's pointer,return BPlusTree.NULL
	 * if this keyword not found
	 * @throws IOException
	 */
	private long delete(Keyword key) throws IOException
	{
		FileChannel ch=null;
		long res=BPlusTree.NULL;
		BPlusTreeNode node;
		NodeRelation relation;
		
		try
		{
			if(isclosed) throw new TreeHasBeenClosedException("the tree has been closed.");
			ch=chmanager.getChannel();//allocate a channel
			relation=new NodeRelation();//realtion list
			/*
			 * find the leaf node the keyword may
			 * in,here add the exclusive lock
			 */
			node=findNode(key,relation,ch,false);
			res=deleteEntry(node,relation,key,ch);//call deleteEntry resurcivly
		}
		catch(IOException exc)
		{
			throw exc;
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);//release lock and close channel
		}
		return res;
	}
	
	/**
	 * delete a keyword and its pointer
	 * @param keyword
	 * keyword need to delete,it is Object form
	 * @return
	 * the keyword's pointer,return BPlusTree.NULL
	 * if this keyword not found
	 * @throws IOException
	 */
	public long delete(Object keyword) throws IOException
	{
		Keyword key;
		
		key=nodeb.buildKeyword(keyword);
		return delete(key);
	}
	
	/**
	 * delete a keyword and its pointer
	 * @param keyword
	 * keyword need to delete,it is byte array form
	 * @return
	 * the keyword's pointer,return BPlusTree.NULL
	 * if this keyword not found
	 * @throws IOException
	 */
	public long delete(byte[] keyword) throws IOException
	{
		Keyword key;
		
		key=nodeb.buildKeyword(keyword);
		return delete(key);
	}
	
	/**
	 * this is the method that delete call resurcively
	 * @param node
	 * tree node need to deal with
	 * @param relation
	 * the relationship among nodes
	 * @param keyword
	 * keyword need to delete
	 * @param ch
	 * file channel
	 * @return
	 * the keyword's pointer
	 * @throws IOException
	 */
	private long deleteEntry(BPlusTreeNode node,NodeRelation relation,Keyword keyword,FileChannel ch) throws IOException
	{
		int i;
		long res=BPlusTree.NULL;
		long node2p,nodepp;
		BPlusTreeNode node2,nodep;
		BPlusTreeNode temp;
		Keyword vp;
		
		/*
		 * delete keyword/pointer pair form node.if this node is a leaf
		 * node,call deleteLeaf to delete keyword and its left pointer,
		 * if this node is a none leaf node,call deleteNoneLeaf to delete
		 * keyword and its right pointer.
		 */
		if(node.isLeaf()) res=node.deleteLeaf(keyword);
		else res=node.deleteNoneLeaf(keyword);
		saveNode(node,node.getAddr(),ch);//save this node
		/*
		 * if root node is not a leaf node,when root is empty,it contain no
		 * keyword but one useful pointer,so use root's only child node as
		 * new root and tree's height decreased by 1,if old root is leaf,
		 * not do this.
		 */
		if(node.getAddr()==root&&!node.isLeaf()&&node.getValid()==0)
		{
			/*
			 * when last deleteEntry,this node's only child is locked
			 * by combine node,so here need not lock node
			 */
			root=node.getFirst();
			rootnode=loadNode(root,ch);
			spmanager.recycle(node.getAddr());
			nodenum--;//node number decreased by 1
			height--;//tree's height decreased
			return res;//return
		}
		/*
		 * the keyword number in this node is too little,
		 * need to combine this node with another node
		 */ 
		if(node.getAddr()!=root&&node.getValid()<Math.ceil(((double)(rank-1))/((double)2)))
		{
			/*
			 * here node2 is node's left brother or right brother
			 * vp is the keyword between node and node2,nodep is
			 * node and node2's parent
			 */
			nodepp=relation.getParent(node.getAddr());
			/*
			 * if this parent is root,use rootnode directly.
			 * load node's parent node,because node's parent is locked
			 * so here need not add lock. 
			 */
			if(nodepp==root) nodep=rootnode;else nodep=loadNode(nodepp,ch);
			i=nodep.indexOf(node.getAddr());
			//get node2 as node's left brother or right brother
			if(i==0)
			{
				vp=nodep.getKeyword(i);
				node2p=nodep.getPointer(i+1);//node2 is node's right brother
			}
			else
			{
				vp=nodep.getKeyword(i-1);
				node2p=nodep.getPointer(i-1);//node2 is node's left brother
			}
			ch.lock(node2p,nodelength,false);
			node2=loadNode(node2p,ch);
			//node and node2 can combine together
			if(node.canCombine(node2))
			{
				/*
				 * if node is the predecessor of node2,swap them
				 * so after here,node2 is the predecessor of node
				 */
				if(nodep.isPred(node.getAddr(),node2.getAddr()))
				{
					temp=node;
					node=node2;
					node2=temp;
				}
				//combine
				if(node.isLeaf()) node2.combineLeaf(node);
				else node2.combineNoneLeaf(vp,node);
				/*
				 * after modified,save node.here just need to save node2
				 * because node is no longer useful and been recycled
				 */
				saveNode(node2,node2.getAddr(),ch);
				spmanager.recycle(node.getAddr());//node is now empty,so recycle it
				nodenum--;//node number decreased by 1
				deleteEntry(nodep,relation,vp,ch);//call insertEntry resurcive
			}
			/*
			 * node and node2's keyword and pointer can not move into on
			 * node,so here must restore keyword and pointer amoung node,
			 * node2 and nodep
			 */
			else
			{	
				nodep.restore(node,node2,vp);
				//save changes
				saveNode(node,node.getAddr(),ch);
				saveNode(node2,node2.getAddr(),ch);
				saveNode(nodep,nodep.getAddr(),ch);
			}
		}
		return res;
	}
	
	/**
	 * it is used to debug
	 */
	void printRootNode()
	{
		System.out.println(rootnode+" addr: "+root);
	}
	
	/**
	 * print all tree,used to debug
	 */
	void printTree()
	{
		long addr;
		ByteBuffer buff;
		FileChannel ch=null;
		BPlusTreeNode node;
		
		try
		{
			System.out.println("root node:");
			System.out.println(rootnode+" addr: "+rootnode.getAddr());
			ch=chmanager.getChannel();
			ch.lock(0L,Long.MAX_VALUE,true);
			buff=ByteBuffer.allocate(nodelength);
			ch.position(BPlusTree.HEAD_LENGTH);
			System.out.println("all node:");
			for(;;)
			{
				addr=ch.position();
				if(ch.read(buff)<=0) break;
				node=nodeb.getInstance(addr,buff.array());
				buff.clear();
				System.out.println(node+" addr: "+node.getAddr());
			}
			System.out.println("recycled:");
			System.out.println(spmanager);
		}
		catch(IOException exc)
		{
			exc.printStackTrace();
		}
		catch(Throwable th)
		{
			th.printStackTrace();
		}
		finally
		{
			chmanager.recycle(ch);
		}
	}

	/*
	public static void main(String args[]) throws IOException
	{}
	*/
}