find_node.htm

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

<title>Commented source code for BTPFIND</title>
<h2>Commented source code for <tt>BTPFIND</tt></h2>
<pre>
    C.BTPFIND
001 SUBROUTINE BTPFIND(ROOT,BFILE,DFILE,ID,ITEM,NODE.ID,NODE.POS)
002 * Find node containing key, 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 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 100 READ NODE FROM BFILE, NODE.ID ELSE STOP "Can't find node"
011 LEFT = 0 ; RIGHT = NODE<1>+1 ;* Boundaries for binary search of keys in node
012 IF RIGHT = 1 THEN NODE.POS = 1 ELSE ;* Not an empty root
013   LOOP
014     NODE.POS = INT((LEFT+RIGHT)/2) ;* Find position midway between boundaries
015     COMPARE.ID = NODE<2,NODE.POS> ;* Get that key
016     IF COMPARE.ID = ID THEN RETURN ;* Key is already in node
017     READ COMPARE.ITEM FROM DFILE, COMPARE.ID ELSE STOP "Can't read"
018     CALL BTPKEY(ROOT,COMPARE.ID,COMPARE.ITEM,KEY) ;* Convert COMPARE.ITEM to KEY for comparison
019     IS.GREATER = (FINDKEY > KEY) ;* Is our key greater than node key?
020     IF IS.GREATER THEN LEFT = NODE.POS ELSE RIGHT = NODE.POS ;* Adjust search boundaries
021   UNTIL (RIGHT-LEFT) <= 1 DO REPEAT
022   IF IS.GREATER THEN NODE.POS = RIGHT ;* Else NODE.POS already OK
023   END
024 NEXT.NODE.ID = NODE<3, NODE.POS> ;* Get id of next node
025 IF NEXT.NODE.ID # "" THEN ;* There's another node, keep looking for leaf
026   NODE.ID = NEXT.NODE.ID
027   GO TO 100
028   END
029 IF NODE.POS <= NODE<1> THEN ID = NODE<2,NODE.POS> ; RETURN
030 * At end of node, get next id like Branches #5 describes
031 NODE.POS = NODE<1> ; LAST.NODE.ID = NODE.ID
032 CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",ID)
033 IF ID = "" THEN ;* Past end of tree, use last id
034   NODE.POS = NODE<1>
035   ID = NODE<2,NODE.POS>
036   NODE.ID = LAST.NODE.ID
037   END
038 RETURN
039 END
</pre>
<hr>
<A HREF="btp.html">B-TREE-P</A> copyright &copy 1987-1999 by <A HREF="/home/contact.html">Semaphore Corporation</A>