bplustreelong.java

R树与B树的混合树

package NET.sourceforge.BplusJ.BplusJ;
import java.util.*;

	/// <summary>
	/// Bplustree mapping fixed length Strings (byte sequences) to longs (seek positions in file indexed).
	/// "Next leaf pointer" is not used since it increases the chance of file corruption on failure.
	/// All modifications are "shadowed" until a flush of all modifications succeeds.  Modifications are
	/// "hardened" when the header record is rewritten with a new root.  This design trades a few "unneeded"
	/// buffer writes for lower likelihood of file corruption.
	/// </summary>
public class BplusTreeLong implements ITreeIndex
{
	public java.io.RandomAccessFile fromfile;
	// should be read only
	//public boolean DontUseCulture = false;
	//public System.Globalization.CultureInfo cultureContext;
	//System.Globalization.CompareInfo cmp = null;
	// should be read only
	public BufferFile buffers;
	// should be read only
	public int buffersize;
	// should be read only
	public int KeyLength;
	public long seekStart = 0;
	public static byte[] HEADERPREFIX = { 98, 112, 78, 98, 112 };
	// header consists of 
	// prefix | version | node size | key size | culture id | buffer number of root | buffer number of free list head
	int headersize = HEADERPREFIX.length + 1 + BufferFile.INTSTORAGE*3 + BufferFile.LONGSTORAGE*2;
	public static byte VERSION = 0;
	// for java, only allow the invariant culture.
	public static int INVARIANTCULTUREID = 127;
	// size of allocated key space in each node (should be a read only property)
	public int NodeSize;
	BplusNode root = null;
	long rootSeek; 
	long freeHeadSeek;
	public long LastValueFound;
	public Hashtable FreeBuffersOnCommit = new Hashtable();
	public Hashtable FreeBuffersOnAbort = new Hashtable();
	Hashtable IdToTerminalNode = new Hashtable();
	Hashtable TerminalNodeToId = new Hashtable();
	int TerminalNodeCount = 0;
	int LowerTerminalNodeCount = 0;
	int FifoLimit = 100;
	public static int NULLBUFFERNUMBER = -1;
	public static byte NONLEAF = 0, LEAF = 1, FREE = 2;

	public BplusTreeLong(java.io.RandomAccessFile fromfile, int NodeSize, int KeyLength, long StartSeek, int CultureId)
		throws Exception
	{
		//this.cultureContext = new System.Globalization.CultureInfo(CultureId);
		if (CultureId!=INVARIANTCULTUREID) 
		{
			throw new BplusTreeException("BplusJ only supports the invariant culture");
		}
		//this.cmp = this.cultureContext.CompareInfo;
		this.fromfile = fromfile;
		this.NodeSize = NodeSize;
		this.seekStart = StartSeek;
		// add in key prefix overhead
		this.KeyLength = KeyLength + BufferFile.SHORTSTORAGE;
		this.rootSeek = NULLBUFFERNUMBER;
		this.root = null;
		this.freeHeadSeek = NULLBUFFERNUMBER;
		this.SanityCheck();
	}
		
	public int MaxKeyLength() 
	{
		return this.KeyLength-BufferFile.SHORTSTORAGE;
	}
	public void Shutdown()
		throws Exception
	{
		//this.fromfile.Flush();
		this.fromfile.close();
	}
	public int Compare(String left, String right) 
		throws Exception
	{
		//System.Globalization.CompareInfo cmp = this.cultureContext.CompareInfo;
		return left.compareTo(right); // only lexicographic compare allowed for java
		//			if (this.cultureContext==null || this.DontUseCulture) 
		//			{
		//				// no culture context: use miscellaneous total ordering on unicode Strings
		//				int i = 0;
		//				while (i<left.length && i<right.length) 
		//				{
		//					int leftOrd = Convert.ToInt32(left[i]);
		//					int rightOrd = Convert.ToInt32(right[i]);
		//					if (leftOrd<rightOrd) 
		//					{
		//						return -1;
		//					}
		//					if (leftOrd>rightOrd)
		//					{
		//						return 1;
		//					}
		//					i++;
		//				}
		//				if (left.length<right.length) 
		//				{
		//					return -1;
		//				}
		//				if (left.length>right.length) 
		//				{
		//					return 1;
		//				}
		//				return 0;
		//			}
		//			if (this.cmp==null) 
		//			{
		//				this.cmp = this.cultureContext.CompareInfo;
		//			}
		//			return this.cmp.Compare(left, right);
	}
	public void SanityCheck(boolean strong) 
		throws Exception
	{
		this.SanityCheck();
		if (strong) 
		{
			this.Recover(false);
			// look at all deferred deallocations -- they should not be free
			byte[] buffer = new byte[1];
			//foreach (Object thing in this.FreeBuffersOnAbort) 
			//for (int i=0; i<this.FreeBuffersOnAbort.size(); i++)
			for (Enumeration e=this.FreeBuffersOnAbort.keys(); e.hasMoreElements(); )
			{
				//Object thing = this.FreeBuffersOnAbort.get(i);
				Object thing = e.nextElement();
				long buffernumber = ((Long) thing).longValue();
				this.buffers.getBuffer(buffernumber, buffer, 0, 1);
				if (buffer[0]==FREE) 
				{
					throw new BplusTreeException("free on abort buffer already marked free "+buffernumber);
				}
			}
			//foreach (Object thing in this.FreeBuffersOnCommit) 
			//for (int i=0; i<this.FreeBuffersOnCommit.size(); i++)
			for (Enumeration e=this.FreeBuffersOnCommit.keys(); e.hasMoreElements(); )
			{
				//Object thing = this.FreeBuffersOnCommit.get(i);
				Object thing = e.nextElement();
				long buffernumber = ((Long) thing).longValue();
				this.buffers.getBuffer(buffernumber, buffer, 0, 1);
				if (buffer[0]==FREE) 
				{
					throw new BplusTreeException("free on commit buffer already marked free "+buffernumber);
				}
			}
		}
	}
	public void Recover(boolean CorrectErrors) 
		throws Exception
	{
		Hashtable visited = new Hashtable();
		if (this.root!=null) 
		{
			// find all reachable nodes
			this.root.SanityCheck(visited);
		}
		// traverse the free list
		long freebuffernumber = this.freeHeadSeek;
		while (freebuffernumber!=NULLBUFFERNUMBER) 
		{
			if (visited.containsKey(new Long(freebuffernumber)) ) 
			{
				throw new BplusTreeException("free buffer visited twice "+freebuffernumber);
			}
			//visited[freebuffernumber] = FREE;
			visited.put(new Long(freebuffernumber), new Byte(FREE));
			freebuffernumber = this.parseFreeBuffer(freebuffernumber);
		}
		// find out what is missing
		Hashtable Missing = new Hashtable();
		long maxbuffer = this.buffers.nextBufferNumber();
		for (long i=0; i<maxbuffer; i++) 
		{
			if (!visited.containsKey(new Long(i))) 
			{
				//Missing[i] = i;
				Missing.put(new Long(i), new Long(i));
			}
		}
		// remove from missing any free-on-commit blocks
		//foreach (Object thing in this.FreeBuffersOnCommit) 
		//for (int i=0; i<this.FreeBuffersOnCommit.size(); i++)
		for (Enumeration e=this.FreeBuffersOnCommit.keys(); e.hasMoreElements(); )
		{
			//long tobefreed = (long) thing;
			//Missing.Remove(tobefreed);
			Missing.remove( e.nextElement() );
		}
		// add the missing values to the free list
		if (CorrectErrors) 
		{
			//				if (Missing.size()>0) 
			//				{
			//					System.Diagnostics.Debug.WriteLine("correcting "+Missing.Count+" unreachable buffers");
			//				}
			//				ArrayList missingL = new ArrayList();
			//				foreach (DictionaryEntry d in Missing) 
			//				{
			//					missingL.Add(d.Key);
			//				}
			//				missingL.Sort();
			//				missingL.Reverse();
			//				foreach (Object thing in missingL) 
			//				{
			//					long buffernumber = (long) thing;
			//					this.deallocateBuffer(buffernumber);
			//				}
			for (Enumeration e = Missing.keys(); e.hasMoreElements(); ) 
			{
				long buffernumber = ((Long) e.nextElement()).longValue();
				this.deallocateBuffer(buffernumber);
			}
			//this.ResetBookkeeping();
		} 
		else if (Missing.size()>0)
		{
			//				String buffers = "";
			//				foreach (DictionaryEntry thing in Missing) 
			//				{
			//					buffers += " "+thing.Key;
			//				}
			throw new BplusTreeException("found "+Missing.size()+" unreachable buffers.");
		}
	}
	public void SerializationCheck()  
		throws Exception
	{
		if (this.root==null) 
		{
			throw new BplusTreeException("serialization check requires initialized root, sorry");
		}
		this.root.SerializationCheck();
	}
	void SanityCheck() 
		throws Exception
	{
		if (this.NodeSize<2) 
		{
			throw new BplusTreeException("node size must be larger than 2");
		}
		if (this.KeyLength<5) 
		{
			throw new BplusTreeException("Key length must be larger than 5");
		}
		if (this.seekStart<0) 
		{
			throw new BplusTreeException("start seek may not be negative");
		}
		// compute the buffer size
		// indicator | seek position | [ key storage | seek position ]*
		int keystorage = this.KeyLength + BufferFile.SHORTSTORAGE;
		this.buffersize = 1 + BufferFile.LONGSTORAGE + (keystorage + BufferFile.LONGSTORAGE)*this.NodeSize;
	}
	public String toHtml() throws Exception
	{
		java.io.CharArrayWriter sb = new java.io.CharArrayWriter();
		sb.write("<h1>BplusTree</h1>\r\n");
		sb.write("\r\n<br> nodesize="+this.NodeSize);
		sb.write("\r\n<br> seekstart="+this.seekStart);
		sb.write("\r\n<br> rootseek="+this.rootSeek);
		sb.write("\r\n<br> free on commit "+this.FreeBuffersOnCommit.size()+" ::");
		//foreach (Object thing in this.FreeBuffersOnCommit) 
		//for (int i=0; i<this.FreeBuffersOnCommit.size(); i++)
		//{
		//	sb.write(" "+this.FreeBuffersOnCommit.get(i));
		//}
		sb.write("\r\n<br> Freebuffers : ");
		Hashtable freevisit = new Hashtable();
		long free = this.freeHeadSeek;
		String allfree = "freehead="+free+" :: ";
		while (free!=NULLBUFFERNUMBER) 
		{
			allfree = allfree+" "+free;
			Long Lfree = new Long(free);
			if (freevisit.containsKey(Lfree)) 
			{
				throw new BplusTreeException("cycle in freelist "+free);
			}
			//freevisit[free] = free;
			freevisit.put(Lfree, Lfree);
			free = this.parseFreeBuffer(free);
		}
		if (allfree.length()==0) 
		{
			sb.write("empty list");
		} 
		else 
		{
			sb.write(allfree);
		}
		sb.write("\r\n<br> free on abort "+this.FreeBuffersOnAbort.size()+" ::");
		//foreach (Object thing in this.FreeBuffersOnAbort) 
		//for (int i=0; i<this.FreeBuffersOnAbort.size(); i++)
		//{
		//	sb.write(" "+this.FreeBuffersOnAbort.get(i));
		//}
		sb.write("\r\n<br>\r\n");
	
		//... add more
		if (this.root==null) 
		{
			sb.write("<br><b>NULL ROOT</b>\r\n");
		} 
		else 
		{
			this.root.AsHtml(sb);
		}
		return sb.toString();
	}
	public BplusTreeLong(java.io.RandomAccessFile fromfile, int KeyLength, int NodeSize, int CultureId) //:
		//this(fromfile, NodeSize, KeyLength, (long)0, CultureId) 
		throws Exception
	{
		// just start seek at 0
		this(fromfile, NodeSize, KeyLength, (long)0, CultureId);
	}
	public static BplusTreeLong SetupFromExistingStream(java.io.RandomAccessFile fromfile) 
		throws Exception
	{
		return SetupFromExistingStream(fromfile, (long)0);
	}
	public static BplusTreeLong SetupFromExistingStream(java.io.RandomAccessFile fromfile, long StartSeek)
		throws Exception 
	{
		//int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
		BplusTreeLong result = new BplusTreeLong(fromfile, 7, 100, StartSeek, INVARIANTCULTUREID); // dummy values for nodesize, keysize
		result.readHeader();
		result.buffers = BufferFile.SetupFromExistingStream(fromfile, StartSeek+result.headersize);
		if (result.buffers.buffersize != result.buffersize) 
		{
			throw new BplusTreeException("inner and outer buffer sizes should match");
		}
		if (result.rootSeek!=NULLBUFFERNUMBER) 
		{
			result.root = new BplusNode(result, null, -1, true);
			result.root.LoadFromBuffer(result.rootSeek);
		}
		return result;
	}
	public static BplusTreeLong InitializeInStream(java.io.RandomAccessFile fromfile, int KeyLength, int NodeSize) 
		throws Exception
	{
		//int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
		return InitializeInStream(fromfile, KeyLength, NodeSize, INVARIANTCULTUREID);
	}
	public static BplusTreeLong InitializeInStream(java.io.RandomAccessFile fromfile, int KeyLength, int NodeSize, int CultureId) 
		throws Exception
	{
		return InitializeInStream(fromfile, KeyLength, NodeSize, CultureId, (long)0);
	}
	public static BplusTreeLong InitializeInStream(java.io.RandomAccessFile fromfile, int KeyLength, int NodeSize, int CultureId, long StartSeek) 
		throws Exception
	{
		if (fromfile.length()>StartSeek) 
		{
			throw new BplusTreeException("can't initialize bplus tree inside written area of stream");
		}
		BplusTreeLong result = new BplusTreeLong(fromfile, NodeSize, KeyLength, StartSeek, CultureId);
		result.setHeader();
		result.buffers = BufferFile.InitializeBufferFileInStream(fromfile, result.buffersize, StartSeek+result.headersize);
		return result;
	}
	public void SetFootPrintLimit(int limit) 
		throws Exception
	{
		if (limit<5) 
		{
			throw new BplusTreeException("foot print limit less than 5 is too small");
		}
		this.FifoLimit = limit;
	}
	public void RemoveKey(String key) 
		throws Exception
	{
		if (this.root==null) 
		{
			throw new BplusTreeKeyMissing("tree is empty: cannot delete");
		}
		boolean MergeMe;
		BplusNode theroot = this.root;
		BplusNode.Delete deletion = theroot.delete(key);
		MergeMe = deletion.MergeMe;
		// if the root is not a leaf and contains only one child (no key), reroot
		if (MergeMe && !this.root.isLeaf && this.root.SizeInUse()==0) 
		{
			this.root = this.root.FirstChild();
			this.rootSeek = this.root.makeRoot();