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.

An indexing method in which the values of the columns used in the index are efficiently maintained in sorted order that also provides fast access (three or four additional disk accesses) to an individual index entry.