C.BTPDEL 001 SUBROUTINE BTPDEL(ROOT,SIZE,BFILE,DFILE,ID,ITEM) 002 * Delete key from B-tree with nodes in following format: 003 * AMC 0: Arbitrary node number. 004 * AMC 1: Count of keys in node. 005 * AMC 2: Keys, stored as a subvalue list. 006 * AMC 3: (number of keys)+1 pointers to next nodes. 007 * AMC 4: Pointer to parent node if any. 008 CALL BTPKEY(ROOT,ID,ITEM,FINDKEY) ;* Get sort string for comparing to rest of tree 009 READ NODE.ID FROM BFILE, ROOT ELSE STOP "No root" 010 FOUND = 0 ;* Flopped true once key found in tree 011 100 READ NODE FROM BFILE, NODE.ID ELSE STOP "Can't find node" 012 LEFT = 0 ; RIGHT = NODE<1>+1 ;* Boundaries for binary search of keys in node 013 IF (RIGHT=1) OR FOUND THEN NEXT.PTR=1 ; POS=1 ELSE ;* Not an empty root and not searching for adjacent key 014 LOOP 015 POS = INT((LEFT+RIGHT)/2) ;* Find position midway between boundaries 016 COMPARE.ID = NODE<2,POS> ;* Get that key 017 IF COMPARE.ID = ID THEN ;* Key is in node 018 FOUND=1 ; OWNER.ID=NODE.ID ; OWNER.POS=POS ;* Remember so and where 019 RIGHT=LEFT ; NEXT.PTR=POS+1 ;* Force loop stop, go right to find adjacent key 020 END ELSE ;* These keys don't match 021 NEXT.PTR = POS ;* If loop stops, go left next time 022 READ COMPARE.ITEM FROM DFILE, COMPARE.ID ELSE STOP "Can't read" 023 CALL BTPKEY(ROOT,COMPARE.ID,COMPARE.ITEM,KEY) ;* Convert COMPARE.ITEM to KEY for comparison 024 IS.GREATER = (FINDKEY > KEY) ;* Is our key greater than node key? 025 IF IS.GREATER THEN LEFT = POS ELSE RIGHT = POS ;* Adjust search boundaries 026 END 027 UNTIL (RIGHT-LEFT) <= 1 DO REPEAT 028 IF NOT(FOUND) THEN ;* May have to adjust POS 029 IF IS.GREATER THEN POS = RIGHT ; NEXT.PTR=POS ;* Else POS already OK 030 END 031 END 032 NEXT.NODE.ID = NODE<3, NEXT.PTR> ;* Get id of next node 033 IF NEXT.NODE.ID # "" THEN ;* There's another node, keep looking for leaf 034 NODE.ID = NEXT.NODE.ID 035 GO TO 100 036 END 037 IF NOT(FOUND) THEN CRT ID:" not present to delete" ; RETURN 038 * Reached a leaf, is it also the one with the key? 039 IF NODE<2, POS> # ID THEN ;* No, this leaf has the adjacent key 040 READ OWNER.NODE FROM BFILE, OWNER.ID ELSE STOP "Can't reread" 041 OWNER.NODE<2, OWNER.POS> = NODE<2,1> ;* Replace key found with adjacent key 042 WRITE OWNER.NODE ON BFILE, OWNER.ID 043 POS = 1 ;* So following delete will erase adjacent key from leaf 044 END 045 NODE = DELETE(NODE, 2, POS) ;* Erase the leaf key 046 NODE<1> = NODE<1> - 1 ;* Reduce count of keys in node 047 200 IF (NODE<1> < SIZE) AND (NODE<4> # "") THEN ;* Underflow, since too few keys in a non-root node 048 PARENT.ID = NODE<4> ;* Get id of parent of underflowed node 049 READ PARENT FROM BFILE, PARENT.ID ELSE STOP "Can't reread" 050 LOCATE(NODE.ID, PARENT, 3; POS) ELSE STOP "Forgot" 051 NEIGHBOR.ID = PARENT<3, POS+1> ; PARENT.POS = POS ;* Assume neighbor's on right 052 NEIGHBOR.ON.LEFT = (NEIGHBOR.ID="") ;* Are we wrong? 053 IF NEIGHBOR.ON.LEFT THEN NEIGHBOR.ID = PARENT<3, POS-1> ; PARENT.POS=POS-1 ;* Yes, try other side 054 READ NEIGHBOR FROM BFILE, NEIGHBOR.ID ELSE STOP "Can't find" 055 TOTAL.KEYS = NODE<1> + NEIGHBOR<1> ;* How many keys left in both nodes 056 IF TOTAL.KEYS >= 2*SIZE THEN ;* Borrow some from neighbor by moving one at a time thru parent pos 057 MOVE.COUNT = INT((NEIGHBOR<1>-NODE<1>)/2) ;* Qty to take 058 FOR I = 1 TO MOVE.COUNT 059 IF NEIGHBOR.ON.LEFT THEN ;* Taking from left node 060 NEIGHBOR.POS = NEIGHBOR<1> ;* Where we take key from 061 NODE.POS = 1 ;* Where we insert key after taking 062 NEIGHBOR.PTR.POS = NEIGHBOR.POS+1 ;* Where we take the ptr, if any 063 NODE.PTR.POS = NODE.POS ;* Where we insert the ptr after taking 064 END ELSE ;* Taking from right node 065 NODE.POS = NODE<1> + 1 ;* Where we insert key 066 NEIGHBOR.POS = 1 ;* Where we take key 067 NODE.PTR.POS = NODE.POS + 1 ;* Where we insert ptr 068 NEIGHBOR.PTR.POS = NEIGHBOR.POS ;* Where we take ptr 069 END 070 NODE = INSERT(NODE,2,NODE.POS;PARENT<2,PARENT.POS>) ;* Move from parent to node 071 NODE<1> = NODE<1>+1 ;* Increase count of keys in node 072 PARENT<2,PARENT.POS> = NEIGHBOR<2,NEIGHBOR.POS> ;* Move from neighbor to parent 073 NEIGHBOR = DELETE(NEIGHBOR,2,NEIGHBOR.POS) ;* Delete from neighbor 074 NEIGHBOR<1> = NEIGHBOR<1>-1 ;* Decrease neighbor key count 075 CHILD.ID = NEIGHBOR<3,NEIGHBOR.PTR.POS> 076 IF CHILD.ID # "" THEN ;* Not a leaf 077 NODE = INSERT(NODE,3,NODE.PTR.POS;CHILD.ID) ;* Move ptr too 078 NEIGHBOR = DELETE(NEIGHBOR,3,NEIGHBOR.PTR.POS) 079 READ CHILD FROM BFILE, CHILD.ID ELSE STOP "Can't find child" 080 CHILD<4> = NODE.ID ;* Tell child about new parent 081 WRITE CHILD ON BFILE, CHILD.ID 082 END 083 NEXT I 084 WRITE NEIGHBOR ON BFILE, NEIGHBOR.ID 085 WRITE PARENT ON BFILE, PARENT.ID 086 WRITE NODE ON BFILE, NODE.ID 087 END ELSE ;* Concatenate into neighbor 088 IF NEIGHBOR.ON.LEFT THEN ;* Will be concatenating onto neighbor end 089 INS.POS = NEIGHBOR<1>+1 ;* Where we insert into neighbor 090 INS.PTR.POS = INS.POS+1 ;* Where ptrs are inserted into neighbor 091 GET.POS = 1 ;* Where ptr for alongside moved parent comes from 092 END ELSE ;* Will be inserting into front of neighbor 093 INS.POS = 1 ;* Where keys are inserted into neighbor 094 INS.PTR.POS = 1 ;* Where ptrs are inserted into neighbor 095 GET.POS = NODE<1>+1 ;* Where first pointer comes from 096 END 097 NEIGHBOR = INSERT(NEIGHBOR,2,INS.POS;PARENT<2,PARENT.POS>) ;* Move parent into neighbor 098 NOT.LEAF = (NEIGHBOR<3,1> # "") ;* At a leaf? 099 IF NOT.LEAF THEN ;* No, move ptr too 100 CHILD.ID = NODE<3,GET.POS> 101 NEIGHBOR = INSERT(NEIGHBOR,3,INS.PTR.POS;CHILD.ID) 102 READ CHILD FROM BFILE, CHILD.ID ELSE STOP "Can't find child" 103 CHILD<4> = NEIGHBOR.ID ;* Tell child about new parent 104 WRITE CHILD ON BFILE, CHILD.ID 105 END 106 IF NEIGHBOR.ON.LEFT THEN ;* Adjust so rest of inserts come after concated parent 107 INS.POS = INS.POS+1 ; INS.PTR.POS = INS.PTR.POS+1 108 END 109 FOR I = NODE<1> TO 1 STEP -1 110 NEIGHBOR = INSERT(NEIGHBOR,2,INS.POS;NODE<2,I>) ;* Concat key from node 111 IF NOT.LEAF THEN ;* Concat ptr too 112 IF NEIGHBOR.ON.LEFT THEN ;* Bring right hand ptr 113 NODE.PTR.POS = I+1 114 END ELSE NODE.PTR.POS = I ;* Bring left hand ptr 115 CHILD.ID = NODE<3,NODE.PTR.POS> 116 NEIGHBOR = INSERT(NEIGHBOR,3,INS.PTR.POS;CHILD.ID) ;* Concat ptr 117 READ CHILD FROM BFILE, CHILD.ID ELSE STOP "Can't find child" 118 CHILD<4> = NEIGHBOR.ID ;* Tell child about new parent 119 WRITE CHILD ON BFILE, CHILD.ID 120 END 121 NEXT I 122 NEIGHBOR<1> = NEIGHBOR<1> + NODE<1> + 1 123 WRITE NEIGHBOR ON BFILE, NEIGHBOR.ID ;* May get written again below to clear parent 124 DELETE BFILE, NODE.ID 125 PARENT = DELETE(PARENT, 2, PARENT.POS) 126 PARENT = DELETE(PARENT, 3, POS) 127 PARENT<1> = PARENT<1>-1 128 IF PARENT<1> <= 0 THEN ;* Descendants of root just got concated 129 DELETE BFILE, PARENT.ID ;* Delete old empty root 130 WRITE NEIGHBOR.ID ON BFILE, ROOT ;* Point to new root 131 NEIGHBOR<4> = "" ;* Since now root, clear parent ptr 132 WRITE NEIGHBOR ON BFILE, NEIGHBOR.ID 133 END ELSE ;* Parent still has keys 134 WRITE PARENT ON BFILE, PARENT.ID 135 NODE = PARENT 136 NODE.ID = PARENT.ID 137 GO TO 200 ;* Check if parent underflowed 138 END 139 END 140 END ELSE WRITE NODE ON BFILE, NODE.ID ;* No underflow 141 RETURN 142 END