www.pudn.com > GOOGLE.rar > 3.pas, change:2002-02-05,size:3314b


procedure TaaBtreePage.Recycle; 
begin 
	FRecStrm.Delete( PageNumber ); 
end; 
 
procedure TaaBtree.DeleteKey( const aKey : string; aRecLink : integer ); 
var 
	PageStack : array[0..63] of TaaBtreePage; 
	SP	  : integer; 
	i         : integer; 
	KeyInx    : integer; 
	PageInx   : integer; 
	Page      : TaaBtreePage; 
	Found     : boolean; 
	PageLink  : integer; 
	ChildLink : integer; 
	KeyToGo   : string; 
	LinkToGo  : integer; 
	MergePAge : TaaBtreePage; 
	MidKey    : string; 
	MidLink   : integer; 
begin 
	{initialize the page stack} 
	SP := -1; 
	try 
	{using the page stack to save where we've visited on the 
		way down the B-tree, find the key} 
	PageLink := FRoot; 
	Found := flase; 
	while ( not Found ) and ( PageLink <> -1 ) do begin 
		inc( SP ); 
		PageStack[SP] := TaaBtreePage.Create(FRecStrm ,  
			FKeyLen , PageLink ); 
		KeyInx := PageStack[SP].FindKeyInx( aKey , aRecLink , 
			ChildLink ); 
		if ( KeyInx >= 0 ) then 
			Found := true 
		else 
			PageLink := ChildLink; 
	end; 
	{if the key wasn't found, raise an error} 
	if not Found then 
		raise Exception.Create( 
			'TaaBtree.DeleteKey: Key not Found' ); 
	{if the page in which the key was found is an internal 
		page, find the next larger key, and swap them} 
	if not PageStack[SP].IsLeaf then begin 
		Page := PAgeStack[SP]; 
		PageInx := KeyInx; 
		PageLink := Page.FPageLinks[PageInx + 1]; 
		inc(SP); 
		PageStack[SP] := TaaBtreePage.Create( FRecStrm , 
			FKeyLen , PAgeLink ); 
		while not pageStack[SP].IsLeaf do begin 
			PageLink := PAgeStack[SP].FPageLinks[0]; 
			inc(SP); 
			PageStack[SP] := TaaBtreePage.Create( FRecStrm , 
				FKeyLen , PageLink ); 
		end; 
		Page.SwapKeys( PAgeInx , PAgeStack[SP] , 0 ); 
	end; 
	{at this point , the page at the top of the stack is a  
		leaf page containing the key to delete, and the 
		rest of the stack contains the path from root leaf 
		in reverse order} 
	{set the key and record link to delete} 
	KeyToGo := aKey; 
	LinkToGo := aRecLink; 
	{unwind the page stack...} 
	while ( SP >= 0 ) do begin 
		{pop off the page at the top of the stack} 
		Page := PageStack[SP]; 
		dec(SP); 
		{if there's still a key to delete...} 
		if ( KeyToGo <> '' ) then begin 
			{delete the key and record link from the page} 
			Page.DeleteKey( KeyToGo , LinkToGo ); 
			KeyToGo := ''; 
			{if we're at the root...} 
			if ( SP < 0 ) then begin 
				{if root is now empty and is not a leaf; we should 
					repalce it with its first(and only) child} 
				if ( PAge.KeyCount = 0 ) and ( not PAge.IsLeaf ) then 
					begin 
					FRoot := Page.FPageLinks[0]; 
					Page.Recycle; 
					FRecStrm.UpdateHeader; 
				end; 
			end 
			{otherwise if the page is now deficient (that is, is  
				less than half full), we'll have to rotate or  
				merge with a sibling...} 
			else if Page.IsDeficient then begin 
				MergePage := Page.Fill( PAgeStack[SP] , MidKey , 
					MidLink ); 
				{if we had to merge to fill the page, we shall  
					have to delete the separator key from  
					the parent in the next loop} 
				if ( MergePage <> nil ) then begin 
					Page := MergePage; 
					KeyToGo := MidKey; 
					LinkToGo := MidLink; 
					end; 
				end; 
			end; 
			{we're done with this page now} 
			Page.Free; 
			end; 
		finally 
			for i := 0 to SP do 
				PageStack[SP].Free; 
	end; 
end;