Using BTREE.READ (TB#101) (Functions/Subroutines/Programs)

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.

Syntax 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 I_filevar is the file handle to the index file being accessed. It is not the handle to the data file.

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

_ Value 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 Sort_method is either "AL" or "AR", indicating either a left-justified or a right-justified (numeric data) sort order in the index.

_ MAT record 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 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 Sep is returned by BTREE.READ. It is the value that all values in record are less than or equal to.

_ found 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.

Index Leaf Record Structure

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.

Field 1 - Node Flag

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.

Field 2 - Forward Pointer

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.

Field 3 - Backward Pointer

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 - Indexed Values

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 - Record Keys

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.

Figure 1

/* 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