BTREE(3)

NAME

btree_open, btree_open_fd, btree_close, btree_txn_begin, btree_txn_get, btree_txn_put, btree_txn_del, btree_txn_commit, btree_txn_abort, btree_get, btree_put, btree_del, btree_txn_cursor_open, btree_cursor_open, btree_cursor_close, btree_cursor_get, btree_stat, btree_compact, btree_revert, btree_sync, btree_set_cache_size, btree_get_flags, btree_get_path, btree_cmp, btval_reset — Append-only prefix B+Tree database library.

SYNOPSIS

#include <btree.h>

struct btree *

btree_open_fd(int fd, uint32_t flags);

struct btree *

btree_open(const char *path, uint32_t flags, mode_t mode);

void

btree_close(struct btree *bt);

struct btree_txn *

btree_txn_begin(struct btree *bt, int rdonly);

int

btree_txn_get(struct btree *bt, struct btree_txn *, struct btval *key, struct btval *data);

int

btree_txn_put(struct btree *bt, struct btree_txn *, struct btval *key, struct btval *data, unsigned flags);

int

btree_txn_del(struct btree *bt, struct btree_txn *, struct btval *key, struct btval *data);

int

btree_txn_commit(struct btree_txn *txn);

void

btree_txn_abort(struct btree_txn *txn);

int

btree_get(struct btree *bt, struct btval *key, struct btval *data);

int

btree_put(struct btree *bt, struct btval *key, struct btval *data, unsigned flags);

int

btree_del(struct btree *bt, struct btval *key, struct btval *data);

struct cursor *

btree_txn_cursor_open(struct btree *bt, struct btree_txn *txn);

struct cursor *

btree_cursor_open(struct btree *bt);

void

btree_cursor_close(struct cursor *cursor);

int

btree_cursor_get(struct cursor *cursor, struct btval *key, struct btval *data, enum cursor_op op);

struct btree_stat *

btree_stat(struct btree *bt);

int

btree_compact(struct btree *bt);

int

btree_revert(struct btree *bt);

int

btree_sync(struct btree *bt);

void

btree_set_cache_size(struct btree *bt, unsigned int cache_size);

unsigned int

btree_get_flags(struct btree *bt);

const char *

btree_get_path(struct btree *bt);

int

btree_cmp(struct btree *bt, const struct btval *a, const struct btval *b);

void

btval_reset(struct btval *btv);

DESCRIPTION

The database is implemented as a modified prefix B+tree. Instead of modifying the database file inplace, each update appends any modified pages at the end of the file. The last block of the file contains metadata and a pointer to the root page.

Append-only writing gives the following properties:

No locks. Since all writes are appended to the end of the file, multiple readers can continue reading from the tree as it was when they started. This snapshot view might contain outdated versions of entries.

Resistance to corruption. The file content is never modified. When opening a database file, the last good meta-data page is searched by scanning backwards. If there is trailing garbage in the file, it will be skipped.

Hot backups. Backups can be made on a running server simply by copying the files. There is no risk for inconsistencies.

The drawback is that it wastes space. A 4-level B+tree database will write at least 5 new pages on each update, including the meta-data page. With 4 KiB pagesize, the file would grow by 20 KiB on each update.

To reclaim the wasted space, the database can be compacted. The compaction process opens the database and traverses the tree. Each active page is then written to a new file. When complete, the old file is replaced. Any updates committed after the file was opened will be lost. All processes using the file should re-open it.

CURSORS

A new cursor may be opened with a call to btree_txn_cursor_open() or btree_cursor_open(). The latter is implemented as a macro to the former with a NULL txn argument. Multiple cursors may be open simultaneously. The cursor must be closed with btree_cursor_close() after use.

The cursor can be placed at a specific key by setting op to BT_CURSOR and filling in the key argument. The cursor will be placed at the smallest key greater or equal to the specified key.

The database may be traversed from the first key to the last by calling btree_cursor_get() with op initially set to BT_FIRST and then set to BT_NEXT. If the cursor is not yet initialized, ie btree_cursor_get() has not yet been called with op set to BT_FIRST or BT_CURSOR, then BT_NEXT behaves as BT_FIRST.

TRANSACTIONS

There are two types of transactions: write and read-only transactions. Only one write transaction is allowed at a time. A read-only transaction allows the grouping of several read operations to see a consistent state of the database.

A transaction is started with btree_txn_begin(). If the rdonly parameter is 0, a write transaction is started and an exclusive lock is taken on the file. No lock is taken for read-only transactions.

The transaction is ended either with btree_txn_commit() or btree_txn_abort(). The btree_txn pointer must not be accessed afterwards.

RETURN VALUES

The btree_txn_get(), btree_txn_put(), btree_txn_del(), btree_txn_commit(), btree_get(), btree_put(), btree_del(), btree_cursor_get(), btree_compact() and btree_revert() functions all return BT_SUCCESS on success and BT_FAIL on failure.

btree_txn_put() and btree_put() returns BT_EXISTS if the key already exists and BT_NOOVERWRITE was not passed in the flags argument.

btree_txn_get(), btree_txn_del(), btree_get(), btree_del() and btree_cursor_get() returns BT_NOTFOUND if the specified key was not found.

All functions returning pointers to structs returns NULL on error.