Table of Contents
The B Tree is stored in a standard UNIX file. To support efficient processing, the size of a B Tree node should be the same as the hardware's disk block size. In the following description, the terms node and block are interchangeable.
A B Tree has a root, which acts as the starting point for all insertions, deletions and searches. A B Tree has a master root stored at file address 0 (zero), which is termed the "superroot". The superroot holds the names and root block addresses of all the B Trees in the file. The superroot also holds the free block list for the file and other administrative information.
Each block contains a number of keys, an associated integer value and pointers to other blocks. The maximum number of keys that can be stored in a block depends on the size of a block and the maximum number of bytes permitted for a key. The integer value associated with a key can be used as desired by the application program. If the record storage facilities of the B Tree are used, it will contain the block address of an associated data record.
Version 3.1 and above allows the definition of duplicate keys, which is enabled on a per-root basis. If not enabled, this version with behave as previous versions, that is, duplicate keys will be rejected.
When a B Tree file is created, the superroot is initialised with two named roots: itself and the default root. These are defined as "$$super" and "$$default" respectively. The application may create more roots as required. When a B Tree file is first opened, the default root ($$default) is always selected.
The maximum size of a B Tree file is governed by the implementation. For an implementation with a 32 bit word length, the maximum file size supported is 2GiB. If the B Tree library is built with Large File Support, that limit is removed.
