bplustreelong.java

R树与B树的混合树

					{
						this.smallestKey = key; // deleted value
					}
				}
				return this.smallestKey;
			}
		}
		String LeastKey() 
			throws Exception
		{
			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 String Merge(BplusNode left, String KeyBetween, BplusNode right) //, out String rightLeastKey, 
			//out boolean DeleteRight) 
			throws Exception
		{
			//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);
				String rightLeastKey = right.ChildKeys[0];
				return rightLeastKey;
			}
			// 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;
				right.isValid = false;
				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 null;
			}
			// otherwise split the content between the nodes
			left.Clear();
			right.Clear();
			left.Soil();
			right.Soil();
			int leftcontent = index/2;
			int rightcontent = index-leftcontent-1;
			String 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();
			return rightLeastKey;
		}
		public static void MergeLeaves(BplusNode left, BplusNode right) //, out boolean DeleteRight) 
			throws Exception
		{
			//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;
				right.isValid = false;
				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 boolean MergeMe) 
		//		{
		//			String result = null;
		//			MergeMe = false;
		//			boolean 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;
		//			//this.ChildBufferNumbers[endlocation+1] = BplusTreeLong.NULLBUFFERNUMBER;
		//			if (this.SizeInUse()<this.Size/2)
		//			{
		//				MergeMe = true;
		//			}
		//			if (deletelocation==0) 
		//			{
		//				result = this.ChildKeys[0];
		//				// this is only relevant for the case of 2-3 trees (empty leaf after deletion)
		//				if (result==null) 
		//				{
		//					result = key; // deleted value
		//				}
		//			}
		//			return result;
		//		}
		/// <summary>
		/// insert key/position entry in self 
		/// </summary>
		/// <param name="key">Key to associate with the leaf</param>
		/// <param name="position">position associated with key in external structur</param>
		/// <param name="splitString">if not null then the smallest key in the new split leaf</param>
		/// <param name="splitNode">if not null then the node was split and this is the leaf to the right.</param>
		/// <returns>null unless the smallest key under this node has changed, in which case it returns the smallest key.</returns>
		public String Insert(String key, long position) //, out String splitString, out BplusNode splitNode) 
			throws Exception
		{
			this.splitString = null;
			this.splitNode = null;
			if (this.isLeaf) 
			{
				return this.InsertLeaf(key, position); //, out splitString, out splitNode);
			}
			int insertposition = this.FindAtOrNextPosition(key, false);
			long insertBufferNumber = this.ChildBufferNumbers[insertposition];
			if (insertBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("key not followed by buffer number in non-leaf");
			}
			// insert in subtree
			BplusNode InsertChild = this.MaterializeNodeAtIndex(insertposition);
			BplusNode childSplit;
			String childSplitString;
			String childInsert = InsertChild.Insert(key, position); //, out childSplitString, out childSplit);
			childSplit = InsertChild.splitNode;
			childSplitString = InsertChild.splitString;
			InsertChild.splitNode = null;
			InsertChild.splitString = null;
			// if there was a split the node must expand
			if (childSplit!=null) 
			{
				// insert the child
				this.Soil(); // redundant -- a child will have a change so this node will need to be copied
				int newChildPosition = insertposition+1;
				boolean dosplit = false;
				// if there is no free space we must do a split
				if (this.ChildBufferNumbers[this.Size]!=BplusTreeLong.NULLBUFFERNUMBER) 
				{
					dosplit = true;
					this.PrepareForSplit();
				}
				// bubble over the current values to make space for new child
				for (int i=this.ChildKeys.length-2; i>=newChildPosition-1; i--) 
				{
					int i1 = i+1;
					int i2 = i1+1;
					this.ChildKeys[i1] = this.ChildKeys[i];
					this.ChildBufferNumbers[i2] = this.ChildBufferNumbers[i1];
					BplusNode childNode = this.MaterializedChildNodes[i2] = this.MaterializedChildNodes[i1];
				}
				// record the new child
				this.ChildKeys[newChildPosition-1] = childSplitString;
				//this.MaterializedChildNodes[newChildPosition] = childSplit;
				//this.ChildBufferNumbers[newChildPosition] = childSplit.myBufferNumber;
				childSplit.Reparent(this, newChildPosition);
				// split, if needed
				if (dosplit) 
				{
					int splitpoint = this.MaterializedChildNodes.length/2-1;
					this.splitString = this.ChildKeys[splitpoint];
					this.splitNode = new BplusNode(this.owner, this.parent, -1, this.isLeaf);
					// make copy of expanded node structure
					BplusNode[] materialized = this.MaterializedChildNodes;
					long[] buffernumbers = this.ChildBufferNumbers;
					String[] keys = this.ChildKeys;
					// repair the expanded node
					this.ChildKeys = new String[this.Size];
					this.MaterializedChildNodes = new BplusNode[this.Size+1];
					this.ChildBufferNumbers = new long[this.Size+1];
					this.Clear();
					//Array.Copy(materialized, 0, this.MaterializedChildNodes, 0, splitpoint+1);
					//Array.Copy(buffernumbers, 0, this.ChildBufferNumbers, 0, splitpoint+1);
					for (int i=0; i<splitpoint+1; i++) 
					{
						this.MaterializedChildNodes[i] = materialized[i];
						this.ChildBufferNumbers[i] = buffernumbers[i];
					}
					//Array.Copy(keys, 0, this.ChildKeys, 0, splitpoint);
					for (int i=0; i<splitpoint; i++) 
					{
						this.ChildKeys[i] = keys[i];
					}
					// initialize the new node
					splitNode.Clear(); // redundant.
					int remainingKeys = this.Size-splitpoint;
					//Array.Copy(materialized, splitpoint+1, splitNode.MaterializedChildNodes, 0, remainingKeys+1);
					//Array.Copy(buffernumbers, splitpoint+1, splitNode.ChildBufferNumbers, 0, remainingKeys+1);
					for (int i=0; i<remainingKeys+1; i++) 
					{
						splitNode.MaterializedChildNodes[i] = materialized[i+splitpoint+1];
						splitNode.ChildBufferNumbers[i] = buffernumbers[i+splitpoint+1];
					}
					//Array.Copy(keys, splitpoint+1, splitNode.ChildKeys, 0, remainingKeys);
					for (int i=0; i<remainingKeys; i++) 
					{
						splitNode.ChildKeys[i] = keys[i+splitpoint+1];
					}
					// fix pointers in materialized children of splitnode
					splitNode.reParentAllChildren();
					// store the new node
					splitNode.DumpToFreshBuffer();
					splitNode.CheckIfTerminal();
					splitNode.Soil();
					this.CheckIfTerminal();
				}
				// fix pointers in children
				this.reParentAllChildren();
			}
			if (insertposition==0) 
			{
				// the smallest key may have changed
				return childInsert;
			}
			return null;  // no change in smallest key
		}
		/// <summary>
		/// Check to see if this is a terminal node, if so record it, otherwise forget it
		/// </summary>
		void CheckIfTerminal() 
			throws Exception
		{
			if (!this.isLeaf) 
			{
				for (int i=0; i<this.Size+1; i++) 
				{
					if (this.MaterializedChildNodes[i]!=null) 
					{
						this.owner.ForgetTerminalNode(this);
						return;
					}
				}
			}
			this.owner.RecordTerminalNode(this);
		}
		/// <summary>
		/// insert key/position entry in self (as leaf)
		/// </summary>
		/// <param name="key">Key to associate with the leaf</param>
		/// <param name="position">position associated with key in external structure</param>
		/// <param name="splitString">if not null then the smallest key in the new split leaf</param>
		/// <param name="splitNode">if not null then the node was split and this is the leaf to the right.</param>
		/// <returns>smallest key