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