Editing Architecture of Btrieve (section)

==Indexing==
[[Image:Btree index.PNG|thumb|Btrieve uses indexes on certain columns to retrieve data in a speedy fashion. The structure at the top is a [[b-tree]] data structure and indexes the '''Employee ID''' column of the database table. The arrows point from the index value to the rows that contains the value in the "Employee ID" column.]]
Btrieve uses a [[b-tree]] format to store [[Index (database)|record indexes]] on particular [[Table (database)|table]] [[Column (database)|columns]]. The index maps each set of indexed column values to the set of unique identifiers for the [[Row (database)|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 structure]]s 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.