Architecture of Btrieve - Indexing

Indexing

Btrieve uses a b-tree format to store record indexes on particular table columns. The index maps each set of indexed column values to the set of unique identifiers for the rows that have those column values, which provides a quick way to find the rows within a table using the indexed column. B-trees are tree data structures and are very efficient as a mechanism for fast data retrieval. The drawback of a btree is that data must be constantly balanced when it is inserted into the tree, therefore Btrieve only stores the record index as btree to reduce the amount of time it takes to insert and update records. A separate b-tree is kept for each index in the system, and the root node information is kept in the FCR. In Btrieve 6.x a new index can be created at file creation time, or added and dropped after the file is created. Index pages are also created as they are needed. Before Btrieve 6.0 existing key indexes could not be removed, though supplemental indexes could be created and dropped as needed.

Btrieve allows for duplicate key values in an index. Btrieve handles duplicate keys using either a linked duplicate method, or by using a repeating duplicate method (this terminology started being used when version 6.0 was released). The linked duplicate method used a pair of record pointers in the index page itself to point to the head and tail of a doubly linked list of duplicate keys. This meant that the order of the duplicate keys in the list was in the order they were entered. The duplicate key method did not use a linked list, but rather made all the keys unique by creating a new index key and appending the address of the record pointer to the end of the key. This means that the key is retrieved via its position order.