Should BTPFIND report end-of-tree?
Branches #5 showed how to modify the original BTPFIND routine so it did not return an insertion point at the end of a node, but instead called BTPSEQ to get the first position of the next node.
In that case, calling BTPFIND for a key greater than all keys in the tree makes BTPFIND return a null id. For example, if the highest ZIP code in a B-tree is 99998, then calling BTPFIND to find 99999 would return a null id (indicating the search "went off the end of the tree"). For some applications, that might be useful information, but for other programs such as browsers, that might create an invalid situation that leaves the operator with nothing to look at. (After all, after searching for 99999, shouldn't the browser just stop at the last possible key and display that one instead?)
If you want BTPFIND to return a null id after searches beyond the end of the tree, the code from Branches #5 will suffice. But if you want BTPFIND to instead return the last item id, use:
SUBROUTINE BTPFIND(ROOT,BFILE,DFILE,ID,ITEM,NODE.ID,NODE.POS) CALL BTPKEY(ROOT, ID, ITEM, FK) READ NODE.ID FROM BFILE, ROOT ELSE STOP "BTP8" 100 READ N FROM BFILE, NODE.ID ELSE STOP "BTP9" L = 0 ; R = N<1>+1 IF R = 1 THEN NODE.POS = 1 ELSE LOOP NODE.POS = INT((L+R)/2) UID = N<2, NODE.POS> IF UID = ID THEN RETURN READ IT FROM DFILE, UID ELSE STOP "BTP10" CALL BTPKEY(ROOT, UID, IT, KEY) IG = (FK > KEY) IF IG THEN L = NODE.POS ELSE R = NODE.POS UNTIL (R-L) <= 1 DO REPEAT IF IG THEN NODE.POS = R END NNID = N<3, NODE.POS> IF NNID # "" THEN NODE.ID = NNID GO TO 100 END IF NODE.POS > N<1> THEN ;* want next node NODE.POS = N<1> ;* go to end of current node LAST.NODE.ID = NODE.ID ;* in case BTPSEQ fails CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",ID) IF ID = "" THEN ;* beyond end of tree NODE.POS = N<1> ;* go to end of last node ID = N<2,NODE.POS> ;* extract the key NODE.ID = LAST.NODE.ID ;* recover the node id END RETURN END ID = N<2, NODE.POS> RETURN END