bplustreelong.cs

R树与B树的混合树

					// free it now
					this.owner.FreeBuffersOnAbort.Remove(oldbuffernumber);
					this.owner.deallocateBuffer(oldbuffernumber);
				} 
				else 
				{
					// free on commit
					this.owner.FreeBuffersOnCommit[oldbuffernumber] = oldbuffernumber;
				}
			}
			//this.owner.FreeBuffersOnAbort.Add(freshBufferNumber);
			this.owner.FreeBuffersOnAbort[freshBufferNumber] = freshBufferNumber;
			return freshBufferNumber;
		}
		void DumpToBuffer(long buffernumber) 
		{
			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() 
		{
			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>
		public string Delete(string key, out bool MergeMe) 
		{
			MergeMe = false; // assumption
			string result = null;
			if (this.isLeaf) 
			{
				return this.DeleteLeaf(key, out MergeMe);
			}
			int deleteposition = this.FindAtOrNextPosition(key, false);
			long deleteBufferNumber = 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 = this.MaterializeNodeAtIndex(deleteposition);
			bool MergeKid;
			string delresult = DeleteChild.Delete(key, out MergeKid);
			// delete succeeded... now fix up the child node if needed.
			this.Soil(); // redundant ?
			// bizarre special case for 2-3  or 3-4 trees -- empty leaf
			if (delresult!=null && this.owner.Compare(delresult, key)==0) // delresult.Equals(key)
			{
				if (this.Size>3) 
				{
					throw new BplusTreeException("assertion error: delete returned delete key for too large node size: "+this.Size);
				}
				// junk this leaf and shift everything over
				if (deleteposition==0) 
				{
					result = this.ChildKeys[deleteposition];
				} 
				else if (deleteposition==this.Size) 
				{
					this.ChildKeys[deleteposition-1] = null;
				}
				else
				{
					this.ChildKeys[deleteposition-1] = this.ChildKeys[deleteposition];
				}
				if (result!=null && this.owner.Compare(result, key)==0) // result.Equals(key)
				{
					// I'm not sure this ever happens
					this.MaterializeNodeAtIndex(1);
					result = this.MaterializedChildNodes[1].LeastKey();
				}
				DeleteChild.Free();
				for (int i=deleteposition; i<this.Size-1; i++) 
				{
					this.ChildKeys[i] = this.ChildKeys[i+1];
					this.MaterializedChildNodes[i] = this.MaterializedChildNodes[i+1];
					this.ChildBufferNumbers[i] = this.ChildBufferNumbers[i+1];
				}
				this.ChildKeys[this.Size-1] = null;
				if (deleteposition<this.Size) 
				{
					this.MaterializedChildNodes[this.Size-1] = this.MaterializedChildNodes[this.Size];
					this.ChildBufferNumbers[this.Size-1] = this.ChildBufferNumbers[this.Size];
				}
				this.MaterializedChildNodes[this.Size] = null;
				this.ChildBufferNumbers[this.Size] = BplusTreeLong.NULLBUFFERNUMBER;
				MergeMe = (this.SizeInUse()<this.Size/2);
				this.reParentAllChildren();
				return result;
			}
			if (deleteposition==0) 
			{
				// smallest key may have changed.
				result = delresult;
			}
				// update key array if needed
			else if (delresult!=null && deleteposition>0) 
			{
				if (this.owner.Compare(delresult,key)!=0) // !delresult.Equals(key)
				{
					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 = this.MaterializeNodeAtIndex(rightindex);
				} 
				else 
				{
					// merge with previous
					leftindex = deleteposition-1;
					rightindex = deleteposition;
					leftNode = this.MaterializeNodeAtIndex(leftindex);
					//keyBetween = this.ChildKeys[deleteBufferNumber-1];
					rightNode = DeleteChild;
				}
				keyBetween = this.ChildKeys[leftindex];
				string rightLeastKey;
				bool DeleteRight;
				Merge(leftNode, keyBetween, rightNode, out rightLeastKey, out DeleteRight);
				// delete the right node if needed.
				if (DeleteRight) 
				{
					for (int i=rightindex; i<this.Size; i++) 
					{
						this.ChildKeys[i-1] = this.ChildKeys[i];
						this.ChildBufferNumbers[i] = this.ChildBufferNumbers[i+1];
						this.MaterializedChildNodes[i] = this.MaterializedChildNodes[i+1];
					}
					this.ChildKeys[this.Size-1] = null;
					this.MaterializedChildNodes[this.Size] = null;
					this.ChildBufferNumbers[this.Size] = BplusTreeLong.NULLBUFFERNUMBER;
					this.reParentAllChildren();
					rightNode.Free();
					// does this node need merging?
					if (this.SizeInUse()<this.Size/2) 
					{
						MergeMe = true;
					}
				} 
				else 
				{
					// update the key entry
					this.ChildKeys[rightindex-1] = rightLeastKey;
				}
			}
			return result;
		}
		string LeastKey() 
		{
			string result = null;
			if (this.isLeaf) 
			{
				result = this.ChildKeys[0];
			} 
			else 
			{
				this.MaterializeNodeAtIndex(0);
				result = this.MaterializedChildNodes[0].LeastKey();
			}
			if (result==null) 
			{
				throw new BplusTreeException("no key found");
			}
			return result;
		}
		public static void Merge(BplusNode left, string KeyBetween, BplusNode right, out string rightLeastKey, 
			out bool DeleteRight) 
		{
			//System.Diagnostics.Debug.WriteLine("\r\n<br> merging "+right.myBufferNumber+" ("+KeyBetween+") "+left.myBufferNumber);
			//System.Diagnostics.Debug.WriteLine(left.owner.toHtml());
			rightLeastKey = null; // only if DeleteRight
			if (left.isLeaf || right.isLeaf) 
			{
				if (!(left.isLeaf&&right.isLeaf)) 
				{
					throw new BplusTreeException("can't merge leaf with non-leaf");
				}
				MergeLeaves(left, right, out DeleteRight);
				rightLeastKey = right.ChildKeys[0];
				return;
			}
			// merge non-leaves
			DeleteRight = false;
			string[] allkeys = new string[left.Size*2+1];
			long[] allseeks = new long[left.Size*2+2];
			BplusNode[] allMaterialized = new BplusNode[left.Size*2+2];
			if (left.ChildBufferNumbers[0]==BplusTreeLong.NULLBUFFERNUMBER ||
				right.ChildBufferNumbers[0]==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("cannot merge empty non-leaf with non-leaf");
			}
			int index = 0;
			allseeks[0] = left.ChildBufferNumbers[0];
			allMaterialized[0] = left.MaterializedChildNodes[0];
			for (int i=0; i<left.Size; i++) 
			{
				if (left.ChildKeys[i]==null) 
				{
					break;
				}
				allkeys[index] = left.ChildKeys[i];
				allseeks[index+1] = left.ChildBufferNumbers[i+1];
				allMaterialized[index+1] = left.MaterializedChildNodes[i+1];
				index++;
			}
			allkeys[index] = KeyBetween;
			index++;
			allseeks[index] = right.ChildBufferNumbers[0];
			allMaterialized[index] = right.MaterializedChildNodes[0];
			int rightcount = 0;
			for (int i=0; i<right.Size; i++) 
			{
				if (right.ChildKeys[i]==null) 
				{
					break;
				}
				allkeys[index] = right.ChildKeys[i];
				allseeks[index+1] = right.ChildBufferNumbers[i+1];
				allMaterialized[index+1] = right.MaterializedChildNodes[i+1];
				index++;
				rightcount++;
			}
			if (index<=left.Size) 
			{
				// it will all fit in one node
				//System.Diagnostics.Debug.WriteLine("deciding to forget "+right.myBufferNumber+" into "+left.myBufferNumber);
				DeleteRight = true;
				for (int i=0; i<index; i++) 
				{
					left.ChildKeys[i] = allkeys[i];
					left.ChildBufferNumbers[i] = allseeks[i];
					left.MaterializedChildNodes[i] = allMaterialized[i];
				}
				left.ChildBufferNumbers[index] = allseeks[index];
				left.MaterializedChildNodes[index] = allMaterialized[index];
				left.reParentAllChildren();
				left.Soil();
				right.Free();
				return;
			}
			// otherwise split the content between the nodes
			left.Clear();
			right.Clear();
			left.Soil();
			right.Soil();
			int leftcontent = index/2;
			int rightcontent = index-leftcontent-1;
			rightLeastKey = allkeys[leftcontent];
			int outputindex = 0;
			for (int i=0; i<leftcontent; i++) 
			{
				left.ChildKeys[i] = allkeys[outputindex];
				left.ChildBufferNumbers[i] = allseeks[outputindex];
				left.MaterializedChildNodes[i] = allMaterialized[outputindex];
				outputindex++;
			}
			rightLeastKey = allkeys[outputindex];
			left.ChildBufferNumbers[outputindex] = allseeks[outputindex];
			left.MaterializedChildNodes[outputindex] = allMaterialized[outputindex];
			outputindex++;
			rightcount = 0;
			for (int i=0; i<rightcontent; i++) 
			{
				right.ChildKeys[i] = allkeys[outputindex];
				right.ChildBufferNumbers[i] = allseeks[outputindex];
				right.MaterializedChildNodes[i] = allMaterialized[outputindex];
				outputindex++;
				rightcount++;
			}
			right.ChildBufferNumbers[rightcount] = allseeks[outputindex];
			right.MaterializedChildNodes[rightcount] = allMaterialized[outputindex];
			left.reParentAllChildren();
			right.reParentAllChildren();
		}
		public static void MergeLeaves(BplusNode left, BplusNode right, out bool DeleteRight) 
		{
			DeleteRight = false;
			string[] allkeys = new string[left.Size*2];
			long[] allseeks = new long[left.Size*2];
			int index = 0;
			for (int i=0; i<left.Size; i++) 
			{
				if (left.ChildKeys[i]==null) 
				{
					break;
				}
				allkeys[index] = left.ChildKeys[i];
				allseeks[index] = left.ChildBufferNumbers[i];
				index++;
			}
			for (int i=0; i<right.Size; i++) 
			{
				if (right.ChildKeys[i]==null) 
				{
					break;
				}
				allkeys[index] = right.ChildKeys[i];
				allseeks[index] = right.ChildBufferNumbers[i];
				index++;
			}
			if (index<=left.Size) 
			{
				left.Clear();
				DeleteRight = true;
				for (int i=0; i<index; i++) 
				{
					left.ChildKeys[i] = allkeys[i];
					left.ChildBufferNumbers[i] = allseeks[i];
				}
				right.Free();
				left.Soil();
				return;
			}
			left.Clear();
			right.Clear();
			left.Soil();
			right.Soil();
			int rightcontent = index/2;
			int leftcontent = index - rightcontent;
			int newindex = 0;
			for (int i=0; i<leftcontent; i++) 
			{
				left.ChildKeys[i] = allkeys[newindex];
				left.ChildBufferNumbers[i] = allseeks[newindex];
				newindex++;
			}
			for (int i=0; i<rightcontent; i++) 
			{
				right.ChildKeys[i] = allkeys[newindex];
				right.ChildBufferNumbers[i] = allseeks[newindex];
				newindex++;
			}
		}
		public string DeleteLeaf(string key, out bool MergeMe) 
		{
			string result = null;
			MergeMe = false;
			bool found = false;
			int deletelocation = 0;
			foreach (string thiskey in this.ChildKeys) 
			{
				// use comparison, not equals, in case different strings sometimes compare same
				if (thiskey!=null && this.owner.Compare(thiskey, key)==0) // thiskey.Equals(key)
				{
					found = true;
					break;
				}
				deletelocation++;
			}
			if (!found) 
			{
				throw new BplusTreeKeyMissing("cannot delete missing key: "+key);
			}
			this.Soil();
			// only keys are important...
			for (int i=deletelocation; i<this.Size-1; i++) 
			{
				this.ChildKeys[i] = this.ChildKeys[i+1];
				this.ChildBufferNumbers[i] = this.ChildBufferNumbers[i+1];
			}
			this.ChildKeys[this.Size-1] = null;
			//this.MaterializedChildNodes[endlocation+1] = null;