BTreeDelete.mesa
Operation for deleting BTree entries.
Last Edited by: Taft, June 3, 1983 2:54 pm
DIRECTORY
BTree,
BTreeInternal;
BTreeDelete: PROGRAM
IMPORTS BTree, BTreeInternal
EXPORTS BTree
= BEGIN OPEN BTree, BTreeInternal;
BTree.
Tree: TYPE = REF TreeObject;
TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject;
PathStk: TYPE = REF PathStkObject;
PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject;
DeleteKey: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEANFALSE] RETURNS [found: BOOLEAN] = TRUSTED
BEGIN
FatherMayNeedWork: PROCEDURE RETURNS [needsWork: BOOLEAN] =
BEGIN
This code assumes that the son page is pointed to by the fatherPage[lastOffset].grPage and that this condition is preserved by InsertRecords.
pagePtr, otherPtr: BTreePagePtr;
fatherPSE: LONG POINTER TO PathStkEntry;
fatherFreeWords: CARDINAL;
pse ← @pathStk.path[pathStk.top];
needsWork ← ChangeInFather[];
pagePtr ← tree.ReferencePage[pse.pageNumber];
IF pathStk.top=1 AND pagePtr.freeWords=tree.maxFreeWords THEN
BEGIN -- Bye-bye, old root page!
tree.state.rootPage ← pagePtr.minPage;
tree.state.depth ← tree.state.depth-1;
tree.ReleasePage[pse.pageNumber];
tree.FreePage[pse.pageNumber];
RETURN [FALSE];
END;
IF pathStk.top=1 OR tree.maxFreeWords-pagePtr.freeWords >= tree.prettyFull THEN
{ tree.ReleasePage[pse.pageNumber]; RETURN };
Page is not sufficiently full. Try to merge with left or right brother page. This is done by extracting the entire contents of this page (plus one father entry) into the ESL, freeing this page, repositioning to the brother page, and calling InsertRecords. Of course, there may not actually be enough space in the brother page(s), in which case InsertRecords will turn around and allocate a new page. But in any event the overall balance of the tree should be improved.
AppendEntSeqRecord[pse: pse, esr: MakeEntSeqRecord[entSeq: @pagePtr.entries, length: tree.maxFreeWords-pagePtr.freeWords]];
fatherPSE ← @pathStk.path[pathStk.top-1];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber];
fatherFreeWords ← otherPtr.freeWords;
tree.ReleasePage[fatherPSE.pageNumber];
IF fatherPSE.offset < nilOffset+(tree.state.pageSize-fatherFreeWords) OR fatherPSE.eslFront#NIL THEN
BEGIN -- the current page has a right brother
rtBroPg: PageNumber;
esr: REF EntSeqRecord;
[esr: esr, grPage: rtBroPg] ← tree.RemoveEntry[fatherPSE];
AppendEntSeqRecord[pse: pse, esr: esr];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber, write];
IF otherPtr[fatherPSE.lastOffset].grPage # pse.pageNumber THEN
ERROR Bug[mcCreightWasWrong];
otherPtr[fatherPSE.lastOffset].grPage ← rtBroPg;
tree.ReleasePage[fatherPSE.pageNumber];
otherPtr ← tree.ReferencePage[rtBroPg, write];
otherPtr.minPage ← pagePtr.minPage;
tree.ReleasePage[rtBroPg];
tree.ReleasePage[pse.pageNumber];
tree.FreePage[pse.pageNumber];
pse.pageNumber ← rtBroPg;
pse.offset ← entry1Offset;
pse.lastOffset ← entry0Offset;
pse.nextToLastOffset ← nilOffset;
END
ELSE BEGIN -- the current page surely has a left brother
esr: REF EntSeqRecord;
tree.ReleasePage[pse.pageNumber];
[esr: esr] ← tree.BackUpAndRemoveEntry[fatherPSE];
PushEntSeqRecord[pse: pse, esr: esr];
tree.FreePage[pse.pageNumber];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber];
pse.pageNumber ← otherPtr[fatherPSE.lastOffset].grPage;
tree.ReleasePage[fatherPSE.pageNumber];
pagePtr ← tree.ReferencePage[pse.pageNumber];
pse.offset ← nilOffset+(tree.state.pageSize-pagePtr.freeWords);
pse.lastOffset ← entry1Offset;
pse.nextToLastOffset ← entry0Offset;
tree.ReleasePage[pse.pageNumber];
tree.RepairOffsets[pse];
END;
[] ← ChangeInFather[];
RETURN [TRUE];
END; -- FatherMayNeedWork
ChangeInFather: PROCEDURE RETURNS [needsWork: BOOLEAN] =
BEGIN
IF pse.eslFront=NIL THEN RETURN [FALSE];
tree.InsertRecords[pathStk];
RETURN [pathStk.top#0 AND pathStk.path[pathStk.top-1].eslFront#NIL];
END; -- ChangeInFather
pathStkWasNil: BOOLEAN ← pathStk=NIL;
pse: LONG POINTER TO PathStkEntry;
tree.Lock[update];
IF pathStkWasNil THEN
BEGIN
IF useExistingPath THEN ERROR Error[nilPathStk];
pathStk ← tree.GetDefaultPathStk[];
END;
Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
BEGIN ENABLE UNWIND =>
{ IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] };
origStkTop: PathStkIndex;
pagePtr: BTreePagePtr ← NIL;
descendantPg: PageNumber;
simpleDelete: BOOLEAN; -- entry is "simple" to delete if it is in a leaf page and removing it will still leave the page at least "prettyFull".
[] ← tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath];
origStkTop ← pathStk.top;
IF origStkTop=0 THEN RETURN [FALSE];
[ptr: pagePtr, pse: pse] ← tree.ReferenceStack[pathStk];
IF tree.Compare[key, @pagePtr[pse.lastOffset].entry] # equal THEN
{ tree.ReleasePage[pse.pageNumber]; tree.Unlock[]; RETURN [FALSE] };
descendantPg ← pagePtr[pse.nextToLastOffset].grPage;
simpleDelete ← descendantPg=nilPage AND tree.maxFreeWords - (pagePtr.freeWords + tree.BTreeEntrySize[@pagePtr[pse.lastOffset]]) >= tree.prettyFull;
tree.ReleasePage[pse.pageNumber];
tree.version ← tree.version+1; -- invalidate existing PathStks that refer to this tree
Set up to delete the entry. If it is in a leaf page, we just remove it. If it is in an interior page, we must find a leaf entry to replace it with.
tree.BackUpOneEntry[pse]; -- pse.offset should index deletion victim
IF simpleDelete THEN
BEGIN
tree.AdjustTreeState[update: unchanged, deltaEntryCount: -1];
pagePtr ← tree.ReferencePage[pse.pageNumber, write];
[] ← tree.RemoveEntry[pse];
tree.ReleasePage[pse.pageNumber, endOfUpdate];
END
ELSE BEGIN
tree.AdjustTreeState[update: startOfUpdate, deltaEntryCount: -1];
Deletion surrogate is one with greatest key less than victim's
tree.PathToMaxDescendant[pathStk: pathStk, page: descendantPg];
IF pathStk.top > origStkTop THEN
BEGIN
dpse: LONG POINTER TO PathStkEntry = @pathStk.path[pathStk.top];
leafESR: REF EntSeqRecord;
[esr: leafESR] ← tree.BackUpAndRemoveEntry[dpse];
[grPage: leafESR.entSeqP.grPage] ← tree.RemoveEntry[pse]; -- discard returned ESR
AppendEntSeqRecord[pse: pse, esr: leafESR];
END
ELSE [] ← tree.RemoveEntry[pse];
tree.GetHeapAndTable[pathStk];
DO
needsWork: BOOLEAN ← FatherMayNeedWork[ !
UNWIND => tree.ReturnHeapAndTable[pathStk]];
IF pathStk.top=0 OR (~needsWork AND pathStk.top<=origStkTop) THEN EXIT
ELSE pathStk.top ← pathStk.top-1;
ENDLOOP;
pathStk.top ← 0;
tree.ReturnHeapAndTable[pathStk];
tree.AdjustTreeState[update: endOfUpdate, deltaEntryCount: 0];
END;
END;
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
RETURN [TRUE];
END;
END.