Products Support Documentation Download
B-Tree Index

The default indexing method for RDM is the B-tree. A B-tree is a self-balancing tree structure that keeps data ordered to allow for both searching and sequential access. Insertions, deletions, updates, and lookups can be done in a logarithmic scale. A B-tree is a good solution for on-disk databases because the width of the B-tree nodes can keep the depth of the node tree smaller than a self-balancing binary tree. This results in fewer disk access required for searching and updates to the tree.

The RDM B-tree implementation is a non-clustered external tree sorted on the column values specified in the index definition. There is an entry in a B-tree node for each row in the table the index is derived from. Nodes are identified by their object id, referred to as a node id for node objects. This allows the implementation to be efficient for databases using either the on-disk or the in-memory engine. In both engines, references to a node id will be looked up via the id index for the drawer the B-tree is stored in. In the on-disk engine, the id-index will contain an offset and size of the node in the pack file. In the in-memory engine, the id index will contain a pointer to the node. The RDM B-tree implementation uses a node size of 32-items; however, only the items that are in-use will be stored on the transaction file server. RDM B-tree nodes are never updated; instead, a new node is created and the id index is updated to point to the location of the new node. The old node will be available for re-use in later transactions.