URL: http://www.firstbasesoftware.com/man/man4/btree.htm
Last modified: 12 September 1995
Copyright © by FirstBase Software.
[
Index of Contents] [
FirstBase RDBMS Overview]
The FirstBase Btree index set is a multiple level tree structured index to the sequence set that provides direct access to database records. The node at the top of the tree is called the root.
The database structure, as explained in database(4), also contains pointers to Btree sequence and index sets, as well as to an arry of automatically maintained btree indexes.
typedef struct fb_s_link fb_link; /* defined link */ typedef struct fb_s_field fb_field; /* defined field */ typedef struct fb_s_database fb_database;/* defined database */ typedef struct fb_s_bidx fb_bidx; /* btree+ index set */ typedef struct fb_s_bseq fb_bseq; /* btree+ sequence set */ typedef struct fb_s_ixauto fb_autoindex;/* autoindex structure */ struct fb_s_bidx { /* btree+ index set node */ long bi_left; /* left side info */ char bi_ltype; long bi_middle; /* middle side info */ char bi_mtype; long bi_right; /* right side info */ char bi_rtype; char *bi_key1; /* separation keys */ char *bi_key2; int bi_lock; char *bi_name; /* index name */ int bi_fd; /* index set file descriptor */ char *bi_rec; /* storage for index record */ int bi_ksize; /* size of an index key */ long bi_root; /* index root */ long bi_height; /* index height */ long bi_recsiz; /* index record size */ long bi_recno; /* current record number */ long bi_reccnt; /* index record count */ long bi_free; /* free pointer */ }; struct fb_s_bseq { /* btree+ sequence set node */ long bs_prev; /* prev and next pointers */ long bs_next; char *bs_key1; /* index keys */ char *bs_key2; char *bs_key3; int bs_curkey; /* current key pointer */ int bs_lock; char *bs_name; /* sequence file name */ int bs_fd; /* sequence file descriptor */ char *bs_rec; /* storage for sequnce record */ int bs_ksize; /* size of a sequence key */ long bs_head; /* head of sequence list */ long bs_tail; /* tail of sequence list */ long bs_recsiz; /* size of sequence record */ long bs_recno; /* current sequence record number */ long bs_reccnt; /* sequence record count */ long bs_free; /* free pointer */ }; struct fb_s_link { fb_database *f_dp; /* pointer to linked database */ fb_field *f_fix; /* indexed value in 'from' database */ fb_field *f_tix; /* ix val in 'to' db providing link */ fb_field *f_ffp; /* field within 'from' database */ fb_field *f_tfp; /* field within 'to' database */ char *f_fld; /* storage area for field val */ char *f_xfld; /* index value creating field link */ fb_link *f_next; /* to link all flinks for searching */ long f_absrec; /* absolute record number to use */ fb_database *f_basedp; /* database which referred link */ }; struct fb_s_ixauto { /* auto indexed field struct */ char *autoname; /* for storing autoindex name */ char *dup_fld; /* for 'old' field value */ int afd, hfd; /* auto index and header fds */ short uniq; /* uniqness flag */ int ix_tree; /* btree flag */ fb_bseq *ix_seq, *ix_seqtmp; /* btree sequence set */ fb_bidx *ix_idx, *ix_idxtmp; /* btree index set */ fb_field **ix_ip; /* field pointers array for auto ix */ long ix_bsmax, ix_bsend; /* for btrees - for auto ix array */ int ix_ifields; /* number of fields in the ix array */ char *ix_key_fld; /* key space for index entry */ }; struct fb_s_field { /* a database field */ char *id; /* unique title labeling field */ char type; /* type of the field */ int size; /* maximum size of field */ int loc; /* location when arec is used */ char *fld; /* actual pointer to field */ int incr; /* to store incremental defaults */ char *comment, *idefault, *help, *prev, *range, *a_template, *f_macro; char comloc, lock, choiceflag; /* various flags */ fb_autoindex *aid; /* pointer to auto index data */ fb_link *dflink; /* link to other database */ fb_link *xflink; /* extended choice/link database */ char *mode; /* permissions settings per field */ short int f_prec; /* precision for field */ }; struct fb_s_database { /* FB database header record */ char *dbase; /* full database path names */ char *dindex; char *dmap; char *ddict; char *idict; char *sdict; /* simple screen name */ char *dlog; /* log name of database */ long reccnt; /* full record count */ char dirty; /* dirty bit == 0 or 1 */ long delcnt; /* deleted record count */ long rec; /* current record number */ int recsiz; /* approximate record size */ int nfields; /* number of fields */ int fd; /* database file descriptor */ int ifields; /* number of index fields */ int ifd; /* index file descriptor */ int ihfd; /* index header file descriptor */ int logfd; /* log file descriptor */ int irecsiz; /* index record size */ long bsmax, bsend, bsrec; /* search max/end points */ int mfd; /* record map file descriptor */ fb_field **kp; /* array of fields */ fb_field **ip; /* array of index fields */ char *orec; /* original copy of rec */ char *arec; /* alternate copy of rec */ char *irec; /* buffer for an index record */ char *afld; /* field buffers for this db */ char *bfld; /* field buffers for this db */ int refcnt; /* reference count for linktop list */ /* B+tree index fields */ int b_tree; /* flag set if dbase is using btrees */ fb_bseq *b_seq, *b_seqtmp; /* sequence set (and temp space) */ fb_bidx *b_idx, *b_idxtmp; /* index set (and temp space) */ fb_autoindex **b_autoindex; /* autoindex ptr array */ int b_maxauto; /* max number of auto index */ int b_curauto; /* cur number of auto index array */ short int fixedwidth; /* fixed width flag */ int b_sid; /* server id - open via server */ };
When a database is opened, the entire database structure is initialized. Optionally, the btree index structures may be initialized also. Note that a formal index dictionary (index.idicti) file is required for all Btree indexes that are not a simple autoindexes (as defined in the database dictionary).
The array of database field structures is allocated on the fly to contain as many fields as are defined in the database dictionary. Each field descriptor is a structure itself. These structures contain the name of the field, its type and size, as well as various pointers to comments, help files, and defaults. The important parts for indexes are the size and type of the field.
If a database is opened with an index, either a Btree index, or a standard flat index, an arry of field pointers representing indexed fields is stored in the database structure variable ip. Automatic Btree indexes, from the b_autoindex array, store their array of field pointers in b_autoindex[N]->ix_ip, where N means the Nth index. (See autoindex(5) for more).
FirstBase routines are provided to handle many indexing tasks. The following is a list of provided functions. Each has a related manual page.
- addidx - subidx - openidx - closeidx - createidx - getxrec - nextxrec - prevxrec - firstxrec - lastxrec - useidx
The next two pieces of header information in the index dictionary are used to keep track of the number of key entries in the Btree sequence set. For Btree indexes, this number is written twice, each one as raw data exactly sizeof(long) bytes.
As mentioned, this header information is delimited by a newline character. The remaining lines list the actual field names that the index data itself refers to. The trailing '%' sign indicates this index is a Btree index.
All keys within the FirstBase Btree mechanisms contain the record number that the keys exist in. Thus, each entry into a Btree is unique, even if the keys are the same.
In standard FirstBase manner, each of the FirstBase Btree sequence set records is stored to disk as a fixed length ASCII record. A header at the top of the sequence set file stores four values, all raw data exactly sizeof(long): head, tail, record count, and a free list pointer.
In standard FirstBase manner, each of the FirstBase Btree index set records is stored to disk as a fixed length ASCII record. A header at the top of the sequence set file stores four values, all raw data exactly sizeof(long): root, height, record count, and a free list pointer.
Note that two methods of autoindexes are available. The original method via the database dictionary, and a more robust method via the autoindex list (see autoindex(5)). If you desire to use the original method, and want FirstBase to use the original flat index mechanism, then a special FirstBase environment variable, AUTOBTREE, must be set to OFF in the setup file.
To enable applications to switch between different auto indexes using the autoindex list, see useidx(3).