Theory: Index Files

By Mark Lester

Indexed Access

So you have stored our data in a database file containing multiple records. Now, how do you know which record number to use? And what about adding records in the middle of the data file? How do you update or append records to our database file and still maintain a particular record order? These problems are easily solved by the use of indexed access to database records. Indexed access provides the means to organize and retrieve information in a logical way by creating keys which are related to the records found in the database file.

Keys

Keys are generally comprised of one or more pieces of information found within the data fields found in the data record. In our example, the company name could be used as a key. Each key points to one or more records found in the data file. When many keys are grouped together they form an index file. xBase uses keys and an indexed lookup system called Indexed Sequential Access Method (ISAM) to permit this easy and logical access of data. Through the use of common fields in related databases, xBASE is capable of basic relational properties.

The index file's job is to keep a list of the keys that were generated from the data records (based on the key expression) and maintain them in sorted order. For each key that is stored, there is an associated record number which the key points to.

ISAM (Indexes)

An index is a structure used to contain and maintain keys in a sorted order. Keys are comprised of one or more fields from the database record. Each key points to one or more records. The index is usually a balanced B-Tree structure that is dynamically maintained by the DBMS. There are a variety of different index file types: NDX, MDX, NTX, IDX, compressed IDX, and CDX.

The keys in the index file are stored in a data structure called a B-Tree. Searching a B-Tree is very fast - much faster than using sequential access (reading the database file record by record until you find the record you are looking for).

Index Types

There are two basic types of index files: single index per file, and multiple indexes per file. The single index per file is the older style of index used by dBASE III+, FoxBase, and Clipper. The multiple indexes per file (also known as a compound index file) is the newer index file style supported by dBASE IV & 5 and FoxPro. The compound index file can greatly reduce the complexity of your database by limiting the number of files that must be open simultaneously.

As mentioned above, we need to view the index file as containing a list of keys which correspond to the records in our database file. The keys are in stored in order based on the key expression which built them. As a result of this ordering, any duplicate keys will be stored next to each other. This makes is quite easy to use the DBKeySearch( ) function to locate the first matching key and then use DBGoNextKey( ) to obtain any additional keys. DBGoNextKey( ) does not apply any search logic, it simply returns the next key in the index.

There is quite a bit of confusion regarding the key search functions. Here is the basic drill to seek for multiple keys:

  • Use DBKeySearch() to locate the first desired key.

  • If the desired key is found, fall into a loop.

  • First step of the loop is to use the first key to retrieve the desired record and process it.

  • Next use DBGoNextKey() to obtain the next key in the index file.

  • Now test the key to see if it meets the original search criteria.

  • If the key is good, then loop back  to DBGoNextKey() again and so on...

If you are interested in looking further into this you can probably search the internet for articles on B-Trees and how they work.

Did you find this article useful? Please tell us.

Back to Theory page.