del_node.htm

一个用Basic实现的B-Tree算法

<title>Commented source code for BTPDEL</title>
<h2>Commented source code for <tt>BTPDEL</tt></h2>
<pre>
    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
</pre>
<hr>
<A HREF="btp.html">B-TREE-P</A> copyright &copy 1987-1999 by <A HREF="/home/contact.html">Semaphore Corporation</A>