bplustreenode.java

支持并发访问的B+树

	 * a keyword/pointer pair
	 */
	public void insertLeaf(KeywordPointerPair pair)
	{
		insertLeaf(pair.getKeyword(),pair.getPointer());
	}
	
	/**
	 * delete a keyword/pointer pair from this leaf node,
	 * the pointer is considered as the left pointer
	 * of the keyword,so only leaf node use this method.
	 * @param key
	 * keyword
	 * @return
	 * the pointer of this keyword,or BPlusTree.NULL
	 * if such keyword not exitts
	 */
	public long deleteLeaf(Keyword key)
	{
		int i;
		
		i=keyword.indexOf(key);
		if(i>=0)
		{
			keyword.remove(i);
			return ((Long)pointer.remove(i)).longValue();	
		}
		else return BPlusTree.NULL;
	}
	
	/**
	 * delete a specified index keyword/pointer pair in this 
	 * leaf node,the pointer is the keyword's left pointer
	 * @param index
	 * @return
	 */
	public KeywordPointerPair deleteLeaf(int index)
	{
		KeywordPointerPair res;
		
		res=new KeywordPointerPair(removeKeyword(index),removePointer(index));
		return res;
	}
	
	/**
	 * insert a keyword and its pointer into this none leaf node.
	 * the keyword's pointer is thought as the keyword's
	 * right pointer,so just none leaf node use this method to
	 * add a new keyword/pointer pair into node in order
	 * @param key
	 * keyword in Keyword form
	 * @param p
	 * the keyword's file pointer
	 */
	public void insertNoneLeaf(Keyword key,long p)
	{
		int i=0;
		
		/*
		 * move the pointer i to the position where the first keyword in
		 * list that the keyword need to insert is small than or equal to  
		 */
		for(i=0;i<keyword.size()&&key.compareTo(getKeyword(i))>0;i++);
		/*
		 * if i=keyword.size(),the keyword need to insert is bigger
		 * than all keywords in the node
		 */
		if(i<keyword.size())
			if(key.equals(getKeyword(i))) throw new IllegalArgumentException("keyword must unique");
		keyword.add(i,key);
		pointer.add(i+1,new Long(p));//the pointer is the right pointer
	}

	/**
	 * insert a keyword and its pointer into this none leaf node.
	 * the keyword's pointer is thought as the keyword's
	 * right pointer,so just none leaf node use this method to
	 * add a new keyword/pointer pair into node in order
	 * @param pair
	 * a keyword/pointer pair
	 */
	public void insertNoneLeaf(KeywordPointerPair pair)
	{
		insertNoneLeaf(pair.getKeyword(),pair.getPointer());
	}

	/**
	 * delete a keyword/pointer pair in a none leaf node 
	 * @param key
	 * the keyword
	 * @return
	 * the keyword's pointer
	 */
	public long deleteNoneLeaf(Keyword key)
	{
		int i;
		
		i=keyword.indexOf(key);
		if(i>=0)
		{
			keyword.remove(i);
			return ((Long)pointer.remove(i+1)).longValue();	
		}
		return BPlusTree.NULL;
	}
	
	/**
	 * delete a keyword/pointer pair form a none leaf node in the 
	 * specified index
	 * @param index
	 * @return
	 */
	public KeywordPointerPair deleteNoneLeaf(int index)
	{
		KeywordPointerPair res;
		
		res=new KeywordPointerPair(removeKeyword(index),removePointer(index+1));
		return res;
	}
	
	/**
	 * do split operation between this node and the argument node
	 * the two node must be leaf node
	 * @param key
	 * keyword need to insert
	 * @param node
	 * a new node do split operation with this node
	 * @return
	 * the keyword that all keyword in this node and the keyword
	 * need to insert have celi(rank/2) keyword small than it,it
	 * is used to call insertEntry resurcive
	 */
	public Keyword splitLeaf(Keyword key,BPlusTreeNode node)
	{
		int i,m,valid,j;
		Keyword vp;
		List temp;
		
		/*
		 * get the keyword value vp that all keyword in this node and
		 * the keyword need to insert have celi(rank/2) keyword small than
		 * vp
		 */
		temp=new ArrayList();
		for(i=0;i<keyword.size();i++) temp.add(keyword.get(i));
		for(i=0;i<temp.size()&&key.compareTo(temp.get(i))>0;i++);
		if(i<temp.size())
			if(temp.get(i).equals(key)) throw new IllegalArgumentException("keyword must unique");
		temp.add(i,key);
		vp=(Keyword)temp.get((int)Math.ceil(((double)rank)/((double)2)));
		/*
		 * m stop to the position in this node where getKeyword(m)
		 * is the smallest value that bigger or equal than vp
		 */
		for(m=0;m<getValid()&&getKeyword(m).compareTo(vp)<0;m++);
		/*
		 * move node.Pm,node.Km...node.Pn-1,node.Kn-1 to the
		 * new node
		 * because here use a list hold the ksywords and the pointers
		 * so when delete a element,the index changed,so use varible 
		 * valid and j to prevent this
		 */
		valid=getValid();//when delete,the getValid() changed
		for(i=m,j=0;i<valid;i++,j++) node.insertLeaf(deleteLeaf(i-j));
		return vp;
	}
	
	/**
	 * split a none leaf node
	 * @param key
	 * the keyword need to insert
	 * @param node
	 * a node do split operation with this node
	 * @return
	 * vp is the keyword that all keywords in this node and
	 * keyword need to insert have celi(rank/2) keywords bigger
	 * than or equal to vp
	 */
	public Keyword splitNoneLeaf(Keyword key,BPlusTreeNode node)
	{
		int i,m,valid,j;
		Keyword vp;
		List temp;
		
		/*
		 * get the keyword value vp that all keyword in this node and
		 * the keyword need to insert have celi(rank/2) keyword bigger than
		 * or equal to vp
		 */
		temp=new ArrayList();
		for(i=0;i<keyword.size();i++) temp.add(keyword.get(i));
		for(i=0;i<temp.size()&&key.compareTo(temp.get(i))>0;i++);
		if(i<temp.size())
			if(temp.get(i).equals(key)) throw new IllegalArgumentException("keyword must unique");
		temp.add(i,key);
		vp=(Keyword)temp.get(temp.size()-(int)Math.ceil(((double)rank)/((double)2)));
		/*
		 * m stop to the position in this node where getKeyword(m)
		 * is the smallest value that bigger or equal than vp
		 */
		for(m=0;m<getValid()&&getKeyword(m).compareTo(vp)<0;m++);
		/*
		 * move node.Pm,node.Km...node.Pn-1,node.Kn-1 to the
		 * new node
		 * because here use a list hold the ksywords and the pointers
		 * so when delete a element,the index changed,so use varible 
		 * valid and j to prevent this
		 */
		valid=getValid();//when delete,the getValid() changed
		for(i=m,j=0;i<valid;i++,j++) node.insertNoneLeaf(deleteNoneLeaf(i-j));
		return vp;
	}

	/**
	 * combine two leaf node,add argument node's all keyword
	 * and pointer into this node
	 * @param node
	 * another node
	 */
	public void combineLeaf(BPlusTreeNode node)
	{
		int i;
		List k,p;
		
		k=node.getKeywordList();
		p=node.getPointerList();
		for(i=0;i<node.getValid();i++)
		{
			keyword.add(k.get(i));
			pointer.add(pointer.size()-1,p.get(i));
		}
		setLast(node.getLast());
	}
	
	/**
	 * combine two none leaf node,add argument node's all keyword
	 * and pointer into this node
	 * @param vp
	 * the keyword in parent between two child node
	 * @param node
	 * another node
	 */
	public void combineNoneLeaf(Keyword vp,BPlusTreeNode node)
	{
		int i;
		List k,p;
		
		k=node.getKeywordList();
		p=node.getPointerList();
		keyword.add(vp);
		for(i=0;i<k.size();i++) keyword.add(k.get(i));
		for(i=0;i<p.size();i++) pointer.add(p.get(i));
	}
	
	/**
	 * replace key1 with key2 in a node
	 * @param key1
	 * the keyword need to be replaced
	 * @param key2
	 * the new keyword
	 */
	public void replace(Keyword key1,Keyword key2)
	{
		int i;
		
		i=keyword.indexOf(key1);
		if(i>=0) keyword.set(i,key2);
	}
	
	/**
	 * when combine two node,when their keyword and pointer can not put into
	 * one node,call this method to restore keyword and pointer amoung this
	 * two node and their parent,like this: parent.restore(child1,child2,vp)
	 * @param node
	 * a node
	 * @param node2
	 * another node
	 * @param vp
	 * keyword between these two nodes
	 */
	public void restore(BPlusTreeNode node,BPlusTreeNode node2,Keyword vp)
	{
		KeywordPointerPair kp;
		List k,p;
		
		k=node.getKeywordList();
		p=node.getPointerList();
		//node2 is node's predecessor
		if(isPred(node2.getAddr(),node.getAddr()))
		{
			//node and node2 are leaf node
			if(node.isLeaf())
			{
				/*
				 * delete node2's last keyword and this keyword's
				 * left pointer
				 */
				kp=node2.deleteLeaf(node2.getValid()-1);
				/*
				 * add this keyword/pointer pair into node as its first
				 * keyword and pointer
				 */
				k.add(0,kp.getKeyword());
				p.add(0,new Long(kp.getPointer()));
				/*
				 * replace node and node2's parent's vp with
				 * old node2's last keyword
				 */
				replace(vp,kp.getKeyword());
			}
			//node and node2 are none leaf node
			else
			{
				/*
				 * delete node2's last keyword and pointer
				 */
				kp=node2.deleteNoneLeaf(node2.getValid()-1);
				/*
				 * add vp and node's last pointer into node
				 * as its first keyword and pointer
				 */
				k.add(0,vp);
				p.add(0,new Long(kp.getPointer()));
				/*
				 * replace node and node2's parent's vp with
				 * old node2's last keyword
				 */
				replace(vp,kp.getKeyword());
			}

		}
		//node is node2's predecessor
		else
		{
			//they are leaf node
			if(node.isLeaf())
			{
				/*
				 * delete node2's first keyword and pointer
				 */
				kp=node2.deleteLeaf(0);
				/*
				 * add this keyword and pointer into node as
				 * its last keyword and pointer
				 */
				k.add(kp.getKeyword());
				p.add(p.size()-1,new Long(kp.getPointer()));
				/*
				 * replace node and node2's parent's vp with
				 * new node2's first keyword,here to make sure
				 * all keyword in new vp's left child is smaller
				 * than vp,and all keyword in vp's right child is
				 * equal to or bigger than vp
				 */
				replace(vp,node2.getKeyword(0));
			}
			//they are none leaf node
			else
			{
				/*
				 * delete node2's first keyword and pointer
				 */
				kp=node2.deleteLeaf(0);
				/*
				 * add vp and this pointer into node as its
				 * last keyword and pointer
				 */
				k.add(vp);
				p.add(new Long(kp.getPointer()));
				/*
				 * replace node and node2's parent's vp with
				 * old node2's first keyword
				 */
				replace(vp,kp.getKeyword());
			}
		}
	}
	
	public String toString()
	{
		int i;
		StringBuffer s;
		
		s=new StringBuffer();
		if(keyword.size()>0)
		{
			for(i=0;i<keyword.size();i++)
			{
				s.append(pointer.get(i)+" "+keyword.get(i)+" ");
			}
			s.append(pointer.get(i));
		}
		return s.toString();
	}

	/*
	 * the following methods are used to support varies kend of
	 * data type,all data type specified node must overwrite these
	 * method to support the specified kind of data type
	 */
	
	/**
	 * get a new empty data type specified node instance
	 * it thought this new node as a leaf node default
	 * @param addr
	 * the file pointer point to this node
	 * @return
	 */
	public abstract BPlusTreeNode getInstance(long addr);

	/**
	 * rebuild the data type specified node instance from byte array
	 * @param addr
	 * the file pointer point to this node
	 * @param node
	 * byte array contain this node's information
	 * @return
	 */
	public abstract BPlusTreeNode getInstance(long addr,byte[] node);

	/**
	 * get the node's binary byte array,used to save node into file
	 * @return
	 */
	public abstract byte[] getBytes();
	
	/**
	 * this method is used to convert keyword form Object form
	 * to Keyword form.a keyword's Object form is convinent to
	 * use,so user use keyword's Object form.but Object can not
	 * compare to each other,so in this package keyword's Keyword
	 * form is used.
	 * @param o
	 * the keyword's Object form
	 * @return
	 * the keyword's Keyword form
	 */
	public abstract Keyword buildKeyword(Object o);
	
	/**
	 * this is used to convert a kwyword's byte array form to the 
	 * Keyword form,it is used when keyword is received from remote
	 * host
	 * @param key
	 * keyword's byte array form
	 * @return
	 * keyword's Keyword form
	 */
	public abstract Keyword buildKeyword(byte[] key);
}