B-tree Node Class

Topics:

Overview
Conditional Directives
Constants
Type Definitions
Enumerations
Data Members
Functions

The BtreeNode class is used by the gxBtree class to insert, delete, and search for database keys in a node. Database keys are derived from the DatabaseKeyB class and are kept in sorted order within each B-tree node. Both the BtreeNode and DatabaseKeyB classes operate independently of actual key type. The database key class derived from the DatabaseKeyB defines how the keys are sorted within the B-tree nodes. The number keys per node is determined by the node order which must be set each time a BtreeNode object is constructed.

Public Data Members

BtreeNodeOrder_t BtreeNode::node_order - Non-persistent data member used to set the B-tree order

BtreeSize_t BtreeNode::key_size - Non-persistent data member used to set the size of a key plus overhead.

FAU BtreeNode::node_address - Non-persistent data member used record the file address of this node.

BtreeKeyCount_t BtreeNode::key_count - Persistent data member used to count how many keys are in use.

FAU BtreeNode::left_child - Persistent data member used to record the file offset pointing to this node's left child.

char * BtreeNode::key_entries - Persistent array of database key entries.

Functions

BtreeNode::BtreeNode()
BtreeNode::~BtreeNode()
BtreeNode::AppendDatabaseKey()
BtreeNode::DeleteDatabaseKey()
BtreeNode::FindKeyLocation()
BtreeNode::GetBranch()
BtreeNode::HasFew()
BtreeNode::HasMany()
BtreeNode::HighestKey()
BtreeNode::InsertDatabaseKey()
BtreeNode::IsEmpty()
BtreeNode::IsFull()
BtreeNode::LoadKey()
BtreeNode::MergeNode()
BtreeNode::OverWriteDatabaseKey()
BtreeNode::SizeOfBtreeNode()
BtreeNode::SplitNode()

BtreeNode::BtreeNode() - Default class constructor. This constructor will not allocate any memory for the entry key array.

BtreeNode::BtreeNode(BtreeSize_t dbkey_size, BtreeNodeOrder_t order) - Class constructor used to set the database key size and the node order for this object. This constructor is responsible for allocating memory for the entry key array based on the key size and node order.

BtreeNode::~BtreeNode() - Class destructor responsible for release the memory allocated for the entry key array.

void BtreeNode::AppendDatabaseKey(DatabaseKeyB &key) - Public member function used to append a database key to the end of this node.

void BtreeNode::DeleteDatabaseKey(BtreeKeyLocation_t key_location) - Public member function used to delete the database key at specified location.

int BtreeNode::FindKeyLocation(const DatabaseKeyB &key, DatabaseKeyB &compare_key, BtreeKeyLocation_t &key_location) - Public member function used to find the key location. Returns 0 if an entry for the key already exists, 1 if the specified key is greater then all the entries in this node, or -1 if the specified key is less the all the entries in this node. The key class derived from the abstract DatabaseKeyB base class defines the key methods used by this function to compare the keys. The key location or the branch to keep searching down the tree is passed back in the "key_location" variable. 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 the comparison because the comparison operators are not defined in the DatabaseKeyB base class.

FAU BtreeNode::GetBranch(BtreeKeyLocation_t key_location) - Public member function that returns the node's left or right child based on the specified key location. The -1th branch represents the nodes left child. The right branch of this key will be returned starting from the 0th branch on.

int BtreeNode::HasFew() - Public member function that returns true if this node has fewer than the minimum number of entries.

int BtreeNode::HasMany() - Public member function that returns true if this node has more than the minimum number of entries required.

BtreeKeyLocation_t BtreeNode::HighestKey() - Public member function that returns the position of the highest key in the node.

void BtreeNode::InsertDatabaseKey(DatabaseKeyB &key, BtreeKeyLocation_t key_location) - Public member function used to insert a database key into the node at the specified location.

int BtreeNode::IsEmpty() - Public member function that returns true if this node is empty.

int BtreeNode::IsFull() - Public member function that returns true if this node is full.

void BtreeNode::LoadKey(DatabaseKeyB &key, BtreeKeyLocation_t key_location) - Public member function used to copy the key at the specified location into the "key" variable.

void BtreeNode::MergeNode(BtreeNode &node) - Public member function used to merge this node with the specified node.

void BtreeNode::OverWriteDatabaseKey(DatabaseKeyB &key,BtreeKeyLocation_t key_location) - Public member function used to overwrite the key at the specified location.

size_t BtreeNode::SizeOfBtreeNode() - Public member function that calculates the total size of this Btree node.

void BtreeNode::SplitNode(BtreeNode &node, BtreeKeyLocation_t split_location) - Public member function used to split this node by moving the keys, starting at the "split_location", into specified node.

End Of Document