Estimating a Key's Location and File Size

The BTREE structure lends itself to estimating the overall number of keys in an index, as well as estimating the position of any key within the index. This function executes at most (2n+1) + NO.LEVELS-2 item reads.

n	Optimizing factor (the minimum number of keys per item).
NO.LEVELS	Number of levels in the tree.

This is an estimate and because of the way that a BTREE statistically builds, it can be in error by what may seem to be a significant amount. In general, the following concepts hold true for this estimate:

The estimate will be better with the fewer levels that the key file has and is exact if the key file has 2 or fewer levels.

The larger the file, the larger the errors.

In general, the error for a very large file can be as high as 200-300%, so the term estimate definitely applies to this function. In order to determine the position of a key along with the file size, use the KEYPOS statement.

KEYPOS Statement

The KEYPOS statement is used to determine the position of a BTREE key.

Format

KEYPOS locn, size IN file.var, keyname, key THEN/ELSE

Parameter(s)

locn	Location of the key (or where it would be placed in the key file if it is not present).
size	Estimates the overall size of the file.
file.var	Variable to which the file has been opened.
keyname	Name of the key to search along.
key	Key value to locate.

The ELSE clause is executed if the file is not a keyed file or if the specified keyname is invalid. If the ELSE clause executes, then the SYSTEM(0) function returns the error condition as:

0	File was not a keyed file.
1	Keyname was invalid.

Sample program using KEYPOS:

OPEN ‘CUSTOMERS’ TO CUST.FILE ELSE STOP 201,’CUSTOMERS’

PRINT ‘ENTER VALUE TO LOCATE‘:

INPUT VALUE

KEYPOS A,B IN CUST.FILE, ‘NAME’,VALUE ELSE

PRINT ‘KEY NOT FOUND’

STOP

END

PRINT ‘THE ENTERED VALUE IS IN POSITION‘: A

PRINT ‘THE TOTAL FILE SIZE IS‘: B