B-Tree Databases

A b-tree database consists of two files: an index file and a data file. The index file is used to organize information that is stored in the data file. The index file contains a set of keys that are maintained in ascending sequence. Associated with each key is a record number. This record number identifies the record in the data file that is associated with the key.

The keys in the index file can be accessed sequentially or randomly. For a given key, the associated record number can be used to retrieve the data file information that is related to that key.

Two or more b-trees may be based on a single data file. This allows the information in the data file to be organized in several different ways. For a file containing employee information, one might construct one index to access employee information by employee number, while creating another index to access the information by employee name.

The b-tree functions are summarized below.

B-tree open, close and flush

File creation functions

Index file functions

Data file functions

B-trees are created by the bt_create_data and bt_create_tree functions. These functions create an empty data file and an empty index file respectively.

When a data file is created, the record size must be specified. If text information is to be stored, then record size should be the length of the longest possible string. If structure information is stored, then record size should be the size of the structure (sizeof <structure name>).

Before a b-tree can be accessed, it must be opened with bt_open . This function returns a b-tree handle. Index file functions use this handle to identify the index file, while data file functions use the handle to identify the data file. If two b-trees use a common data file, then either handle can be used to identify the data file.