B-tree Class


Topics:

Overview
Conditional Directives
Constants
Type Definitions
Enumerations
Headers
Functions


Overview

A B-tree (Balance multi-way tree) is a special type of tree designed for fast disk-based insert, delete, and search operations. B-trees comprise a collection of multi-way nodes arranged in sort order. Multi-way nodes are used to store a left child pointer and multiple entry keys, with smaller keys on the left and larger keys on the right. Each entry key stores some type of data and right child pointer. The number of entry keys per node is determined by the node order. By definition B-trees are balanced, meaning that all nodes, except the root node, must be at least half full following an insertion or deletion. A single insertion can cause a number of splits all the way to the root node. The excessive node splitting that can occur following insertions and deletions complicate non-serialized concurrent operations.

The gxBtree class is a non-recursive disk-base B-tree used by various database applications for searching and sorting structured data and indexing associated objects or records stored in a data file. The gxBtree uses the 32/64-bit gxDatabase engine to perform all disk operations, supporting large files and proprietary file system interfaces. This is a non-recursive B-tree implementation designed to index any type of data regardless of the key type. It was originally designed to index multiple data types in read-only data files with 10M to 100M entries per index. Concurrent operations can be supported directly by serializing access to the entire tree or specific nodes during key insertions and key deletions. Additionally, concurrent operations can be supported using unbalanced deletions and file synchronization functions.

The gxBtree class uses three primary classes:

DatabaseKeyB - Abstract base class used to define database key types and the methods by which database keys are sorted. The key type and comparison operators are defined in the derived class allowing the B-tree to index multiple data types.

BtreeNode - B-tree node class used to manipulate a preset order of keys values in memory and on disk. B-tree nodes are stored on disk and manipulated in memory for fast disk-based operations.

BtreeStack - Stack used in place of the processor stack to store node addresses during non-recursive insertions and deletions. Eliminating recursive insertions and deletions allow a single B-tree to grow extremely large and maintain stability.


Type Definitions

gxClassID - Persistent class ID type

gxClassID_t - Native class ID type

gxObjectID - Persistent object ID type

gxObjectID_t - Native object ID type

BtreeNodeOrder_t - Type used for the B-tree node order

BtreeSize_t - Type used to store entry key sizes

BtreeKeyCount_t - Type used for the B-tree node key count

BtreeKeyLocation_t - Type used for B-tree node key locations

Database engine type definitions


B-tree Headers

The B-tree header is a persistent data structure required to store tree parameters from one invocation of the program to the next. Each header is stored in a pre-allocated static storage area within the gxDatabase file. Multiple B-trees can be stored in a single file provided that a separate header exists for every tree.

struct gxBtreeHeader
{ 
  BtreeNodeOrder_t node_order; // B-tree node order
  BtreeSize_t key_size;        // Database key size
  BtreeSize_t n_keys;          // Total number of entry keys
  BtreeSize_t n_nodes;         // Total number of nodes
  BtreeSize_t btree_height;    // Height of this B-tree
  FAU root;                    // B-tree root address  
  gxClassID class_id;          // Optional class ID for B-tree object keys
};


Functions

gxBtree::gxBtree()
gxBtree::~gxBtree()
gxBtree::BtreeHeader()
gxBtree::BtreeHeight()
gxBtree::ClassID()
gxBtree::Close()
gxBtree::CollapseRoot()
gxBtree::Create()
gxBtree::DatabaseExceptionMessage()
gxBtree::Delete()
gxBtree::DeleteDatabaseKey()
gxBtree::Find()
gxBtree::FindFirst()
gxBtree::FindLast()
gxBtree::FindNext()
gxBtree::FindPrev()
gxBtree::Flush()
gxBtree::GetDatabaseError()
gxBtree::GrowNewRoot()
gxBtree::HeaderAddress()
gxBtree::HeaderInSync()
gxBtree::InitBtree()
gxBtree::Insert()
gxBtree::InsertBalance()
gxBtree::InsertDatabaseKey()
gxBtree::InsertLeftRotation()
gxBtree::InsertRightRotation()
gxBtree::IsEmpty()
gxBtree::KeySize()
gxBtree::LazyDelete()
gxBtree::LazyDeleteDatabaseKey()
gxBtree::Merge()
gxBtree::NodeOrder()
gxBtree::NumKeys()
gxBtree::NumNodes()
gxBtree::Open()
gxBtree::ReInit()
gxBtree::ReadBtreeHeader()
gxBtree::ReadNode()
gxBtree::Release()
gxBtree::ResetDatabaseError()
gxBtree::Root()
gxBtree::SetDatabaseError()
gxBtree::TestTree()
gxBtree::TotalNodeSize()
gxBtree::WriteBtreeHeader()
gxBtree::WriteNode()
gxBtree::gxDatabasePtr()

gxBtree::gxBtree(DatabaseKeyB &key_type, BtreeNodeOrder_t order,gxClassID cid = (gxClassID_t)-1) - Class constructor used to set the database entry key type and node order. The class ID is an optional parameter used by applications that require unique class IDs when indexing associated objects.

virtual gxBtree::~gxBtree() - Virtual class destructor responsible for closing the file and flushing any open disk buffers.

gxBtreeHeader *gxBtree::BtreeHeader() - Public member function that returns a pointer to B-tree header.

BtreeSize_t gxBtree::BtreeHeight() - Public member function that returns the height of the B-tree.

gxClassID gxBtree::ClassID() - Public member function that returns the class ID of this B-tree.

gxDatabaseError gxBtree::Close() - Public member function used to close the open B-tree file. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::CollapseRoot() - Protected member function used to collapse the current root node and shorten the tree. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::CollapseRoot(BtreeNode &root_node) - Protected member function used to collapse the specified root node after a read operation and shorten the tree. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::Create(const char *fname, int num_trees = 1) - Public member function used to create a new B-tree file, specifying the number of trees this index will contain. NOTE: This create function only initialize the first tree header and will always connect the tree to the first tree header. Returns zero if successful or a non-zero value to indicate a failure.

const char *gxBtree::DatabaseExceptionMessage() - Public member function that returns a null terminated string, which can be used to log or print the last reported database engine exception.

int gxBtree::Delete(DatabaseKeyB &key, DatabaseKeyB &compare_key, int flush = 1) - Public member function used to delete the specified key and balance the B-tree following the deletion. Returns true if successful or false if the key could not be deleted. By default all disk buffers will be flushed following a deletion to maintain synchronization during multiple file access. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class.

gxDatabaseError gxBtree::DeleteDatabaseKey(DatabaseKeyB &key, DatabaseKeyB &compare_key) -Protected non-recursive balanced B-tree delete function used to ensure that all nodes, with the exception of the root node, are at least half full following a deletion. Returns zero if successful or a non-zero value to indicate a failure.

int gxBtree::Find(DatabaseKeyB &key, DatabaseKeyB &compare_key, int test_tree = 1) - Public member function used to find the specified key in the B-tree. Returns true if successful or false if the key could not be found. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class.

int gxBtree::FindFirst(DatabaseKeyB &key, int test_tree = 1) - Public member function used to find the first key in the B-tree. If the "test_tree" variable is true a test is performed to ensure that the file data stays in sync during multiple file access. Returns true if successful or false if the key could not be found.

int gxBtree::FindLast(DatabaseKeyB &key, int test_tree = 1) - Public member function used to find the last key in the B-tree. If the "test_tree" variable is true a test is performed to ensure that the file data stays in sync during multiple file access. Returns true if successful or false if the key could not be found.

int gxBtree::FindNext(DatabaseKeyB &key, DatabaseKeyB &compare_key,int test_tree = 1) - Public member function used to find the next key after the specified key, passing back the key in the "key" variable. If the "test_tree" variable is true a test is performed to ensure that the file data stays in sync during multiple file access. Returns true if successful or false if the key could not be found. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class.

int gxBtree::FindPrev(DatabaseKeyB &key, DatabaseKeyB &compare_key,int test_tree = 1) - Public member function used to find the previous key before the specified key, passing back the key in the "key" variable. If the "test_tree" variable is true a test is performed to ensure that the file data stays in sync during multiple file access. Returns true if successful or false if the key could not be found. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class.

gxDatabaseError gxBtree::Flush() - Public member function used to write the B-tree header and flush any open disk buffers. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::GetDatabaseError() - Public member function the returns an error code representing the last reported database error.

gxDatabaseError gxBtree::GrowNewRoot(DatabaseKeyB &key) - Protected member function used to grow a new root node. Returns zero if successful or a non-zero value to indicate a failure.

FAU gxBtree::HeaderAddress() - Public member function that returns the file address of the B-tree header for this tree.

int gxBtree::HeaderInSync() - Public member function that returns true if the in-memory copy of the B-tree header is in sync with the disk copy.

gxDatabaseError gxBtree::InitBtree(gxDatabase *fptr, int create, FAU header_address) - Public member function used to connect the B-tree to the database engine and write a new B-tree header if the "create" variable is true. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::InitBtree(int create, FAU header_address) - Public member function used connect the B-tree to a header in the open database engine or write a new B-tree header if the "create" variable is true. Returns zero if successful or a non-zero value to indicate a failure.

int gxBtree::Insert(DatabaseKeyB &key, DatabaseKeyB &compare_key, int flush = 1) - Public member function used to insert the specified key. By default all disk buffers will be flushed following an insertion to maintain synchronization during multiple file access. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class. Returns true if successful or false if the key could not be inserted.

gxDatabaseError gxBtree::InsertBalance(BtreeNode &parent_node, BtreeKeyLocation_t key_location, DatabaseKeyB &compare_key) - Protected member function used to balance this parent's sibling node after performing a deletion. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::InsertDatabaseKey(DatabaseKeyB &key, DatabaseKeyB &compare_key) - Protected non-recursive insertion function used to insert a key into the B-tree. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::InsertLeftRotation(BtreeNode &parent_node, BtreeKeyLocation_t key_location,DatabaseKeyB &compare_key) - Protected member function used by the gxBtree::InsertBalance() function to perform a left rotation. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::InsertRightRotation(BtreeNode &parent_node, BtreeKeyLocation_t key_location,DatabaseKeyB &compare_key) - Protected member function used by the gxBtree::InsertBalance() function to perform a right rotation. Returns zero if successful or a non-zero value to indicate a failure.

int gxBtree::IsEmpty() - Public member function that returns true if the B-tree is empty.

BtreeSize_t gxBtree::KeySize() - Public member function that returns the current key size.

int gxBtree::LazyDelete(DatabaseKeyB &key, DatabaseKeyB &compare_key, int flush = 1) - Public member function used to delete the specified key without balancing the tree following the deletion. Returns true if successful or false if the key could not be deleted. By default all disk buffers will be flushed following a deletion to maintain synchronization during multiple file access. NOTE: The "DatabaseKeyB& compare_key" is a type cast from the derived key class back to a DatabaseKeyB base type and is required to perform comparisons because the comparison operators are not defined in the DatabaseKeyB base class.

gxDatabaseError gxBtree::LazyDeleteDatabaseKey(DatabaseKeyB &key,DatabaseKeyB &compare_key) - Protected lazy (unbalanced) deletion method implemented specifically to support concurrent database operations that are effected by the excessive node splitting and merging that occurs during tree rotations. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::Merge(BtreeNode &parent_node, BtreeKeyLocation_t key_location,DatabaseKeyB &compare_key) - Protected member function used by the gxBtree::InsertBalance() function to merge the parents left and right siblings and remove the right sibling. Returns zero if successful or a non-zero value to indicate a failure.

BtreeNodeOrder_t gxBtree::NodeOrder() - Public member function that returns the node order for this B-tree

BtreeSize_t gxBtree::NumKeys() - Public member function that returns the total number entry keys stored in this B-tree.

BtreeSize_t gxBtree::NumNodes() - Public member function that returns the total number of B-tree nodes.

gxDatabaseError gxBtree::Open(const char *fname, gxDatabaseAccessMode mode = gxDBASE_READWRITE) - Public member function used to open an existing B-tree file. Returns zero if successful or a non-zero value to indicate a failure. NOTE: This function assumes that there is only one B-tree in this file.

gxDatabaseError gxBtree::Open(const char *fname, FAU header_address,gxDatabaseAccessMode mode = gxDBASE_READWRITE) - Public member function used to open an existing B-tree file, specifying the file address of the B-tree header. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::ReInit(int flush = 0) - Public member function used to reconnect the B-tree header to ensure that the file data stays in sync during multiple file access and multiple instances of the same application. If the "flush" variable is true, the file buffers will be flushed to disk before reconnecting the B-tree. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::ReInit(FAU header_address, int flush = 0) - Public member function used to reconnect the B-tree to a new tree header. If the "flush" variable is true, the file buffers will be flushed to disk before reconnecting the B-tree. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::ReadBtreeHeader() - Public member function used to Read the B-tree header from disk. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::ReadNode(BtreeNode &node, FAUnode_address = gxCurrAddress) - Public member function used to read a B-tree node from the specified file address. Returns zero if successful or a non-zero value to indicate a failure.

void gxBtree::Release() - Public member function used to reset the database file pointer to zero without closing the file or performing any other action. NOTE: This function is used to reset the file pointer when more then one object is referencing this file pointer and the file has been closed or the pointer has been deleted. You can also use the a Release() class to signal that this object is finished with the file and can be deleted without affecting other objects currently using this file.

gxDatabaseError gxBtree::ResetDatabaseError() - Public member function Public member function used to reset the last reported database engine error.

FAU gxBtree::Root() - Public member function that returns the file address of this B-tree's root node.

gxDatabaseError gxBtree::SetDatabaseError(gxDatabaseError err) - Public member function used to set the last reported database engine error. This function is used to inform the database engine of a fatal error condition. Redundantly returns the "err" value to allow this function to be used as a return value.

int gxBtree::TestTree(int reinit = 1) - Public member function used to ensure that the file data stays in sync during multiple file access. If the "reinit" variable is true this function will reconnect the B-tree header. Returns zero if no errors were encountered or an integer value corresponding to one of the following values:

1 = Node order error
2 = Key size error
3 = Number of keys error
4 = Number of nodes error
5 = B-tree height error
6 = B-tree root address error
7 = B-tree class ID error
8 = Error reading the B-tree header

size_t gxBtree::TotalNodeSize() - Public member function that returns the total size of a single Btree node, including overhead.

gxDatabaseError gxBtree::WriteBtreeHeader() - Public member function used to write the B-tree header to disk. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabaseError gxBtree::WriteNode(const BtreeNode &node,FAU node_address = gxCurrAddress) - Public member function used to write a B-tree node to the specified file address. Returns zero if successful or a non-zero value to indicate a failure.

gxDatabase *gxBtree::gxDatabasePtr() - Public member function that returns a pointer to the database engine.


End Of Document