Patent ID: 8180763

Claim:
In a data storage and retrieval system including a B-tree (BT) having a plurality of nodes, including internal nodes and leaf nodes, each leaf node including one or more BT keys, each BT key having a corresponding data record, a computer-based method of accessing data records comprising: a) creating an auxiliary index including a plurality of aux key values, each aux key value having a corresponding aux page identifier that points to a corresponding B-tree node; b) receiving a search key; c) employing the search key to search the auxiliary index to locate a matching aux key value and a corresponding aux page identifier; d) in response to finding the aux key value, determining whether the aux page identifier is trusted; e) if the aux page identifier is trusted, using the aux page identifier to retrieve a data record corresponding to the search key; and f) if the aux page identifier is not trusted, performing a search of the B-tree to retrieve the data record corresponding to the search key; wherein the B-tree is a tree data structure that maintains data in a sorted order; and wherein the method is performed by a computer processor.