bplustreelong.cs

R树与B树的混合树

			//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) 
		{
			if (this.isLeaf) 
			{
				return this.InsertLeaf(key, position, out splitString, out splitNode);
			}
			splitString = null;
			splitNode = null;
			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);
			// 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;
				bool 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;
					splitString = this.ChildKeys[splitpoint];
					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);
					Array.Copy(keys, 0, this.ChildKeys, 0, splitpoint);
					// 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);
					Array.Copy(keys, splitpoint+1, splitNode.ChildKeys, 0, remainingKeys);
					// 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() 
		{
			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 value in keys, or null if no change</returns>
		public string InsertLeaf(string key, long position, out string splitString, out BplusNode splitNode) 
		{
			splitString = null;
			splitNode = null;
			bool dosplit = false;
			if (!this.isLeaf) 
			{
				throw new BplusTreeException("bad call to InsertLeaf: this is not a leaf");
			}
			this.Soil();
			int insertposition = this.FindAtOrNextPosition(key, false);
			if (insertposition>=this.Size) 
			{
				//throw new BplusTreeException("key too big and leaf is full");
				dosplit = true;
				this.PrepareForSplit();
			} 
			else 
			{
				// if it's already there then change the value at the current location (duplicate entries not supported).
				if (this.ChildKeys[insertposition]==null || this.owner.Compare(this.ChildKeys[insertposition], key)==0) // this.ChildKeys[insertposition].Equals(key)
				{
					this.ChildBufferNumbers[insertposition] = position;
					this.ChildKeys[insertposition] = key;
					if (insertposition==0) 
					{
						return key;
					} 
					else 
					{
						return null;
					}
				}
			}
			// check for a null position
			int nullindex = insertposition;
			while (nullindex<this.ChildKeys.Length && this.ChildKeys[nullindex]!=null) 
			{
				nullindex++;
			}
			if (nullindex>=this.ChildKeys.Length) 
			{
				if (dosplit) 
				{
					throw new BplusTreeException("can't split twice!!");
				}
				//throw new BplusTreeException("no space in leaf");
				dosplit = true;
				this.PrepareForSplit();
			}
			// bubble in the new info XXXX THIS SHOULD BUBBLE BACKWARDS	
			string nextkey = this.ChildKeys[insertposition];
			long nextposition = this.ChildBufferNumbers[insertposition];
			this.ChildKeys[insertposition] = key;
			this.ChildBufferNumbers[insertposition] = position;
			while (nextkey!=null) 
			{
				key = nextkey;
				position = nextposition;
				insertposition++;
				nextkey = this.ChildKeys[insertposition];
				nextposition = this.ChildBufferNumbers[insertposition];
				this.ChildKeys[insertposition] = key;
				this.ChildBufferNumbers[insertposition] = position;
			}
			// split if needed
			if (dosplit) 
			{
				int splitpoint = this.ChildKeys.Length/2;
				int splitlength = this.ChildKeys.Length - splitpoint;
				splitNode = new BplusNode(this.owner, this.parent, -1, this.isLeaf);
				// copy the split info into the splitNode
				Array.Copy(this.ChildBufferNumbers, splitpoint, splitNode.ChildBufferNumbers, 0, splitlength);
				Array.Copy(this.ChildKeys, splitpoint, splitNode.ChildKeys, 0, splitlength);
				Array.Copy(this.MaterializedChildNodes, splitpoint, splitNode.MaterializedChildNodes, 0, splitlength);
				splitString = splitNode.ChildKeys[0];
				// archive the new node
				splitNode.DumpToFreshBuffer();
				// store the node data temporarily
				long[] buffernumbers = this.ChildBufferNumbers;
				string[] keys = this.ChildKeys;
				BplusNode[] nodes = this.MaterializedChildNodes;
				// repair current node, copy in the other part of the split
				this.ChildBufferNumbers = new long[this.Size+1];
				this.ChildKeys = new string[this.Size];
				this.MaterializedChildNodes = new BplusNode[this.Size+1];
				Array.Copy(buffernumbers, 0, this.ChildBufferNumbers, 0, splitpoint);
				Array.Copy(keys, 0, this.ChildKeys, 0, splitpoint);
				Array.Copy(nodes, 0, this.MaterializedChildNodes, 0, splitpoint);
				for (int i=splitpoint; i<this.ChildKeys.Length; i++) 
				{
					this.ChildKeys[i] = null;
					this.ChildBufferNumbers[i] = BplusTreeLong.NULLBUFFERNUMBER;
					this.MaterializedChildNodes[i] = null;
				}
				// store the new node
				//splitNode.DumpToFreshBuffer();
				this.owner.RecordTerminalNode(splitNode);
				splitNode.Soil();
			}
			//return this.ChildKeys[0];
			if (insertposition==0) 
			{
				return key; // smallest key changed.
			} 
			else 
			{
				return null; // no change in smallest key
			}
		}
		/// <summary>
		/// Grow to this.size+1 in preparation for insertion and split
		/// </summary>
		void PrepareForSplit() 
		{
			int supersize = this.Size+1;
			long[] positions = new long[supersize+1];
			string[] keys = new string[supersize];
			BplusNode[] materialized = new BplusNode[supersize+1];
			Array.Copy(this.ChildBufferNumbers, 0, positions, 0, this.Size+1);
			positions[this.Size+1] = BplusTreeLong.NULLBUFFERNUMBER;
			Array.Copy(this.ChildKeys, 0, keys, 0, this.Size);
			keys[this.Size] = null;
			Array.Copy(this.MaterializedChildNodes, 0, materialized, 0, this.Size+1);
			materialized[this.Size+1] = null;
			this.ChildBufferNumbers = positions;
			this.ChildKeys = keys;
			this.MaterializedChildNodes = materialized;
		}
		public void Load(byte[] buffer) 
		{
			// load serialized data
			// indicator | seek position | [ key storage | seek position ]*
			this.Clear();
			if (buffer.Length!=owner.buffersize) 
			{
				throw new BplusTreeException("bad buffer size "+buffer.Length+" should be "+owner.buffersize);
			}
			byte indicator = buffer[0];
			this.isLeaf = false;
			if (indicator==BplusTreeLong.LEAF) 
			{
				this.isLeaf = true;
			} 
			else if (indicator!=BplusTreeLong.NONLEAF) 
			{
				throw new BplusTreeException("bad indicator, not leaf or nonleaf in tree "+indicator);
			}
			int index = 1;
			// get the first seek position
			this.ChildBufferNumbers[0] = BufferFile.RetrieveLong(buffer, index);
			System.Text.Decoder decode = System.Text.Encoding.UTF8.GetDecoder();
			index+= BufferFile.LONGSTORAGE;
			int maxKeyLength = this.owner.KeyLength;
			int maxKeyPayload = maxKeyLength - BufferFile.SHORTSTORAGE;
			//this.NumberOfValidKids = 0;
			// get remaining key storages and seek positions
			string lastkey = "";
			for (int KeyIndex=0; KeyIndex<this.Size; KeyIndex++) 
			{
				// decode and store a key
				short keylength = BufferFile.RetrieveShort(buffer, index);
				if (keylength<-1 || keylength>maxKeyPayload) 
				{
					throw new BplusTreeException("invalid keylength decoded");
				}
				index+= BufferFile.SHORTSTORAGE;
				string key = null;
				if (keylength==0) 
				{
					key = "";
				} 
				else if (keylength>0) 
				{
					int charCount = decode.GetCharCount(buffer, index, keylength);
					char[] ca = new char[charCount];
					decode.GetChars(buffer, index, keylength, ca, 0);
					//this.NumberOfValidKids++;
					key = new String(ca);
				}
				this.ChildKeys[KeyIndex] = key;
				index+= maxKeyPayload;
				// decode and store a seek position
				long seekPosition = BufferFile.RetrieveLong(buffer, index);
				if (!this.isLeaf) 
				{
					if (key==null & seekPosition!=BplusTreeLong.NULLBUFFERNUMBER) 
					{
						throw new BplusTreeException("key is null but position is not "+KeyIndex);
					} 
					else if (lastkey==null && key!=null) 
					{
						throw new BplusTreeException("null key followed by non-null key "+KeyIndex);
					}
				}
				lastkey = key;
				this.ChildBufferNumbers[KeyIndex+1] = seekPosition;
				index+= BufferFile.LONGSTORAGE;
			}
		}
		/// <summary>
		/// check that key is ok for node of this size (put here for locality of relevant code).
		/// </summary>
		/// <param name="key">key to check</param>
		/// <param name="owner">tree to contain node containing the key</param>
		/// <returns>true if key is ok</returns>
		public static bool KeyOK(string key, BplusTreeLong owner) 
		{
			if (key==null) 
			{ 
				return false;
			}
			System.Text.Encoder encode = System.Text.Encoding.UTF8.GetEncoder();
			int maxKeyLength = owner.KeyLength;
			int maxKeyPayload = maxKeyLength - BufferFile.SHORTSTORAGE;
			char[] keyChars = key.ToCharArray();
			int charCount = encode.GetByteCount(keyChars, 0, keyChars.Length, true);
			if (charCount>maxKeyPayload) 
			{
				return false;
			}
			return true;
		}
		public void Dump(byte[] buffer) 
		{
			// indicator | seek position | [ key storage | seek position ]*
			if (buffer.Length!=owner.buffersize) 
			{
				throw new BplusTreeException("bad buffer size "+buffer.Length+" should be "+owner.buffersize);
			}
			buffer[0] = BplusTreeLong.NONLEAF;
			if (this.isLeaf) { buffer[0] = BplusTreeLong.LEAF; }
			int index = 1;
			// store first seek position
			BufferFile.Store(this.ChildBufferNumbers[0], buffer, index);
			index+= BufferFile.LONGSTORAGE;
			System.Text.Encoder encode = System.Text.Encoding.UTF8.GetEncoder();
			// store remaining keys and seeks
			int maxKeyLength = this.owner.KeyLength;
			int maxKeyPayload = maxKeyLength - BufferFile.SHORTSTORAGE;
			string lastkey = "";
			for (int KeyIndex=0; KeyIndex<this.Size; KeyIndex++) 
			{
				// store a key
				string theKey = this.ChildKeys[KeyIndex];
				short charCount = -1;
				if (theKey!=null) 
				{
					char[] keyChars = theKey.ToCharArray();
					charCount = (short) encode.GetByteCount(keyChars, 0, keyChars.Length, true);
					if (charCount>maxKeyPayload) 
					{
						throw new BplusTreeException("string bytes to large for use as key "+charCount+">"+maxKeyPayload);
					}
					BufferFile.Store(charCount, buffer, index);
					index+= BufferFile.SHORTSTORAGE;
					encode.GetBytes(keyChars, 0, keyChars.Length, buffer, index, true);
				}