a.txt

搜索算法源代码

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;