Chapter 1. Introduction

The B Tree (BT) library offers a set of C language functions which implement a generalised index file capability, based on the B tree indexing scheme. The B tree was originally described by Bayer and McCraight. A B tree is a multiway balanced tree: i.e. there is more than one key per node, and all leaf nodes are the same distance from the root node.

The BT functions implement a 'classical' B tree, not one of the later variants (B* or B+ tree).

The B Tree is stored in a UNIX disk file. The file can contain many B Trees, each of which is referred to by a name assigned by the user (or application). The system allows many such files to exist.

In order for BT to function efficiently on different hardware platforms, the important constants relating to disk block size, maximum number of keys per block, etc. are defined as constants, and may be modified prior to compilation.