bplustreelong.cs

R树与B树的混合树

					this.owner.deallocateBuffer(this.myBufferNumber);
				} 
				else 
				{
					// free on commit
					//this.owner.FreeBuffersOnCommit.Add(this.myBufferNumber);
					this.owner.FreeBuffersOnCommit[this.myBufferNumber] = this.myBufferNumber;
				}
			}
			this.myBufferNumber = BplusTreeLong.NULLBUFFERNUMBER; // don't do it twice...
		}
		public void SerializationCheck() 
		{ 
			BplusNode A = new BplusNode(this.owner, null, -1, false);
			for (int i=0; i<this.Size; i++) 
			{
				long j = i*((long)0xf0f0f0f0f0f0f01);
				A.ChildBufferNumbers[i] = j;
				A.ChildKeys[i] = "k"+i;
			}
			A.ChildBufferNumbers[this.Size] = 7;
			A.TestRebuffer();
			A.isLeaf = true;
			for (int i=0; i<this.Size; i++) 
			{
				long j = -i*((long)0x3e3e3e3e3e3e666);
				A.ChildBufferNumbers[i] = j;
				A.ChildKeys[i] = "key"+i;
			}
			A.ChildBufferNumbers[this.Size] = -9097;
			A.TestRebuffer();
		}
		void TestRebuffer() 
		{
			bool IL = this.isLeaf;
			long[] Ns = this.ChildBufferNumbers;
			string[] Ks = this.ChildKeys;
			byte[] buffer = new byte[this.owner.buffersize];
			this.Dump(buffer);
			this.Clear();
			this.Load(buffer);
			for (int i=0; i<this.Size; i++) 
			{
				if (this.ChildBufferNumbers[i]!=Ns[i]) 
				{
					throw new BplusTreeException("didn't get back buffernumber "+i+" got "+this.ChildBufferNumbers[i]+" not "+Ns[i]);
				}
				if (!this.ChildKeys[i].Equals(Ks[i])) 
				{
					throw new BplusTreeException("didn't get back key "+i+" got "+this.ChildKeys[i]+" not "+Ks[i]);
				}
			}
			if (this.ChildBufferNumbers[this.Size]!=Ns[this.Size]) 
			{
				throw new BplusTreeException("didn't get back buffernumber "+this.Size+" got "+this.ChildBufferNumbers[this.Size]+" not "+Ns[this.Size]);
			}
			if (this.isLeaf!=IL) 
			{
				throw new BplusTreeException("isLeaf should be "+IL+" got "+this.isLeaf);
			}
		}
		public string SanityCheck(Hashtable visited) 
		{
			string result = null;
			if (visited==null) 
			{
				visited = new Hashtable();
			}
			if (visited.ContainsKey(this)) 
			{
				throw new BplusTreeException("node visited twice "+this.myBufferNumber);
			}
			visited[this] = this.myBufferNumber;
			if (this.myBufferNumber!=BplusTreeLong.NULLBUFFERNUMBER) 
			{
				if (visited.ContainsKey(this.myBufferNumber))
				{
					throw new BplusTreeException("buffer number seen twice "+this.myBufferNumber);
				}
				visited[this.myBufferNumber] = this;
			}
			if (this.parent!=null) 
			{
				if (this.parent.isLeaf) 
				{
					throw new BplusTreeException("parent is leaf");
				}
				this.parent.MaterializeNodeAtIndex(this.indexInParent);
				if (this.parent.MaterializedChildNodes[this.indexInParent]!=this) 
				{
					throw new BplusTreeException("incorrect index in parent");
				}
				// since not at root there should be at least size/2 keys
				int limit = this.Size/2;
				if (this.isLeaf) 
				{
					limit--;
				}
				for (int i=0; i<limit; i++) 
				{
					if (this.ChildKeys[i]==null) 
					{
						throw new BplusTreeException("null child in first half");
					}
				}
			}
			result = this.ChildKeys[0]; // for leaf
			if (!this.isLeaf) 
			{
				this.MaterializeNodeAtIndex(0);
				result = this.MaterializedChildNodes[0].SanityCheck(visited);
				for (int i=0; i<this.Size; i++) 
				{
					if (this.ChildKeys[i]==null) 
					{
						break;
					}
					this.MaterializeNodeAtIndex(i+1);
					string least = this.MaterializedChildNodes[i+1].SanityCheck(visited);
					if (least==null) 
					{
						throw new BplusTreeException("null least in child doesn't match node entry "+this.ChildKeys[i]);
					}
					if (!least.Equals(this.ChildKeys[i])) 
					{
						throw new BplusTreeException("least in child "+least+" doesn't match node entry "+this.ChildKeys[i]);
					}
				}
			}
			// look for duplicate keys
			string lastkey = this.ChildKeys[0];
			for (int i=1; i<this.Size; i++) 
			{
				if (this.ChildKeys[i]==null) 
				{
					break;
				}
				if (lastkey.Equals(this.ChildKeys[i]) ) 
				{
					throw new BplusTreeException("duplicate key in node "+lastkey);
				}
				lastkey = this.ChildKeys[i];
			}
			return result;
		}
		void Destroy() 
		{
			// make sure the structure is useless, it should no longer be used.
			this.owner = null;
			this.parent = null;
			this.Size = -100;
			this.ChildBufferNumbers = null;
			this.ChildKeys = null;
			this.MaterializedChildNodes = null;
			this.myBufferNumber = BplusTreeLong.NULLBUFFERNUMBER;
			this.indexInParent = -100;
			this.Dirty = false;
		}
		public int SizeInUse() 
		{
			int result = 0;
			for (int i=0; i<this.Size; i++) 
			{
				if (this.ChildKeys[i]==null) 
				{
					break;
				}
				result++;
			}
			return result;
		}
		public static BplusNode BinaryRoot(BplusNode LeftNode, string key, BplusNode RightNode, BplusTreeLong owner) 
		{
			BplusNode newRoot = new BplusNode(owner, null, -1, false);
			//newRoot.Clear(); // redundant
			newRoot.ChildKeys[0] = key;
			LeftNode.Reparent(newRoot, 0);
			RightNode.Reparent(newRoot, 1);
			// new root is stored elsewhere
			return newRoot;
		}
		void Reparent(BplusNode newParent, int ParentIndex) 
		{
			// keys and existing parent structure must be updated elsewhere.
			this.parent = newParent;
			this.indexInParent = ParentIndex;
			newParent.ChildBufferNumbers[ParentIndex] = this.myBufferNumber;
			newParent.MaterializedChildNodes[ParentIndex] = this;
			// parent is no longer terminal
			this.owner.ForgetTerminalNode(parent);
		}
		void Clear() 
		{
			this.ChildBufferNumbers = new long[this.Size+1];
			this.ChildKeys = new string[this.Size];
			this.MaterializedChildNodes = new BplusNode[this.Size+1];
			for (int i=0; i<this.Size; i++) 
			{
				this.ChildBufferNumbers[i] = BplusTreeLong.NULLBUFFERNUMBER;
				this.MaterializedChildNodes[i] = null;
				this.ChildKeys[i] = null;
			}
			this.ChildBufferNumbers[this.Size] = BplusTreeLong.NULLBUFFERNUMBER;
			this.MaterializedChildNodes[this.Size] = null;
			// this is now a terminal node
			this.owner.RecordTerminalNode(this);
		}
		/// <summary>
		/// Find first index in self associated with a key same or greater than CompareKey
		/// </summary>
		/// <param name="CompareKey">CompareKey</param>
		/// <param name="LookPastOnly">if true and this is a leaf then look for a greater value</param>
		/// <returns>lowest index of same or greater key or this.Size if no greater key.</returns>
		int FindAtOrNextPosition(string CompareKey, bool LookPastOnly) 
		{
			int insertposition = 0;
			//System.Globalization.CultureInfo culture = this.owner.cultureContext;
			//System.Globalization.CompareInfo cmp = culture.CompareInfo;
			if (this.isLeaf && !LookPastOnly) 
			{
				// look for exact match or greater or null
				while (insertposition<this.Size && this.ChildKeys[insertposition]!=null &&
					//cmp.Compare(this.ChildKeys[insertposition], CompareKey)<0) 
					this.owner.Compare(this.ChildKeys[insertposition], CompareKey)<0)
				{
					insertposition++;
				}
			} 
			else 
			{
				// look for greater or null only
				while (insertposition<this.Size && this.ChildKeys[insertposition]!=null &&
					this.owner.Compare(this.ChildKeys[insertposition], CompareKey)<=0) 
				{
					insertposition++;
				}
			}
			return insertposition;
		}
		/// <summary>
		/// Find the first key below atIndex, or if no such node traverse to the next key to the right.
		/// If no such key exists, return nulls.
		/// </summary>
		/// <param name="atIndex">where to look in this node</param>
		/// <param name="FoundInLeaf">leaf where found</param>
		/// <param name="KeyFound">key value found</param>
		void TraverseToFollowingKey(int atIndex, out BplusNode FoundInLeaf, out string KeyFound) 
		{
			FoundInLeaf = null;
			KeyFound = null;
			bool LookInParent = false;
			if (this.isLeaf) 
			{
				LookInParent = (atIndex>=this.Size) || (this.ChildKeys[atIndex]==null);
			} 
			else 
			{
				LookInParent = (atIndex>this.Size) ||
					(atIndex>0 && this.ChildKeys[atIndex-1]==null);
			}
			if (LookInParent) 
			{
				// if it's anywhere it's in the next child of parent
				if (this.parent!=null && this.indexInParent>=0) 
				{
					this.parent.TraverseToFollowingKey(this.indexInParent+1, out FoundInLeaf, out KeyFound);
					return;
				} 
				else 
				{
					return; // no such following key
				}
			}
			if (this.isLeaf) 
			{
				// leaf, we found it.
				FoundInLeaf = this;
				KeyFound = this.ChildKeys[atIndex];
				return;
			} 
			else 
			{
				// nonleaf, look in child (if there is one)
				if (atIndex==0 || this.ChildKeys[atIndex-1]!=null) 
				{
					BplusNode thechild = this.MaterializeNodeAtIndex(atIndex);
					thechild.TraverseToFollowingKey(0, out FoundInLeaf, out KeyFound);
				}
			}
		}
		public bool FindMatch(string CompareKey, out long ValueFound) 
		{
			ValueFound = 0; // dummy value on failure
			BplusNode leaf;
			int position = this.FindAtOrNextPositionInLeaf(CompareKey, out leaf, false);
			if (position<leaf.Size) 
			{
				string key = leaf.ChildKeys[position];
				if ((key!=null) && this.owner.Compare(key, CompareKey)==0) //(key.Equals(CompareKey)
				{
					ValueFound = leaf.ChildBufferNumbers[position];
					return true;
				}
			}
			return false;
		}
		public string FindNextKey(string CompareKey) 
		{
			string result = null;
			BplusNode leaf;
			int position = this.FindAtOrNextPositionInLeaf(CompareKey, out leaf, true);
			if (position>=leaf.Size || leaf.ChildKeys[position]==null) 
			{
				// try to traverse to the right.
				BplusNode newleaf;
				leaf.TraverseToFollowingKey(leaf.Size, out newleaf, out result);
			} 
			else 
			{
				result = leaf.ChildKeys[position];
			}
			return result;
		}
		/// <summary>
		/// Find near-index of comparekey in leaf under this node. 
		/// </summary>
		/// <param name="CompareKey">the key to look for</param>
		/// <param name="inLeaf">the leaf where found</param>
		/// <param name="LookPastOnly">If true then only look for a greater value, not an exact match.</param>
		/// <returns>index of match in leaf</returns>
		int FindAtOrNextPositionInLeaf(string CompareKey, out BplusNode inLeaf, bool LookPastOnly) 
		{
			int myposition = this.FindAtOrNextPosition(CompareKey, LookPastOnly);
			if (this.isLeaf) 
			{
				inLeaf = this;
				return myposition;
			}
			long childBufferNumber = this.ChildBufferNumbers[myposition];
			if (childBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("can't search null subtree");
			}
			BplusNode child = this.MaterializeNodeAtIndex(myposition);
			return child.FindAtOrNextPositionInLeaf(CompareKey, out inLeaf, LookPastOnly);
		}
		BplusNode MaterializeNodeAtIndex(int myposition) 
		{
			if (this.isLeaf) 
			{
				throw new BplusTreeException("cannot materialize child for leaf");
			}
			long childBufferNumber = this.ChildBufferNumbers[myposition];
			if (childBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("can't search null subtree at position "+myposition+" in "+this.myBufferNumber);
			}
			// is it already materialized?
			BplusNode result = this.MaterializedChildNodes[myposition];
			if (result!=null) 
			{
				return result;
			}
			// otherwise read it in...
			result = new BplusNode(this.owner, this, myposition, true); // dummy isLeaf value
			result.LoadFromBuffer(childBufferNumber);
			this.MaterializedChildNodes[myposition] = result;
			// no longer terminal
			this.owner.ForgetTerminalNode(this);
			return result;
		}
		public void LoadFromBuffer(long bufferNumber) 
		{
			// freelist bookkeeping done elsewhere
			string parentinfo = "no parent"; // debug
			if (this.parent!=null) 
			{
				parentinfo = "parent="+parent.myBufferNumber; // debug
			}
			//System.Diagnostics.Debug.WriteLine("\r\n<br> loading "+this.indexInParent+" from "+bufferNumber+" for "+parentinfo);
			byte[] rawdata = new byte[this.owner.buffersize];
			this.owner.buffers.getBuffer(bufferNumber, rawdata, 0, rawdata.Length);
			this.Load(rawdata);
			this.Dirty = false;
			this.myBufferNumber = bufferNumber;
			// it's terminal until a child is materialized
			this.owner.RecordTerminalNode(this);
		}
		public long DumpToFreshBuffer() 
		{
			long oldbuffernumber = this.myBufferNumber;
			long freshBufferNumber = this.owner.allocateBuffer();
			//System.Diagnostics.Debug.WriteLine("\r\n<br> dumping "+this.indexInParent+" from "+oldbuffernumber+" to "+freshBufferNumber);
			this.DumpToBuffer(freshBufferNumber);
			if (oldbuffernumber!=BplusTreeLong.NULLBUFFERNUMBER) 
			{
				//this.owner.FreeBuffersOnCommit.Add(oldbuffernumber);
				if (this.owner.FreeBuffersOnAbort.ContainsKey(oldbuffernumber)) 
				{