bplustreelong.cs

R树与B树的混合树

using System;
using System.Collections;

// delete next

namespace BplusDotNet
{
	/// <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: ITreeIndex
	{
		public System.IO.Stream fromfile;
		// should be read only
		public bool 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 const byte VERSION = 0;
		// 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 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(System.IO.Stream fromfile, int NodeSize, int KeyLength, long StartSeek, int CultureId)
		{
			this.cultureContext = new System.Globalization.CultureInfo(CultureId);
			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()
		{
			this.fromfile.Flush();
			this.fromfile.Close();
		}
		public int Compare(string left, string right) 
		{
			//System.Globalization.CompareInfo cmp = this.cultureContext.CompareInfo;
			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(bool strong) 
		{
			this.SanityCheck();
			if (strong) 
			{
				this.Recover(false);
				// look at all deferred deallocations -- they should not be free
				byte[] buffer = new byte[1];
				foreach (DictionaryEntry thing in this.FreeBuffersOnAbort) 
				{
					long buffernumber = (long) thing.Key;
					this.buffers.getBuffer(buffernumber, buffer, 0, 1);
					if (buffer[0]==FREE) 
					{
						throw new BplusTreeException("free on abort buffer already marked free "+buffernumber);
					}
				}
				foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
				{
					long buffernumber = (long) thing.Key;
					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(bool CorrectErrors) 
		{
			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(freebuffernumber) ) 
				{
					throw new BplusTreeException("free buffer visited twice "+freebuffernumber);
				}
				visited[freebuffernumber] = 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(i)) 
				{
					Missing[i] = i;
				}
			}
			// remove from missing any free-on-commit blocks
			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
			{
				long tobefreed = (long) thing.Key;
				Missing.Remove(tobefreed);
			}
			// add the missing values to the free list
			if (CorrectErrors) 
			{
				if (Missing.Count>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);
				}
				//this.ResetBookkeeping();
			} 
			else if (Missing.Count>0)
			{
				string buffers = "";
				foreach (DictionaryEntry thing in Missing) 
				{
					buffers += " "+thing.Key;
				}
				throw new BplusTreeException("found "+Missing.Count+" unreachable buffers."+buffers);
			}
		}
		public void SerializationCheck()  
		{
			if (this.root==null) 
			{
				throw new BplusTreeException("serialization check requires initialized root, sorry");
			}
			this.root.SerializationCheck();
		}
		void SanityCheck() 
		{
			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() 
		{
			System.Text.StringBuilder sb = new System.Text.StringBuilder();
			sb.Append("<h1>BplusTree</h1>\r\n");
			sb.Append("\r\n<br> nodesize="+this.NodeSize);
			sb.Append("\r\n<br> seekstart="+this.seekStart);
			sb.Append("\r\n<br> rootseek="+this.rootSeek);
			sb.Append("\r\n<br> free on commit "+this.FreeBuffersOnCommit.Count+" ::");
			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
			{
				sb.Append(" "+thing.Key);
			}
			sb.Append("\r\n<br> Freebuffers : ");
			Hashtable freevisit = new Hashtable();
			long free = this.freeHeadSeek;
			string allfree = "freehead="+free+" :: ";
			while (free!=NULLBUFFERNUMBER) 
			{
				allfree = allfree+" "+free;
				if (freevisit.ContainsKey(free)) 
				{
					throw new BplusTreeException("cycle in freelist "+free);
				}
				freevisit[free] = free;
				free = this.parseFreeBuffer(free);
			}
			if (allfree.Length==0) 
			{
				sb.Append("empty list");
			} 
			else 
			{
				sb.Append(allfree);
			}
			foreach (DictionaryEntry thing in this.FreeBuffersOnCommit) 
			{
				sb.Append(" "+thing.Key);
			}
			sb.Append("\r\n<br> free on abort "+this.FreeBuffersOnAbort.Count+" ::");
			foreach (DictionaryEntry thing in this.FreeBuffersOnAbort) 
			{
				sb.Append(" "+thing.Key);
			}
			sb.Append("\r\n<br>\r\n");

			//... add more
			if (this.root==null) 
			{
				sb.Append("<br><b>NULL ROOT</b>\r\n");
			} 
			else 
			{
				this.root.AsHtml(sb);
			}
			return sb.ToString();
		}
		public BplusTreeLong(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId):
			this(fromfile, NodeSize, KeyLength, (long)0, CultureId) 
		{
			// just start seek at 0
		}
		public static BplusTreeLong SetupFromExistingStream(System.IO.Stream fromfile) 
		{
			return SetupFromExistingStream(fromfile, (long)0);
		}
		public static BplusTreeLong SetupFromExistingStream(System.IO.Stream fromfile, long StartSeek) 
		{
			int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
			BplusTreeLong result = new BplusTreeLong(fromfile, 7, 100, StartSeek, dummyId); // 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(System.IO.Stream fromfile, int KeyLength, int NodeSize) 
		{
			int dummyId = System.Globalization.CultureInfo.InvariantCulture.LCID;
			return InitializeInStream(fromfile, KeyLength, NodeSize, dummyId);
		}
		public static BplusTreeLong InitializeInStream(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId) 
		{
			return InitializeInStream(fromfile, KeyLength, NodeSize, CultureId, (long)0);
		}
		public static BplusTreeLong InitializeInStream(System.IO.Stream fromfile, int KeyLength, int NodeSize, int CultureId, long StartSeek) 
		{
			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) 
		{
			if (limit<5) 
			{
				throw new BplusTreeException("foot print limit less than 5 is too small");
			}
			this.FifoLimit = limit;
		}
		public void RemoveKey(string key) 
		{
			if (this.root==null) 
			{
				throw new BplusTreeKeyMissing("tree is empty: cannot delete");
			}
			bool MergeMe;
			BplusNode theroot = this.root;
			theroot.Delete(key, out 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();
				theroot.Free();
			}
		}
		public long this[string key] 
		{
			get 
			{
				long valueFound;
				bool test = this.ContainsKey(key, out valueFound);
				if (!test) 
				{
					throw new BplusTreeKeyMissing("no such key found: "+key);
				}
				return valueFound;
			}
			set 
			{
				if (!BplusNode.KeyOK(key, this)) 
				{
					throw new BplusTreeBadKeyValue("null or too large key cannot be inserted into tree: "+key);
				}
				bool rootinit = false;
				if (this.root==null) 
				{
					// allocate root
					this.root = new BplusNode(this, null, -1, true);
					rootinit = true;
					//this.rootSeek = root.DumpToFreshBuffer();
				}
				// insert into root...
				string splitString;
				BplusNode splitNode;
				root.Insert(key, value, out splitString, out splitNode);
				if (splitNode!=null) 
				{
					// split of root: make a new root.
					rootinit = true;
					BplusNode oldRoot = this.root;
					this.root = BplusNode.BinaryRoot(oldRoot, splitString, splitNode, this);
				}
				if (rootinit) 
				{
					this.rootSeek = root.DumpToFreshBuffer();
				}
				// check size in memory