bplustreelong.java

R树与B树的混合树

				{
					// nonleaf, look in child (if there is one)
					if (atIndex==0 || BplusNode.this.ChildKeys[atIndex-1]!=null) 
					{
						BplusNode thechild = BplusNode.this.MaterializeNodeAtIndex(atIndex);
						TraverseToFollowingKey t = thechild.traverseToFollowingKey(0); //, out FoundInLeaf, out KeyFound);this.FoundInLeaf = t.FoundInLeaf;
						this.KeyFound = t.KeyFound;
						this.FoundInLeaf = t.FoundInLeaf;
					}
				}
			}
		}
		public boolean FindMatch(String CompareKey) //, out long ValueFound) 
			throws Exception
		{
			this.LastValueFound = 0; // dummy value on failure
			BplusNode leaf;
			//int position = this.FindAtOrNextPositionInLeaf(CompareKey, out leaf, false);
			FindAtOrNextPositionInLeaf f = new FindAtOrNextPositionInLeaf(CompareKey, false);
			leaf = f.inLeaf;
			int position = f.atPosition;
			if (position<leaf.Size) 
			{
				String key = leaf.ChildKeys[position];
				if ((key!=null) && this.owner.Compare(key, CompareKey)==0) //(key.equals(CompareKey)
				{
					this.LastValueFound = leaf.ChildBufferNumbers[position];
					return true;
				}
			}
			return false;
		}
		public String FindNextKey(String CompareKey) 
			throws Exception
		{
			String result = null;
			BplusNode leaf;
			//int position = this.FindAtOrNextPositionInLeaf(CompareKey, out leaf, true);
			FindAtOrNextPositionInLeaf f = new FindAtOrNextPositionInLeaf(CompareKey, true);
			leaf = f.inLeaf;
			int position = f.atPosition;
			if (position>=leaf.Size || leaf.ChildKeys[position]==null) 
			{
				// try to traverse to the right.
				BplusNode newleaf;
				TraverseToFollowingKey t = leaf.traverseToFollowingKey(leaf.Size); //, out newleaf, out result);
				newleaf = t.FoundInLeaf;
				result = t.KeyFound;
			} 
			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>
		FindAtOrNextPositionInLeaf findAtOrNextPositionInLeaf(String CompareKey, boolean LookPastOnly) 
			throws Exception
		{
			return new FindAtOrNextPositionInLeaf(CompareKey, LookPastOnly);
		}
		class FindAtOrNextPositionInLeaf 
		{
			public BplusNode inLeaf;
			public int atPosition;
			public FindAtOrNextPositionInLeaf(String CompareKey, boolean LookPastOnly) 
				throws Exception
			{
				int myposition = BplusNode.this.FindAtOrNextPosition(CompareKey, LookPastOnly);
				if (BplusNode.this.isLeaf) 
				{
					this.inLeaf = BplusNode.this;
					this.atPosition = myposition;
					return;
				}
				long childBufferNumber = BplusNode.this.ChildBufferNumbers[myposition];
				if (childBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
				{
					throw new BplusTreeException("can't search null subtree");
				}
				BplusNode child = BplusNode.this.MaterializeNodeAtIndex(myposition);
				FindAtOrNextPositionInLeaf f = child.findAtOrNextPositionInLeaf(CompareKey, LookPastOnly);
				this.inLeaf = f.inLeaf;
				this.atPosition = f.atPosition;
			}
		}
		BplusNode MaterializeNodeAtIndex(int myposition) 
			throws Exception
		{
			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) 
			throws Exception
		{
			// 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() throws Exception
		{
			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) 
			{
				Long L = new Long(oldbuffernumber);
				//this.owner.FreeBuffersOnCommit.Add(oldbuffernumber);
				if (this.owner.FreeBuffersOnAbort.containsKey(L)) 
				{
					// free it now
					this.owner.FreeBuffersOnAbort.remove(L);
					this.owner.deallocateBuffer(oldbuffernumber);
				} 
				else 
				{
					// free on commit
					this.owner.FreeBuffersOnCommit.put(L,L);
				}
			}
			//this.owner.FreeBuffersOnAbort.Add(freshBufferNumber);
			Long F = new Long(freshBufferNumber);
			this.owner.FreeBuffersOnAbort.put(F, F);
			return freshBufferNumber;
		}
		void DumpToBuffer(long buffernumber) 
			throws Exception
		{
			byte[] rawdata = new byte[this.owner.buffersize];
			this.Dump(rawdata);
			this.owner.buffers.setBuffer(buffernumber, rawdata, 0, rawdata.length);
			this.Dirty = false;
			this.myBufferNumber = buffernumber;
			if (this.parent!=null && this.indexInParent>=0 &&
				this.parent.ChildBufferNumbers[this.indexInParent]!=buffernumber) 
			{
				if (this.parent.MaterializedChildNodes[this.indexInParent]!=this) 
				{
					throw new BplusTreeException("invalid parent connection "+this.parent.myBufferNumber+" at "+this.indexInParent);
				}
				this.parent.ChildBufferNumbers[this.indexInParent] = buffernumber;
				this.parent.Soil();
			}
		}
		void reParentAllChildren() 
			throws Exception
		{
			for (int i=0; i<=this.Size; i++) 
			{
				BplusNode thisnode = this.MaterializedChildNodes[i];
				if (thisnode!=null) 
				{
					thisnode.Reparent(this, i);
				}
			}
		}
		/// <summary>
		/// Delete entry for key
		/// </summary>
		/// <param name="key">key to delete</param>
		/// <param name="MergeMe">true if the node is less than half full after deletion</param>
		/// <returns>null unless the smallest key under this node has changed in which case it returns the smallest key.</returns>
		Delete delete(String Key) throws Exception
		{
			return new Delete(Key);
		}
		public class Delete
		{
			public String smallestKey;
			public boolean MergeMe;
			public Delete(String key) 
				throws Exception
			{
				this.MergeMe = false; // assumption
				this.smallestKey = null;
				if (BplusNode.this.isLeaf) 
				{
					this.DeleteLeaf(key);
					return;
				}
				int deleteposition = BplusNode.this.FindAtOrNextPosition(key, false);
				long deleteBufferNumber = BplusNode.this.ChildBufferNumbers[deleteposition];
				if (deleteBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
				{
					throw new BplusTreeException("key not followed by buffer number in non-leaf (del)");
				}
				// del in subtree
				BplusNode DeleteChild = BplusNode.this.MaterializeNodeAtIndex(deleteposition);
				boolean MergeKid;
				//String delresult = DeleteChild.Delete(key, out MergeKid);
				Delete deletion = DeleteChild.delete(key);
				MergeKid = deletion.MergeMe;
				String delresult = deletion.smallestKey;
				// delete succeeded... now fix up the child node if needed.
				BplusNode.this.Soil(); // redundant ?
				// bizarre special case for 2-3  or 3-4 trees -- empty leaf
				if (delresult!=null && BplusNode.this.owner.Compare(delresult, key)==0) // delresult.equals(key)
				{
					if (BplusNode.this.Size>3) 
					{
						throw new BplusTreeException("assertion error: delete returned delete key for too large node size: "+BplusNode.this.Size);
					}
					// junk this leaf and shift everything over
					if (deleteposition==0) 
					{
						this.smallestKey = BplusNode.this.ChildKeys[deleteposition];
					} 
					else if (deleteposition==BplusNode.this.Size) 
					{
						BplusNode.this.ChildKeys[deleteposition-1] = null;
					}
					else
					{
						BplusNode.this.ChildKeys[deleteposition-1] = BplusNode.this.ChildKeys[deleteposition];
					}
					if (this.smallestKey!=null && BplusNode.this.owner.Compare(this.smallestKey, key)==0) // result.equals(key)
					{
						// I'm not sure this ever happens
						BplusNode.this.MaterializeNodeAtIndex(1);
						this.smallestKey = BplusNode.this.MaterializedChildNodes[1].LeastKey();
					}
					DeleteChild.Free();
					for (int i=deleteposition; i<BplusNode.this.Size-1; i++) 
					{
						BplusNode.this.ChildKeys[i] = BplusNode.this.ChildKeys[i+1];
						BplusNode.this.MaterializedChildNodes[i] = BplusNode.this.MaterializedChildNodes[i+1];
						BplusNode.this.ChildBufferNumbers[i] = BplusNode.this.ChildBufferNumbers[i+1];
					}
					BplusNode.this.ChildKeys[BplusNode.this.Size-1] = null;
					if (deleteposition<BplusNode.this.Size) 
					{
						BplusNode.this.MaterializedChildNodes[BplusNode.this.Size-1] = BplusNode.this.MaterializedChildNodes[BplusNode.this.Size];
						BplusNode.this.ChildBufferNumbers[BplusNode.this.Size-1] = BplusNode.this.ChildBufferNumbers[BplusNode.this.Size];
					}
					BplusNode.this.MaterializedChildNodes[BplusNode.this.Size] = null;
					BplusNode.this.ChildBufferNumbers[BplusNode.this.Size] = BplusTreeLong.NULLBUFFERNUMBER;
					MergeMe = (BplusNode.this.SizeInUse()<BplusNode.this.Size/2);
					BplusNode.this.reParentAllChildren();
					//return result;
					return;
				}
				if (deleteposition==0) 
				{
					// smallest key may have changed.
					this.smallestKey = delresult;
				}
					// update key array if needed
				else if (delresult!=null && deleteposition>0) 
				{
					if (BplusNode.this.owner.Compare(delresult,key)!=0) // !delresult.equals(key)
					{
						BplusNode.this.ChildKeys[deleteposition-1] = delresult;
					} 
				}
				// if the child needs merging... do it
				if (MergeKid) 
				{
					int leftindex, rightindex;
					BplusNode leftNode;
					BplusNode rightNode;
					String keyBetween;
					if (deleteposition==0) 
					{
						// merge with next
						leftindex = deleteposition;
						rightindex = deleteposition+1;
						leftNode = DeleteChild;
						//keyBetween = this.ChildKeys[deleteposition];
						rightNode = BplusNode.this.MaterializeNodeAtIndex(rightindex);
					} 
					else 
					{
						// merge with previous
						leftindex = deleteposition-1;
						rightindex = deleteposition;
						leftNode = BplusNode.this.MaterializeNodeAtIndex(leftindex);
						//keyBetween = this.ChildKeys[deleteBufferNumber-1];
						rightNode = DeleteChild;
					}
					keyBetween = BplusNode.this.ChildKeys[leftindex];
					String rightLeastKey;
					boolean DeleteRight;
					rightLeastKey = Merge(leftNode, keyBetween, rightNode);//, out rightLeastKey, out DeleteRight);
					DeleteRight = !rightNode.isValid;
					// delete the right node if needed.
					if (DeleteRight) 
					{
						for (int i=rightindex; i<BplusNode.this.Size; i++) 
						{
							BplusNode.this.ChildKeys[i-1] = BplusNode.this.ChildKeys[i];
							BplusNode.this.ChildBufferNumbers[i] = BplusNode.this.ChildBufferNumbers[i+1];
							BplusNode.this.MaterializedChildNodes[i] = BplusNode.this.MaterializedChildNodes[i+1];
						}
						BplusNode.this.ChildKeys[BplusNode.this.Size-1] = null;
						BplusNode.this.MaterializedChildNodes[BplusNode.this.Size] = null;
						BplusNode.this.ChildBufferNumbers[BplusNode.this.Size] = BplusTreeLong.NULLBUFFERNUMBER;
						BplusNode.this.reParentAllChildren();
						rightNode.Free();
						// does this node need merging?
						if (BplusNode.this.SizeInUse()<BplusNode.this.Size/2) 
						{
							MergeMe = true;
						}
					} 
					else 
					{
						// update the key entry
						BplusNode.this.ChildKeys[rightindex-1] = rightLeastKey;
					}
				}
				//return result;
			}
			
			public String DeleteLeaf(String key) 
				throws Exception
			{
				this.smallestKey  = null;
				this.MergeMe = false;
				boolean found = false;
				int deletelocation = 0;
				//foreach (String thiskey in this.ChildKeys) 
				for (int i=0; i<BplusNode.this.ChildKeys.length; i++)
				{
					String thiskey = BplusNode.this.ChildKeys[i];
					// use comparison, not equals, in case different Strings sometimes compare same
					if (thiskey!=null && BplusNode.this.owner.Compare(thiskey, key)==0) // thiskey.equals(key)
					{
						found = true;
						deletelocation = i;
						break;
					}
					//deletelocation++;
				}
				if (!found) 
				{
					throw new BplusTreeKeyMissing("cannot delete missing key: "+key);
				}
				BplusNode.this.Soil();
				// only keys are important...
				for (int i=deletelocation; i<BplusNode.this.Size-1; i++) 
				{
					BplusNode.this.ChildKeys[i] = BplusNode.this.ChildKeys[i+1];
					BplusNode.this.ChildBufferNumbers[i] = BplusNode.this.ChildBufferNumbers[i+1];
				}
				BplusNode.this.ChildKeys[BplusNode.this.Size-1] = null;
				//this.MaterializedChildNodes[endlocation+1] = null;
				//this.ChildBufferNumbers[endlocation+1] = BplusTreeLong.NULLBUFFERNUMBER;
				if (BplusNode.this.SizeInUse()<BplusNode.this.Size/2)
				{
					this.MergeMe = true;
				}
				if (deletelocation==0) 
				{
					this.smallestKey  = BplusNode.this.ChildKeys[0];
					// this is only relevant for the case of 2-3 trees (empty leaf after deletion)
					if (this.smallestKey ==null)