B-tree Cache Classes

Contents

Overview
Usage
Conditional Directives
Constants
Public Data Members
B-tree Bucket Functions
B-tree Cache Functions
B-tree Cache Node Functions

Overview

The B-tree cache classes are a special adaptation of the Device Cache classes. They use the BtreeNode class as the bucket type and are tuned for B-tree operations. The cache links disk-based B-tree nodes to memory-based cache buckets. This lets the gxBtree class work with cache buckets in place of disk-based nodes. The goal is to reduce disk reads and writes during insert, find, and delete operations.

The B-tree cache uses three cooperating classes:

BtreeBucket - Derived from the BtreeNode class. A bucket holds one B-tree node in memory and records the file address of that node. Each bucket has a dirty flag that tells the cache the in-memory copy has changed and must be written to disk. Buckets also have previous and next pointers used to link them into a list.

BtreeCache - Allocates and frees a fixed number of buckets and handles requests for memory-based B-tree nodes. When a node is requested the cache first looks for a bucket already holding that node. If none is found it reuses the least recently reserved bucket, writing it to disk first if it is dirty, clears it, and loads the node from disk. If the cache is not connected to a file, a dirty bucket is not reused. Buckets are kept in a circular doubly linked list. The head of the list is the most recently reserved bucket and the tail is the least recently reserved bucket.

BtreeCacheNode - A lightweight pointer used to reach cache buckets directly. Each cache node stores a node address, a pointer to the bucket holding that node, and a pointer to its cache. The B-tree class uses cache nodes to load and unload buckets as needed.

The cache owns all bucket memory. The bucket array and the key storage of every bucket are allocated when the cache is constructed and freed when the cache is destroyed. Cache nodes never own memory. A cache node that is still in use after its cache is destroyed holds an invalid pointer.

The cache does not write changes to disk until a bucket is reused or one of the flush functions is called. The destructor flushes all dirty buckets to the connected database file, so the file must still be open when the cache is destroyed. Call BtreeCache::Flush() before closing the B-tree file.

Usage

Construct a cache from an open gxBtree object and pass a pointer to the cache to the cached versions of the gxBtree insert, find, change, and delete functions. The following code is taken from the examples_database/btree_cached test program:

BtreeCache btree_cache(num_buckets, &btx);
if(!btree_cache) {
  cout << "Error constructing the B-tree cache object" << "\n";
  return 0;
}
cout << "Cache size = " << btree_cache.CacheSize() << " bytes" << "\n";

rv = btx.Insert(key, compare_key, &btree_cache);
rv = btx.Find(key, compare_key, &btree_cache);

if(btree_cache.Flush() != gxDBASE_NO_ERROR) {
  cout << "Error flushing cache" << "\n";
  return 0;
}

The cached gxBtree functions are: ChangeKey(), ChangeOrAddKey(), Insert(), Delete(), FastDelete(), Find(), FindFirst(), FindNext(), FindPrev(), FindLast(), and PartialFind(). Some of these also have overloads that take a BtreeCacheNode reference to keep a search position.

Conditional Directives

__USE_BTREE_CACHE__ - The B-tree cache classes and the cached gxBtree functions are only compiled when this directive is defined. If it is not defined the btcache.h header declares nothing. The Linux build environment (env/linux.env) defines it by default.

Constants

Minimum number of cache buckets. The gxBtree insert function needs at least 2 cached nodes (left and right) and both delete functions need at least 3 cached nodes (left, right, and parent). If fewer buckets are requested the cache allocates this many instead.

const int MIN_BTREECACHE_SEGMENTS = 3;

Public Data Members

class BtreeBucket : public BtreeNode
{
public:
  BtreeBucket *prev; // Previous bucket in the list
  BtreeBucket *next; // Next bucket in the list
};

class BtreeCache
{
public: // Cache statistics
  unsigned uncached_reads; // Counts the number of disk reads
  unsigned cached_reads;   // Counts the number of cached reads
};

The BtreeCache statistics counters are updated by BtreeCache::AllocBucket(). A request for a node that is already in a bucket increments "cached_reads". A request for a node that is not in the cache increments "uncached_reads", even if the node is not loaded from disk. Use BtreeCache::ResetStats() to set both counters to zero. The bucket "prev" and "next" pointers are managed by the cache and should not be changed by the application.

B-tree Bucket Functions

BtreeBucket::Flush()
BtreeBucket::GetNode()
BtreeBucket::HasKeys()
BtreeBucket::IsDirty()
BtreeBucket::IsNull()
BtreeBucket::ReadNode()
BtreeBucket::ResetBucket()
BtreeBucket::ResetNode()
BtreeBucket::SetDirty()
BtreeBucket::WriteNode()
BtreeBucket::BtreeBucket()
BtreeBucket::~BtreeBucket()

gxDatabaseError BtreeBucket::Flush(gxDatabase *f)

Public member function used to write this bucket to the database file "f" if the bucket is dirty and has a non-zero node address. After a successful write the key count, node address, and dirty flag are reset. A bucket that is not dirty is left unchanged. Returns zero if successful or a non-zero value to indicate a failure.

BtreeNode *BtreeBucket::GetNode()

Public member function that returns this bucket as a pointer to its BtreeNode base class.

int BtreeBucket::HasKeys()

Public member function that returns true if the node in this bucket has one or more keys.

int BtreeBucket::HasKeys() const

Public member function that returns true if the node in this bucket has one or more keys. Const version.

int BtreeBucket::IsDirty()

Public member function that returns true if this bucket has been marked dirty.

int BtreeBucket::IsDirty() const

Public member function that returns true if this bucket has been marked dirty. Const version.

int BtreeBucket::IsNull()

Public member function that returns true if this bucket is not linked to a node, meaning its node address is zero.

int BtreeBucket::IsNull() const

Public member function that returns true if this bucket is not linked to a node, meaning its node address is zero. Const version.

gxDatabaseError BtreeBucket::ReadNode(gxDatabase *f)

Public member function used to load the B-tree node stored at this bucket's node address from the database file "f". Only the key count, the left child pointer, and the keys actually in use are read. The dirty flag is cleared after a successful read. Returns gxDBASE_NULL_PTR if "f" is null, zero if successful, or the database error code if a read fails.

void BtreeBucket::ResetBucket()

Public member function used to clear the dirty flag and set the node address and key count to zero. The memory used to store keys is not freed.

void BtreeBucket::ResetNode()

Public member function used to set the key count to zero without changing the node address or the dirty flag.

void BtreeBucket::SetDirty()

Public member function used to mark this bucket as dirty. A dirty bucket is written to disk when it is flushed or reused. Call this function after changing the node held in the bucket.

gxDatabaseError BtreeBucket::WriteNode(gxDatabase *f)

Public member function used to write the node in this bucket to its node address in the database file "f". Only the key count, the left child pointer, and the keys actually in use are written. The writes are not flushed and the block is not bit tested. The dirty flag is cleared after a successful write, but the node address and keys are kept. Returns gxDBASE_NULL_PTR if "f" is null, zero if successful, or the database error code if a write fails.

BtreeBucket::BtreeBucket()

Default class constructor. Calls ResetBucket(). The key storage is allocated later by the BtreeCache class when it builds its bucket array.

BtreeBucket::~BtreeBucket()

Class destructor. Does nothing itself. The BtreeNode base class destructor frees the key storage.

B-tree Cache Functions

BtreeCache::AllocBucket()
BtreeCache::BucketsInUse()
BtreeCache::CacheSize()
BtreeCache::Connect()
BtreeCache::ConstructCache()
BtreeCache::DemoteBucket()
BtreeCache::DestroyCache()
BtreeCache::FindBucket()
BtreeCache::Flush()
BtreeCache::GetHead()
BtreeCache::GetTail()
BtreeCache::gxDatabasePtr()
BtreeCache::IsEmpty()
BtreeCache::LRUFlush()
BtreeCache::NumBuckets()
BtreeCache::operator int()
BtreeCache::operator!()
BtreeCache::PromoteBucket()
BtreeCache::ResetStats()
BtreeCache::BtreeCache()
BtreeCache::~BtreeCache()

BtreeBucket *BtreeCache::AllocBucket(FAU_t node_address, int load_bucket = 1)

Public member function used to reserve a bucket for the node at "node_address". If the node is already in the cache its bucket is moved to the head of the list and returned. Otherwise the tail bucket is written to disk if it is dirty, moved to the head of the list, cleared (key count and left child set to zero), and assigned to the node. If "load_bucket" is equal to 1 the node is then read from disk. Returns a pointer to the bucket or a null value if an error occurs. A zero node address, a failed flush, a failed read, a dirty tail bucket when the cache is not connected to a file, or a cache that is not connected to a file when a load is needed are all errors. If the read fails the bucket is cleared and moved to the tail of the list. For most errors the gxDBASE_CACHE_ERROR code is set in the connected database file. NOTE: 10/14/2026: Fixed three problems. A reused bucket kept the keys of the node it held before, so a new node reserved without loading (such as a new root node) started with old keys. A failed read left the bucket assigned to the node, so the next request returned unread data as a cache hit. A dirty bucket was reused and its changes lost when the cache had no file.

unsigned BtreeCache::BucketsInUse()

Public member function that returns the number of dirty buckets in the cache.

unsigned BtreeCache::CacheSize()

Public member function that returns the number of bytes allocated for the cache. The value is set when the cache is constructed. It equals the number of buckets multiplied by the sum of the bucket object size and the key storage size of one node.

unsigned BtreeCache::CacheSize() const

Public member function that returns the number of bytes allocated for the cache. Const version.

gxDatabaseError BtreeCache::Connect(gxDatabase *fptr)

Public member function used to connect the cache to an open database file. If the cache is already connected to a file, all dirty buckets are flushed to that file first. Returns gxDBASE_NULL_PTR if "fptr" is null, zero if successful, or a non-zero value if the flush fails. If the flush fails the cache stays connected to the old file.

BtreeBucket *BtreeCache::ConstructCache(unsigned num_bkts, BtreeSize_t dbkey_size, BtreeNodeOrder_t order)

Public member function used to allocate the bucket array as one contiguous block and link the buckets into a circular list. Each bucket gets key storage for "order" minus 1 keys of "dbkey_size" bytes. An order less than 5 is raised to 5, the same minimum used by the BtreeNode constructor. If "num_bkts" is less than MIN_BTREECACHE_SEGMENTS, the minimum is used. If a bucket array already exists it is destroyed first, which also flushes and disconnects the cache. The statistics counters are reset. Returns a pointer to the bucket array. NOTE: 10/14/2026: Fixed buckets for orders below 5 having fewer key slots than the uncached B-tree nodes stored in the same file.

void BtreeCache::DemoteBucket(BtreeBucket *bucket)

Public member function used to move the specified bucket to the tail of the list, making it the least recently reserved bucket and the next one to be reused. Does nothing if the cache is empty or "bucket" is null.

void BtreeCache::DestroyCache()

Public member function used to flush all dirty buckets, disconnect the cache from its database file, and free the bucket array.

BtreeBucket *BtreeCache::FindBucket(FAU_t node_address)

Public member function used to search the cache for the bucket holding the node at "node_address". Does not change the order of the list or the statistics counters. Returns a pointer to the bucket or a null value if the node is not in the cache.

gxDatabaseError BtreeCache::Flush()

Public member function used to write every dirty bucket to the connected database file, starting at the head of the list. Flushed buckets are reset and no longer hold their node. Returns gxDBASE_NULL_PTR if the cache is not connected or has no buckets, gxDBASE_FILE_NOT_READY if the file is not open for writing, zero if successful, or the database error code if a write fails.

BtreeBucket *BtreeCache::GetHead()

Public member function that returns a pointer to the head of the bucket list, which is the most recently reserved bucket.

BtreeBucket *BtreeCache::GetHead() const

Public member function that returns a pointer to the most recently reserved bucket. Const version.

BtreeBucket *BtreeCache::GetTail()

Public member function that returns a pointer to the tail of the bucket list, which is the least recently reserved bucket.

BtreeBucket *BtreeCache::GetTail() const

Public member function that returns a pointer to the least recently reserved bucket. Const version.

gxDatabase *BtreeCache::gxDatabasePtr()

Public member function that returns a pointer to the database file the cache is connected to, or a null value if the cache is not connected.

int BtreeCache::IsEmpty()

Public member function that returns true if no bucket array is allocated.

int BtreeCache::IsEmpty() const

Public member function that returns true if no bucket array is allocated. Const version.

gxDatabaseError BtreeCache::LRUFlush(unsigned num_to_flush)

Public member function used to flush up to "num_to_flush" buckets, starting at the tail of the list (the least recently reserved bucket) and moving toward the head. Clean buckets count toward "num_to_flush" but are not written. Returns the same values as Flush().

int BtreeCache::NumBuckets()

Public member function that returns the total number of buckets allocated.

int BtreeCache::NumBuckets() const

Public member function that returns the total number of buckets allocated. Const version.

BtreeCache::operator int()

Conversion operator that returns true if a bucket array is allocated. Used to test the cache after construction.

BtreeCache::operator const int() const

Const conversion operator that returns true if a bucket array is allocated.

int BtreeCache::operator!()

Overloaded not operator that returns true if no bucket array is allocated.

int BtreeCache::operator!() const

Overloaded not operator that returns true if no bucket array is allocated. Const version.

void BtreeCache::PromoteBucket(BtreeBucket *bucket)

Public member function used to move the specified bucket to the head of the list, making it the most recently reserved bucket. Does nothing if the cache is empty or the bucket is already at the head.

void BtreeCache::ResetStats()

Public member function used to set the uncached_reads and cached_reads counters to zero.

BtreeCache::BtreeCache(unsigned num_bkts, gxBtree *btree)

Class constructor used to build a cache of "num_bkts" buckets for an open gxBtree. The key size and node order are taken from the B-tree header and the cache is connected to the B-tree's database file. Use the not operator to test for an allocation failure.

BtreeCache::BtreeCache(unsigned num_bkts, BtreeSize_t dbkey_size, BtreeNodeOrder_t order)

Class constructor used to build a cache of "num_bkts" buckets for nodes with the given key size and node order. The cache is not connected to a file. Call Connect() before using it.

BtreeCache::~BtreeCache()

Class destructor. Calls DestroyCache(), which flushes all dirty buckets to the connected file and frees all bucket memory.

B-tree Cache Node Functions

BtreeCacheNode::Alloc()
BtreeCacheNode::Bind()
BtreeCacheNode::Delete()
BtreeCacheNode::GetBucket()
BtreeCacheNode::GetCache()
BtreeCacheNode::GetNodeAddress()
BtreeCacheNode::HasBucket()
BtreeCacheNode::operator FAU_t()
BtreeCacheNode::operator*()
BtreeCacheNode::operator->()
BtreeCacheNode::operator=()
BtreeCacheNode::Release()
BtreeCacheNode::BtreeCacheNode()
BtreeCacheNode::~BtreeCacheNode()

int BtreeCacheNode::Alloc(BtreeNode *node, FAU_t address = (FAU_t)0)

Public member function used to reserve a bucket, copy the key count, left child pointer, and keys of "node" into it, and mark the bucket dirty so the copy is written to disk when the bucket is flushed or reused. If "address" is zero a new block the size of the node is allocated in the database file first. Returns true if successful or false if a bucket could not be reserved, in which case the gxDBASE_CACHE_ERROR code is set if no other error is set. NOTE: 10/14/2026: Fixed the copied node never being marked dirty, so it was not written to disk. Also fixed a crash when the cache was not connected to a file.

int BtreeCacheNode::Alloc(BtreeNode &node, FAU_t address = (FAU_t)0)

Public member function that calls Alloc(&node, address).

BtreeBucket *BtreeCacheNode::Alloc(size_t node_size, FAU_t address = (FAU_t)0)

Public member function used to reserve a bucket for the node at "address" without reading it from disk. If "address" is zero a new block of "node_size" bytes is allocated in the database file and its address is used. On success the node address of this cache node is set. Returns a pointer to the bucket, or a null value if the cache is not connected, the block allocation fails, or no bucket can be reserved. NOTE: 10/14/2026: Fixed a crash when no bucket could be reserved and the cache was not connected to a file.

BtreeBucket *BtreeCacheNode::Bind()

Public member function used to bind this cache node to the bucket holding its node address. If the current bucket still holds that address it is returned. Otherwise the cache reserves a bucket and loads the node from disk. If no bucket can be reserved the node address is set to zero and a null value is returned. NOTE: 10/14/2026: Fixed a crash when the cache was not connected to a file.

int BtreeCacheNode::Delete()

Public member function used to release the bucket this cache node points to. The bucket is reset, which clears its dirty flag so the node is not written to disk, and the bucket is moved to the tail of the list for reuse. The node address of this cache node is set to zero. The block in the database file is not freed. Returns true if successful or false if the cache is not connected, this cache node has no bucket, or the bucket now holds a different node. NOTE: 10/14/2026: Fixed a crash when this cache node had no bucket and the cache was not connected to a file.

BtreeBucket *BtreeCacheNode::GetBucket()

Public member function that returns the current bucket pointer without binding. The bucket may have been reused for another node.

BtreeBucket *BtreeCacheNode::GetBucket() const

Public member function that returns the current bucket pointer without binding. Const version.

BtreeCache *BtreeCacheNode::GetCache()

Public member function that returns a pointer to the cache this cache node is connected to.

BtreeCache *BtreeCacheNode::GetCache() const

Public member function that returns a pointer to the cache this cache node is connected to. Const version.

FAU_t BtreeCacheNode::GetNodeAddress()

Public member function that returns the file address of the node this cache node refers to.

FAU_t BtreeCacheNode::GetNodeAddress() const

Public member function that returns the file address of the node this cache node refers to. Const version.

int BtreeCacheNode::HasBucket()

Public member function that returns true if this cache node has a bucket pointer.

int BtreeCacheNode::HasBucket() const

Public member function that returns true if this cache node has a bucket pointer. Const version.

BtreeCacheNode::operator FAU_t()

Conversion operator that returns the node address of this cache node.

BtreeBucket &BtreeCacheNode::operator*()

Overloaded indirection operator. Calls Bind() and returns a reference to the bucket. The result is not checked, so the bucket must be valid.

BtreeBucket *BtreeCacheNode::operator->()

Overloaded arrow operator. Calls Bind() and returns a pointer to the bucket, which may be null.

BtreeCacheNode &BtreeCacheNode::operator=(const BtreeCacheNode &ob)

Assignment operator. Copies the bucket and cache pointers from "ob" and sets the node address of this cache node to zero, the same as the copy constructor.

void BtreeCacheNode::operator=(FAU_t address)

Assignment operator used to set the node address and call Bind(), which loads the node into a bucket.

void BtreeCacheNode::Release()

Public member function used to set the bucket pointer to null. The bucket and the node address are not changed.

BtreeCacheNode::BtreeCacheNode(BtreeCache &btree_cache, FAU_t address = (FAU_t)0)

Class constructor used to connect this cache node to a cache and set its node address. No bucket is bound until the node is used.

BtreeCacheNode::BtreeCacheNode(BtreeCache *btree_cache, FAU_t address = (FAU_t)0)

Class constructor used to connect this cache node to a cache, given a pointer, and set its node address.

BtreeCacheNode::BtreeCacheNode(const BtreeCacheNode &ob)

Copy constructor. Copies the bucket and cache pointers from "ob" and sets the node address to zero. The node address is not copied on purpose: the cached gxBtree search functions copy the current node to get a node on the same cache and test for a zero address to see if a parent node has been set.

BtreeCacheNode::~BtreeCacheNode()

Class destructor. Does nothing. The bucket remains in the cache.