bplustreenode.java

支持并发访问的B+树

/*
 * Created on Jun 6, 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.util.*;

/**
 * Description: <br>
 * &nbsp&nbsp this is the common B+ tree's node,use this to support varies data type.a
 * specified data type extends this to support that kind of data type's node.
 * more over,this class is a connection of the abstract tree node and the node's storage
 * in the underlying file.abstract tree node can do search,insert,delete
 * operation and the underlying storage convert abstract tree node to fixed
 * length byte array and save it into file.<br>
 * &nbsp&nbsp BPlusTreeNode use a List to store keywords,in this List,it use the
 * keyword's Keyword form to support the compareTo and equals method.but when user
 * use a BPlusTree,they use the keyword's Object form,because the Object form is more
 * common and more convenient,the buildKeyword method convert a Object form's keyword
 * to a Keyword form's keyword<br>
 * &nbsp&nbsp according to the define of the B+ tree's node,a node is a empty node or
 * it must have at least two pointer.because insert and delete operation once deal with
 * a keyword/pointer pair,so when a node build,add a NULL pointer into it to keep the
 * pointer number is 1 more than keyword number,so when the node is empty,it still 
 * contain one pointer,and so when the node is build it contain none keyword but a NULL pointer
 * @abstract
 * @keywords
 * @author nay0648
 * @version last modified:Jun 6, 2004
 */
public abstract class BPlusTreeNode
{
/*
 * the boolean value true and false.used to save in
 * file to see whether a node is a leaf node or not
 */
protected static final byte TRUE=(byte)0xff;
protected static final byte FALSE=(byte)0x00;
/*
 * a node's fixed head length,contain a byte to see whether
 * this node is a leaf or not and the valid keyword number
 */
public static final int HEAD_LENGTH=5;
/*
 * thest static varibles are metadata of tree node. because a tree's
 * node is the same size and not change when tree is constructed,so they
 * are static.before get a node instance,metadata must be initialized by
 * call BPlusTree.init method
 */
protected static int rank;//tree rank
protected static int nodelength;//node length
protected static int keywordlength;//keyword length
protected static int datatype;//data type
/*
 * to see this node is leaf or not,when the node is build,it regard this
 * node as a leaf node by default,call isLeaf method can set this node is
 * leaf or not
 */
private boolean isleaf=true;
/*
 * file pointer point to this node,this is used when compare
 * node relationship chain
 */
private long addr;
private List keyword;//keyword list
private List pointer;//pointer list

	/**
	 * only build a node builder use this method,exactaly,it is called
	 * by Class.forName().newInstance() method,when build a node instance,
	 * use node builder to call getInstance method
	 */
	public BPlusTreeNode()
	{
		//construct list
		keyword=new ArrayList();
		pointer=new ArrayList();
		/*
		 * beceuse the pointer number is 1 more than the keyword number,
		 * and insert,delete operation deal with keyword/pointer pair,
		 * so add a NULL pointer when a node constructed.
		 */
		pointer.add(new Long(BPlusTree.NULL));
	}
	
	/*
	 * these methods used to visit List contain keyword and pointer,
	 * use these method to get high performance,but any update on these
	 * list will interfere the node
	 */
	
	/**
	 * get the List contain keyword
	 * @return
	 */
	public List getKeywordList()
	{
		return keyword;
	}

	/**
	 * set a List as the keyword List
	 * @param keyword
	 * the keyword list
	 */
	public void setKeywordList(List keyword)
	{
		this.keyword=keyword;
	}
	
	/**
	 * get the List contain pointer
	 * @return
	 */
	public List getPointerList()
	{
		return pointer;
	}

	/**
	 * set a List as pointer List
	 * @param pointer
	 * the pointer list
	 */
	public void setPointerList(List pointer)
	{
		this.pointer=pointer;
	}

	/**
	 * init the meta data of a node to support a specified data 
	 * type,this must be done when getInstance() first be called.
	 * @param rank
	 * the B+ tree's rank
	 * @param nodelength
	 * node length measured in byte
	 * @param keywordlength
	 * keyword's length measured in byte
	 * @param datatype
	 * keyword's datatype
	 */
	public static void init(int rank,int nodelength,int keywordlength,int datatype)
	{
		BPlusTreeNode.rank=rank;
		BPlusTreeNode.nodelength=nodelength;
		BPlusTreeNode.keywordlength=keywordlength;
		BPlusTreeNode.datatype=datatype;
	}

	/**
	 * get valid keyword number in this node
	 * @return
	 */
	public int getValid()
	{
		return keyword.size();
	}
	
	/**
	 * get the last pointer of this node,if this node
	 * is a leaf node,it get the pointer point to the
	 * next leaf
	 * @return
	 */
	public long getLast()
	{
		return ((Long)pointer.get(pointer.size()-1)).longValue();
	}
	
	/**
	 * set the last pointer of this node,if this node
	 * is a leaf node,it set the pointer point to the
	 * next leaf
	 * @param p
	 * pointer
	 */
	public void setLast(long p)
	{
		pointer.set(pointer.size()-1,new Long(p));
	}
	
	/**
	 * get the first pointer of the pointer list
	 * @return
	 */
	public long getFirst()
	{
		return ((Long)pointer.get(0)).longValue();
	}
	
	/**
	 * set the first pointer of the pointer list
	 * @param p
	 * file pointer
	 */
	public void setFirst(long p)
	{
		pointer.set(0,new Long(p));
	}
	
	/**
	 * get the file pointer point to this node
	 * @return
	 */
	public long getAddr()
	{
		return addr;
	}
	
	/**
	 * set the file pointer point to this node
	 * @param addr
	 * a file pointer point to this node
	 */
	public void setAddr(long addr)
	{
		this.addr=addr;
	}
	
	/**
	 * get pointer in specified index
	 * @param index
	 * pointer index
	 * @return
	 */
	public long getPointer(int index)
	{
		return ((Long)pointer.get(index)).longValue();
	}
	
	/**
	 * get the Long form of the pointer in specified index
	 * @param index
	 * pointer index
	 * @return
	 */
	public Long getPointerObject(int index)
	{
		return (Long)pointer.get(index);
	}
	
	/**
	 * get keyword in specified index
	 * @param index
	 * keyword index
	 * @return
	 */
	public Keyword getKeyword(int index)
	{
		return (Keyword)keyword.get(index);
	}
	
	/**
	 * to see this node is leaf or not
	 * @return return true if this node is leaf
	 */
	public boolean isLeaf()
	{
		return isleaf;
	}
	
	/**
	 * set this node to a leaf node or a none
	 * leaf node
	 * @param isleaf
	 * true means this node is a leaf node and false means
	 * this node is a none leaf node
	 */
	public void isLeaf(boolean isleaf)
	{
		this.isleaf=isleaf;
	}
	
	/**
	 * to see a child node of this node is the predecessor of another
	 * child node of this node or not.such as: parent.isPred(node1,node2)
	 * return true is node1 is node2's predecessor
	 * @param addrp
	 * the predecessor node's address
	 * @param addr
	 * the child node's address
	 * @return
	 * if addrp is addr's predecessor return true,else return false
	 */
	public boolean isPred(long addrp,long addr)
	{
		int index;
		
		index=pointer.indexOf(new Long(addr));
		if(index<1) return false;
		else return ((Long)pointer.get(index-1)).longValue()==addrp;
	}
	
	/**
	 * to see if the argument node's keyword and pointer
	 * can combine with this node
	 * @param node
	 * a tree node need to combine
	 * @return
	 * return true if the two node can combine
	 */
	public boolean canCombine(BPlusTreeNode node)
	{
		/*
		 * when compare two leaf node,the last pointer is not useful,so
		 * compare keyword number,when compare two none leaf node,the last
		 * pointer is useful,so compare pointer number
		 */
		if(node.isLeaf()) return node.getValid()+getValid()<=rank-1;
		else return node.getValid()+1+pointer.size()<=rank;
	}
	
	/**
	 * get the specified keyword's index in this node
	 * @param keyword
	 * the specified keyword
	 * @return return -1 if not found
	 */
	public int indexOf(Keyword keyword)
	{
		/*
		 * before the keyword is Keyword form in the List,
		 * so here use Keyword form to compare 
		 */
		return this.keyword.indexOf(keyword);
	}
	
	/**
	 * get the specified pointer's index in this node
	 * @param pointer
	 * the specified pointer in this node
	 * @return return -1 if not found
	 */
	public int indexOf(long pointer)
	{
		return this.pointer.indexOf(new Long(pointer));
	}
	
	/**
	 * get the left pointer of the specified index's keyword
	 * @param keyword
	 * the keyword's index
	 * @return
	 */
	public long getLeftPointer(int keyword)
	{
		return ((Long)pointer.get(keyword)).longValue();
	}
	
	/**
	 * get the right pointer of the specified index's keyword
	 * @param keyword
	 * the keyword's index
	 * @return
	 */
	public long getRightPointer(int keyword)
	{
		return ((Long)pointer.get(keyword+1)).longValue();
	}

	/**
	 * add a keyword into the end of the keyword list,
	 * this is used to rebuild node from byte array
	 * @param key
	 * keyword in Object form
	 */
	protected void addKeyword(Keyword key)
	{
		keyword.add(key);
	}
	
	/**
	 * remove the keyword in the specified index
	 * @param index
	 * keyword index
	 * @return
	 */
	protected Keyword removeKeyword(int index)
	{
		return (Keyword)keyword.remove(index);
	}
	
	/**
	 * add a pointer to the end of the pointer list,
	 * this is used to rebuild node from byte array
	 * @param p
	 * pointer
	 */
	protected void addPointer(long p)
	{
		pointer.add(new Long(p));
	}
	
	/**
	 * remove the pointer in specified index
	 * @param index
	 * pointer index
	 * @return
	 */
	protected long removePointer(int index)
	{
		return ((Long)pointer.remove(index)).longValue();
	}
	
	/**
	 * to see if this node have space to insert a keyword
	 * @return
	 */
	public boolean haveSpace()
	{
		/*
		 * the rank is equals to the pointer number,so the rank-1
		 * is the max keyword number a node can hold
		 */
		return keyword.size()<BPlusTreeNode.rank-1;
	}
	
	/**
	 * insert a keyword and its pointer into this leaf node.
	 * the keyword's pointer is thought as the keyword's
	 * left pointer,so just 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 insertLeaf(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,new Long(p));
	}

	/**
	 * insert a keyword and its pointer into this leaf node.
	 * the keyword's pointer is thought as the keyword's
	 * left pointer,so just leaf node use this method to
	 * add a new keyword/pointer pair into node in order
	 * @param pair