What BTPFIND really finds

If the BTPFIND subroutine is given a complete item identifier and data record, it will find the actual position of that item in a B-tree. But BTPFIND is often used (for example, by BROWSE.NAMES) to search for a partial record, such as just one attribute like a ZIP code, with no known item identifier.

In that case, BTPFIND will never be able to completely match any particular record in the B-tree. For example, imagine browsing the following file sorted by ZIP:

ID 103 ZIP 95003

ID 704 ZIP 95005

ID 552 ZIP 95007

ID 302 ZIP 95009

If we call BTPFIND with a null item identifier and a ZIP of 95006, BTPFIND will be unable to find any such record, so it returns the item identifier of whatever other key is already at the position where 95006 would be inserted. Usually, BTPFIND would return identifier 552 after a search for ZIP 95006. But if identifier 704 happens to be at the end of a node in the the B-tree file, BTPFIND will return identifier 704, since inserting 95006 after 95005 instead of before 95007 is still a valid way to keep the B-tree sorted, and it simplifies the logic inside BTPFIND when the end of a B-tree node is reached at the end of a search.

While browsing, it's generally not important if the user requests 95006, and the browser highlights 95005 or 95007, since both are alongside the future position of 95006. But what if the user searches for 95007? If identifier 704 is not at the end of a B-tree node, then calling BTPFIND with a null identifier and ZIP 95007 will return identifier 552. But if identifier 704 is at the end of a node, BTPFIND will return identifier 704. Although the position after 704 is a valid insertion point for ZIP 95007 with a null identifier, a user normally expects the browser to highlight 552 after searching for ZIP 95007.

Such apparently "off by one record" results from BTPFIND occur more frequently if a small node size is chosen for a B-tree, since there are then more nodes, and more keys end up at the ends of nodes. To keep BTPFIND from stopping its search for an insertion point at the end of a node, change line 23 in BTPFIND from

IF NODE.POS > N<1> THEN NODE.POS = N<1>

to

IF NODE.POS > N<1> THEN

  NODE.POS = N<1>

  CALL BTPSEQ(BFILE,NODE.ID,NODE.POS,"NEXT",ID)

  RETURN

  END

Although the above code occasionally causes BTPFIND to do more work, the results of arbitrary searches while browsing will appear more meaningful to users, and in general provide a more "logical" result for calls to BTPFIND.