Itzam/Core

C API Documentation (B-tree Indexes)



 

Itzam/C 5.0.0 Download: (tar.gz) (bzip2) (zip) Open Source License (GPL) Non-free, Closed-Source License: $495 Itzam/Sharp 1.0.3 Download: (Windows Set-up Application) Open Source License (GPL) Non-free, Closed-Source License: $395 Itzam/Java 2.2.0 Download: (source) (extension) Open Source License (GPL) Non-free, Closed-Source License: $395

Index

General Types & Functions
Datafiles
About Keys
B-tree Indexes
B-tree Index Cursors
Hash Indexes
Sparse Matrix Indexes
 

The B-tree data structure maintains a list of keys in order, as determined by a user-supplied key comparison function. You determine the sort order via the comparison function supplied when opening or creating an itzam_btree. Just be certain that you always use the same comparison function whenever making changes to the index.

All keys must be unique in a B-tree index.

More about keys

Functions that directly manipulate b-tree indexes follow the naming pattern itzam_btree_*.

Types and Structures

itzam_btree

For the most part, you won't directly access the members of an itzam_btree structure. However, it is possible (and often quite desirable) to store non-index data in the same datafile used by an index. The example program does this very thing, combining contact records with the name-based B-tree index.

typedef struct
{
    itzam_datafile * m_datafile;       // file associated with this btree file
    
    // The rest is internal stuff
}
itzam_btree;

itzam_key_comparator

A B-tree index uses a comparator to determine the relative order of two keys. The user defines and supplies a comparator function pointer when opening or creating an index; the function's signature must match this type definition.

typedef int itzam_key_comparator(const void * key1, const void * key2);

Parameters
btree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be created
key_comparator - a function that compares two index keys

Return Value
< 0, if key1 is before key2
= 0, if key1 equals key2
> 0, if key1 is after key2

Functions

itzam_btree_create

Creates a new B-tree index by creating a data file with a specific internal structure. Keys will be ordered based on comparisons performed via the called-supplied key_comparator function.

itzam_state itzam_btree_create(itzam_btree * btree,
                               const char * filename,
                               itzam_file_lock_mode lock_mode,
                               uint16_t order,
                               itzam_int key_size,
                               itzam_key_comparator * key_comparator);

Parameters
btree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be created
lock_mode - the mode of file locking; possible values include ITZAM_LOCK_NONE (no locking), ITZAM_LOCK_OS (lock via operating system functions), and ITZAM_LOCK_FILE (lock using temporary secondary file)
buckets - the number of "buckets" held in the hash table; a larger number of buckets results in a faster the index and a bigger the datafile
order - the number of keys held in each B-tree page; predefined constants include ITZAM_BTREE_ORDER_DEFAULT (which works well for most indexes) and ITZAM_BTREE_ORDER_HUGEFILE (meant for databases containing more than a million different indexes)
key_size - the number of bytes in the key being stored
key_comparator - a function that compares two index keys

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_open

Opens an existing B-tree index file. The key_comparator function must produce the same results as the comparison functions used in previous manipulations of the index. In other words, always use the same key_comparator function for a given index.

itzam_state itzam_btree_open(itzam_btree * btree,
                             const char * filename,
                             itzam_file_lock_mode   lock_mode,
                             itzam_key_comparator * key_comparator,
                             bool read_only,
			     bool recover);

Parameters
btree - a pointer to the target itzam_btree structure
filename - the platform-specific name of the file to be opened
lock_mode - the mode of file locking; possible values include ITZAM_LOCK_NONE (no locking), ITZAM_LOCK_OS (lock via operating system functions), and ITZAM_LOCK_FILE (lock using temporary secondary file)
buckets - the number of "buckets" held in the hash table; a larger number of buckets results in a faster the index and a bigger the datafile
key_comparator - a function that compares two index keys
read_only - if true, the file will be opened read-only (no writes allowed)
recover - if true, any unfinished transactions will be rolled back; if false, existing transaction files are simply deleted

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_close

Closes an open B-tree file and flushes any remaining file operations.

itzam_state itzam_btree_close(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_insert

Adds a new record reference to the index, with a given key. The index does not place any semantics on the value of reference; it is merely stored in association with key. The reference can be a file pointer in btree->m_datafile or a file position in another datafile, or any other 64-bit value of the caller's choosing.

itzam_state itzam_btree_insert(itzam_btree * btree,
                               const void * key);

Parameters
btree - a pointer to the target itzam_btree structure
key - a pointer to the key data that identifies the record reference

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_find

Finds the record reference associated with a given key.

itzam_ref itzam_btree_find(itzam_btree * btree,
                           const void * search_key
                           void * result);

Parameters
btree - a pointer to the target itzam_btree structure
search_key - a pointer to the key data that identifies the record result - a pointer to key data that will be updated with the contents found by searchign for search_key

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_remove

Removes the first key found that is associated with the given key. If ref is NULL, the function also attempts to remove the associated record from the btree->m_datafile. If ref is not NULL, this function returns the record reference associated with the deleted key.

itzam_state itzam_btree_remove(itzam_btree * btree,
                               const void * key);

Parameters
btree - a pointer to the target itzam_btree structure
key - a pointer to the key data that identifies the record

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_lock

Exclusively locks a btree, preventing other processes or threads form making changes.

bool itzam_btree_lock(itzam_btree * btree, bool read_only);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; btree is in an unknown state

itzam_btree_unlock

Removes an existing lock from the file.

bool itzam_btree_unlock(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; btree is in an unknown state

itzam_btree_transaction_start

Begins a new transaction and locks the file. Until a commit or reollback is performed, all changes to the btree file are recorded in an external journal file.

itzam_state itzam_btree_transaction_start(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_transaction_commit

Commits the current transaction, which makes all changes permanent. The temporary journal file is removed, and the file unlocked.

itzam_state itzam_btree_transaction_commit(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_transaction_rollback

The current transaction is "rolled back", meaning that all changes to the file will be "undone". The temporary journal file is removed, and the file unlocked.

itzam_state itzam_btree_transaction_rollback(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
ITZAM_OKAY if the function succeeded
ITZAM_UNKNOWN the function failed; datafile is in an unknown state

itzam_btree_count

Returns the number of active keys stored in the B-tree.

uint64_t itzam_btree_count(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
The number of active keys in the B-tree.

itzam_btree_ticker

Returns a count of the number of times a key has been added to the B-tree.

uint64_t itzam_btree_ticker(itzam_btree * btree);

Parameters
btree - a pointer to the target itzam_btree structure

Return Value
The number of times a key has been added to the B-tree.