Using BTREE.READ

There are times when you need direct access to indexed values. Much of the time, the system subroutine, BTREE.EXTRACT will perform this job quickly and efficiently, returning a sub-set of record keys that matches the required specifications. However, while BTREE.EXTRACT is powerful, versatile, and easy to use, it has two limitations:

• It will only return up to 64K worth of record keys, even though there may be more keys that would match the search criteria.
• It returns only the record keys, not the index values.

You can use system subroutine BTREE.READ to address these limitations. BTREE.READ returns the complete index record that contains the searched-for value. Since each index record contains the record keys to the next and previous records in the index you use the record returned by BTREE.READ as a start and follow pointers from there.

Use BTREE.READ to find a starting position within an index. Once the starting position is found, you can traverse the index based on your search criteria. The syntax for BTREE.READ is:

BTREE.READ(i_filevar, field, value, sort_method, MAT record, i, sep, found)

I_filevar is the file handle to the index file being accessed. It is not the handle to the data file.

Field is the name of the indexed field being accessed, for example, "NAME.XREF" or "DATE".

Value contains the value to be searched for. This is a single value, not a range. If a partial word is passed, for example, "SM", a starting-with search is implied.

The format of value must match the format of the data stored in the index. If data is stored in internal format, you must convert value to its internal representation before passing it to BTREE.READ.

Sort_method is either "AL" or "AR", indicating either a left-justified or a right-justified (numeric data) sort order in the index.

Record is a 5 element dimensioned array that has been initialized to null (""). BTREE.READ returns an index leaf record in record. For more information on the layout of record, see "Index Leaf Record Structure" below.

I is a variable that acts as an index into the value mark- delimited arrays of values and associated record keys returned in record.

Sep is returned by BTREE.READ. It is the value that all values in record are less than or equal to.

Found is a flag indicating whether or not the exact value searched for was found. If found is true (1), i points to the value that contains the searched-for value. If found is false (0), i points to the position in the index where the value would be located if it existed.

Figure 1 demonstrates calling BTREE.READ.

BTREE.READ returns a Btree index leaf node. Understanding the structure of the leaf node will help you understand BTREE.READ. A leaf node is a 5 field record. Each field has a different meaning.

The first field in the index leaf record contains a value of either "0", "1", or "2", where "2" denotes that this record contains index values and keys. The other values indicate that the record contains branch information and no actual index values.

The second field contains the record key to the next record in the index, assuming ascending order. The index record keys take the form of <fieldname>*<optional-identifier>*<separator value>.

The optional identifier is used when there is more than one index leaf record that contains a single indexed value, common in large files with relatively few index values for a field, i.e. a status code field that can contain only a few possible values.

The separator value is the same as the value returned by BTREE.READ in sep.

If field 2 is empty then this is the last leaf record in the index.

The third field contains the record key to the previous record in the index, again assuming ascending order. If field 3 is empty, then this is the first leaf record in the index.

Field 4 contains a value-mark delimited list of index values, sorted in either left-justified (alphabetical) or right-justified (numeric). The BTREE.READ argument i references a position in this list.

Field 5, the last field in the index leaf record, contains a multivalued list of keys. Each value is associated with the index value in the same position in field 4. If more than one key is associated with an index value, then the keys are delimited with subvalue marks.

Multi-User Access BTREE.READ does not perform any locking. If your index file is being updated by multiple users simultaneously these problems could result:

• The forward or backward pointer in record could point to a non-existant record.
• The values in the index could change as you traverse the index.

To prevent the index from changing as you traverse the index, you should lock the root node of the index (the "FieldName*ROOT" record in the indexing file) before accessing the index. Users will still be allowed to update the data file and to post new index transactions. Be sure to unlock the root when you're finished with the index.

If you must allow updates while traversing the index use this strategy to account for a shifting index:

• If your read of the next index record fails, reread the current record from the index. This will give you an updated version of the record with new pointers.
• If the new pointer fails (the read still doesn't return a record) call BTREE.READ again with using the last index value in val. This will give you a new starting position within the index from which to to start traversing.

Warning! Both of these techniques could result in your program missing records or in your program processing the same record twice.

/* This program searches the customer_name index using BTREE.READ and
   returns all records that have an indexed value between "SMITH" and
   "THOMPSON".
*/

DECLARE SUBROUTINE BTREE.READ, FSMSG

EQU TRUE$  TO 1
EQU FALSE$ TO 0
EQU NULL$  TO ""

DIM I_RECORD(5)
MAT I_RECORD = NULL$
I            = NULL$
SEP          = NULL$
FOUND        = NULL$
I_FILEVAR    = NULL$

FIELD        = "CUSTOMER_NAME"
VALUE        = "SMITH"
MAX_VALUE    = "THOMPSON"

/* Get the sort information from the index.*/
SORT_METHOD = XLATE("!SAMPLE_CUSTOMERS", FIELD, 1, "X")

OPEN "!SAMPLE_CUSTOMERS" TO INDEX_FILE ELSE
  FSMSG()
  STOP
END

OPEN "SAMPLE_CUSTOMERS" TO CUSTOMER_FILE ELSE
  FSMSG()
  STOP
END

LOCKED = FALSE$
LOOP
  LOCK INDEX_FILE, FIELD:"*ROOT" THEN
    LOCKED = TRUE$
  END
  UNTIL LOCKED
REPEAT

BTREE.READ(INDEX_FILE,FIELD,VALUE,SORT_METHOD,MAT I_RECORD,I,SEP,FOUND)
/* Find the starting position in the key list in element five of the index
leaf record.
*/
IF I > 1 THEN
  POS = INDEX(I_RECORD(5), @VM, I-1) + 1
END ELSE
  POS = 1
END

FLAG = NULL$
DONE = FALSE$
LOOP
/* Get the next key to process */
  REMOVE @ID FROM I_RECORD(5) AT POS SETTING FLAG
  READ @RECORD FROM CUSTOMER_FILE, @ID THEN
    GOSUB PROCESS_RECORD
  END
  IF FLAG = 3 THEN
    /* REMOVE sets FLAG to 3 when a value mark is found. Finding a value
    mark indicates the indexed value has changed. */

    IF I_RECORD(4)<1,I> > MAX_VALUE THEN
      /* No more valid values to process. */
      DONE = TRUE$
    END
  END ELSE
    IF FLAG ELSE
      /* If flag = 0 then we have reached the end of the current leaf record
      and it is time to read the next record or stop. */
      IF I_RECORD(2) THEN
        /* There is a pointer to another record. */
        MATREAD I_RECORD FROM INDEX_FILE, I_RECORD(2) THEN
          /* Start at the beginning of the list of keys in the new record.*/
          POS = 1
          I = 1
        END ELSE
          /* Recovery logic goes here if you're not locking the index. */
          DONE = TRUE$
        END
      END ELSE
        /* There are no more index records. */
        DONE = TRUE$
      END
    END
  END
UNTIL DONE
REPEAT

UNLOCK INDEX_FILE, FIELD:"*ROOT" ELSE
  FMSG()
END

PROCESS_RECORD:
/* Logic to process records goes here. */
RETURN