Btree Subroutines

Copying Btree Subroutines

The subroutines in the lib directory are compiled into the shared library, libbthash.so.

Subroutine Description
btinit Initialize a btree database
btopen Open the database
btopent Create a temporary database
btclose Close the database
btcloset Remove a temporary database from disk
btisrt Insert a record in the database
btupdt Replace a record in the database
btdlet Delete a record from the database
btget Read a record in the database
btgetnxt Read the next higher record in the database
btgetp Read a record searching backward
btgetprv Read the next lower record in the database
btsweep Read the next physical record in the database
btdbck Check the integrity of the database
btdlets Count deleted index nodes
btreorg Reorganize the database
btdepth Compute the depth of the database
btlock Lock the database (UNIX)
btunlock Unlock the database (UNIX)

Update Transaction

The following calls may be used together to create an update transaction.


btinit

Read Initialize a Btree Database about initializing a database.


btopen

btreefmt *btopen(char *dbname, int rwflag, int lock, int *reason);

Parameters:

Processing:

btopen tests for locks. If no lock is pending, it opens the database according to the read/write parameter. Then it reads the first 256 bytes of the database to gather schema information about the database. It validates the signature of the database before formatting the btreefmt structure. It allocates memory for buffers and initializes the stack. The btreefmt structure is not freed until btclose. If more than one database is open, the buffers are kept separate.

Returns:

Error Codes


btopent

btreefmt *btopent(int nodesz, int rcdlen, int keylen, int keyofst, int *reason, unsigned char *seed);

Parameters:

Processing:

btopent creates a temporary database name. It then calls btinit to create the temporary database and initialize it. Finally, it calls btopen to make it available for update. The temporary database is locked until it is closed with btcloset.

A temporary database is useful for joins and views of a permanent database. It is also useful for creating summary databases for reports.

Returns:

Error Codes


btclose

int btclose(btreefmt *bthdr);

Parameters:

Processing:

btclose closes the database. Then it frees all allocated memory in the btreefmt structure. Finally, it frees the btreefmt structure, itself.

Returns:

Zero for good close.

Error Codes


btcloset

int btcloset(btreefmt *bthdr);

Parameters:

Processing:

btcloset closes the database by calling btclose. It then removes the temporary database from disk.

The link count for the temporary database must go to zero before it can be removed. If the program pipes to another process, the link count may not go to zero. In that case the file may not be removed.

Returns:

Zero for good close.

Error Codes


btisrt

int btisrt(btreefmt *bthdr, off_t ofst, unsigned char *rcd);

Parameters:

Processing:

Locking is mandatory during insert. If a lock is pending, btisrt returns with an error. After a successful insert, the file is unlocked only if it was not opened with a lock. If the file was opened with a lock, the lock remains in effect after a good insert.

btisrt looks for an existing record with the same key. If no record exists with the same key, it tries to fit the record in the appropriate leaf node. The Cormen algorithm is used to split nodes. All blocks in the tree path are split before the insertion takes place. If the offset parameter is for a sub-tree, a higher level split will not occur. Therefore, specify ROOT as the offset, unless you know what you are doing. The algorithm for splitting the root is different from the algorithm for splitting a lower level node. Frequently a split cascades upward to the root.

Returns:

Error Codes


btupdt

int btupdt(btreefmt *bthdr, off_t ofst, unsigned char *rcd);

Parameters:

Processing:

Locking is mandatory during update. If a lock is pending, btupdt returns with an error. After a successful update, the file is unlocked only if it was not opened with a lock. If the file was opened with a lock, the lock remains in effect after a good update.

btupdt looks for the record matching the embedded key. If the record is found, it is replaced in the same physical location and written back to disk. If the matching key is a deleted index node, the record is replaced and becomes an active node in the same index block. The pointers remain unchanged.

No splits occur in btupdt.

Returns:

Error Codes


btdlet

int btdlet(btreefmt *bthdr, off_t ofst, unsigned char *key);

Parameters:

Processing:

Locking is mandatory during delete. If a lock is pending, btdlet returns with an error. After a successful delete, the file is unlocked only if it was not opened with a lock. If the file was opened with a lock, the lock remains in effect after a good delete.

btdlet looks for the record matching the key. If the record is found, it is deleted. If the record is an index node, the delete byte is set to hex FF. If the record is a leaf node, the record is erased and the space is reused.

See btinit for more information how to define the delete byte.

Returns:

Error Codes


btget

int btget(btreefmt *bthdr, off_t ofst, unsigned char *key, unsigned char *buf);

Parameters:

Processing:

btget searches recursively for an existing record with the same key. If no existing record is found, it returns the record with the next higher key.

If the key is matched to a deleted index node, the record is treated as not found. The next higher record is not returned in this case. You will have to use the btgetnxt call to obtain the next higher record.

Returns:

Error Codes


btgetnxt

int btgetnxt(btreefmt *bthdr, off_t ofst, unsigned char *key, unsigned char *buf);

Parameters:

Processing:

btgetnxt adds a value of one to the search key. It then searches recursively for an existing record with the new key. If no existing record is found, it returns the record with the next higher key.

btgetnxt assumes that the user will search with the last key read. Therefore it returns the next record after the last one read.

Returns:

Error Codes


btgetp

int btgetp(btreefmt *bthdr, off_t ofst, unsigned char *key, unsigned char *buf);

Parameters:

Processing:

btgetp searches recursively for an existing record with the same key. If no existing record is found, it returns the record with the next lower key. The search is performed from the end toward the front of each block.

If the key is matched to a deleted index node, the record is treated as not found. The next lower record is not returned in this case. You will have to use the btgetprv call to obtain the next lower record.

This routine is the logical mirror image of btget.

Returns:

Error Codes


btgetprv

int btgetprv(btreefmt *bthdr, off_t ofst, unsigned char *key, unsigned char *buf);

Parameters:

Processing:

btgetprv subtracts a value of one from the search key. It then searches recursively for an existing record with the new key. If no existing record is found, it returns the record with the next lower key.

btgetprv assumes that the user will search with the last key read. Therefore it returns the record before the last one read.

Returns:

Error Codes


btsweep

int btsweep(btreefmt *bthdr, int position, unsigned char *buf);

Parameters:

Processing:

btsweep reads the database in physical sequence. The block is saved in bthdr->blk. The record number in the block is saved in bthdr->rcdnum. The ofset of the block is saved in bthdr->ofst. The sequence number of the record is saved in bthdr->seq. After all records have been read from a block, the next block is read.

btsweep returns one record per call. This subroutine is useful for matching criteria in the data portion of the record. It is also useful for doing mass updates to the database. Remember that the keys are usually out of sequence.

Returns:

Error Codes


btdbck

int btdbck(btreefmt *bthdr);

Parameters:

Processing:

btdbck reads the database in physical sequence. Every pointer is mapped into a bit map. If a pointer is mapped twice, it is an error. If a pointer points to the root block, it is an error. If the bitmap lacks a pointer to a block, it is an error.

No leaf nodes can have pointers. No index node can have a null pointer.

Returns:

Error Codes


btdlets

int btdlets(btreefmt *bthdr, int *blocks, int *count, int *leaf, int *nonleaf, int *active, int *deletes, int *indxrcd, int *leafrcd);

Parameters:

Processing:

btdlets reads the database in physical sequence. Every type of record is counted in its respective total. The total number of active records is computed by subtracting the number of deletes from the count of records.

This routine is useful for determining when to reorganize the database. When the number of deletes gets too high, it is time to reorganize.

Returns:

Error Codes


btreorg

int btreorg(btreefmt *bthdr);

Parameters:

Processing:

btreorg copies the database to a temporary database. Then it renames the temporary database to the original database.

Be sure to back up the database before you run this routine. There is a risk of losing your data during the renames.

btreorg closes the original database with btclose before the rename occurs. When you receive control back from btreorg, you will have to open the database to use it.

Returns:

Error Codes


btdepth

int btdepth(btreefmt *bthdr);

Parameters:

Processing:

btdepth follows the right pointer starting with the root. It counts the number of levels deep it can go, following the pointers.

Returns:

Error Codes


btlock (UNIX)

int btlock(btreefmt *bthdr);

Parameters:

Processing:

btlock returns if the database is locked by another user. If the database is not locked, the lock is applied and the database status is now LOCK;

Returns:

Error Codes


btunlock (UNIX)

int btunlock(btreefmt *bthdr);

Parameters:

Processing:

If the database is locked, the unlock is applied and the database status is now NOLOCK;

Returns:

Error Codes