bplustreelong.java

R树与B树的混合树

		index+= BufferFile.LONGSTORAGE;
		BufferFile.Store(this.freeHeadSeek, result, index);
		return result;
	}
	
	public static class BplusNode 
	{
		public boolean isLeaf = true;
		// the maximum number of children to each node.
		int Size;
		// false if the node is no longer active and should not be used.
		boolean isValid = true;
		// true if the materialized node needs to be persisted.
		boolean Dirty = true;
		// if non-root reference to the parent node containing this node
		BplusNode parent = null;
		// tree containing this node
		BplusTreeLong owner = null;
		// buffer number of this node
		public long myBufferNumber = BplusTreeLong.NULLBUFFERNUMBER;
		// number of children used by this node
		//int NumberOfValidKids = 0;
		long[] ChildBufferNumbers;
		String[] ChildKeys;
		BplusNode[] MaterializedChildNodes;
		int indexInParent = -1;
		/// Temporary slots for use in splitting, fetching
		public BplusNode splitNode = null;
		public String splitString = null;
		public long LastValueFound = 0;
		/// <summary>
		/// Create a new BplusNode and install in parent if parent is not null.
		/// </summary>
		/// <param name="owner">tree containing the node</param>
		/// <param name="parent">parent node (if provided)</param>
		/// <param name="indexInParent">location in parent if provided</param>
		public BplusNode(BplusTreeLong owner, BplusNode parent, int indexInParent, boolean isLeaf) 
			throws Exception
		{
			this.isLeaf = isLeaf;
			this.owner = owner;
			this.parent = parent;
			this.Size = owner.NodeSize;
			this.isValid = true;
			this.Dirty = true;
			//			this.ChildBufferNumbers = new long[this.Size+1];
			//			this.ChildKeys = new String[this.Size];
			//			this.MaterializedChildNodes = new BplusNode[this.Size+1];
			this.Clear();
			if (parent!=null && indexInParent>=0) 
			{
				if (indexInParent>this.Size) 
				{
					throw new BplusTreeException("parent index too large");
				}
				// key info, etc, set elsewhere
				this.parent.MaterializedChildNodes[indexInParent] = this;
				this.myBufferNumber = this.parent.ChildBufferNumbers[indexInParent];
				this.indexInParent = indexInParent;
			}
		}
		public BplusNode FirstChild() 
			throws Exception
		{
			BplusNode result = this.MaterializeNodeAtIndex(0);
			if (result==null) 
			{
				throw new BplusTreeException("no first child");
			}
			return result;
		}
		public long makeRoot() 
			throws Exception
		{
			this.parent = null;
			this.indexInParent = -1;
			if (this.myBufferNumber==BplusTreeLong.NULLBUFFERNUMBER) 
			{
				throw new BplusTreeException("no root seek allocated to new root");
			}
			return this.myBufferNumber;
		}
		public void Free() throws Exception
		{
			if (this.myBufferNumber!=BplusTreeLong.NULLBUFFERNUMBER) 
			{
				Long L = new Long(this.myBufferNumber);
				if (this.owner.FreeBuffersOnAbort.containsKey(L)) 
				{
					// free it now
					this.owner.FreeBuffersOnAbort.remove(L);
					this.owner.deallocateBuffer(this.myBufferNumber);
				} 
				else 
				{
					// free on commit
					//this.owner.FreeBuffersOnCommit.Add(this.myBufferNumber);
					this.owner.FreeBuffersOnCommit.put(L,L);
				}
			}
			this.myBufferNumber = BplusTreeLong.NULLBUFFERNUMBER; // don't do it twice...
		}
		public void SerializationCheck() 
			throws Exception
		{ 
			BplusNode A = new BplusNode(this.owner, null, -1, false);
			for (int i=0; i<this.Size; i++) 
			{
				long j = i*((long)0xf0f0f0f0f0f0f01L);
				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)0x3e3e3e3e3e3e666L);
				A.ChildBufferNumbers[i] = j;
				A.ChildKeys[i] = "key"+i;
			}
			A.ChildBufferNumbers[this.Size] = -9097;
			A.TestRebuffer();
		}
		void TestRebuffer() 
			throws Exception
		{
			boolean 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) 
			throws Exception
		{
			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;
			visited.put(this, new Long(this.myBufferNumber));
			if (this.myBufferNumber!=BplusTreeLong.NULLBUFFERNUMBER) 
			{
				Long bf = new Long(this.myBufferNumber);
				if (visited.containsKey(bf))
				{
					throw new BplusTreeException("buffer number seen twice "+this.myBufferNumber);
				}
				//visited[bf] = this;
				visited.put(bf, 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) 
			throws Exception
		{
			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) 
			throws Exception
		{
			// 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() 
			throws Exception
		{
			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, boolean LookPastOnly) 
			throws Exception
		{
			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>
		TraverseToFollowingKey traverseToFollowingKey(int atIndex) 
			throws Exception
		{
			return new TraverseToFollowingKey(atIndex);
		}
		class TraverseToFollowingKey 
		{
			public BplusNode FoundInLeaf = null;
			public String KeyFound = null;
			public TraverseToFollowingKey(int atIndex) 
				throws Exception
			{
				this.FoundInLeaf = null;
				this.KeyFound = null;
				boolean LookInParent = false;
				if (BplusNode.this.isLeaf) 
				{
					LookInParent = (atIndex>=BplusNode.this.Size) || (BplusNode.this.ChildKeys[atIndex]==null);
				} 
				else 
				{
					LookInParent = (atIndex>BplusNode.this.Size) ||
						(atIndex>0 && BplusNode.this.ChildKeys[atIndex-1]==null);
				}
				if (LookInParent) 
				{
					// if it's anywhere it's in the next child of parent
					if (BplusNode.this.parent!=null && BplusNode.this.indexInParent>=0) 
					{
						TraverseToFollowingKey t = BplusNode.this.parent.traverseToFollowingKey(BplusNode.this.indexInParent+1);//, out FoundInLeaf, out KeyFound);
						this.FoundInLeaf = t.FoundInLeaf;
						this.KeyFound = t.KeyFound;
						return;
					} 
					else 
					{
						return; // no such following key
					}
				}
				if (BplusNode.this.isLeaf) 
				{
					// leaf, we found it.
					FoundInLeaf = BplusNode.this;
					KeyFound = BplusNode.this.ChildKeys[atIndex];
					return;
				} 
				else