Cache-friendly b-tree accelerator

A computer-readable storage medium comprising computer program instructions for accessing a specified data record in a B-tree, the B-tree 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, the program instructions executable by a processor to perform actions including:

• a) creating a hash table with a plurality of entries, each entry including an aux key value, an aux page identifier that points to a corresponding B-tree leaf node, and an aux slot identifier that points to a corresponding slot in the corresponding B-tree leaf node;
• b) receiving a search key;
• c) searching the hash table for an entry with an aux key value that matches the search key;
• d) if the entry is found, performing additional actions including:
• i) determining whether a corresponding page identifier is trusted;
• ii) if the corresponding aux page identifier is trusted, using the corresponding aux page identifier and a corresponding aux slot identifier to retrieve a data record corresponding to the search key from the B-tree;
• and
• iii) if the corresponding aux page identifier is not trusted, performing a search of the B-tree to retrieve the data record corresponding to the search key and updating the entry.

A computer-based system for accessing data records of a B-tree, the B-tree having a plurality of nodes, including internal nodes and leaf nodes, each leaf node including one or more keys, each key having a corresponding data record, the system comprising:

• a) an auxiliary index that includes a plurality of entries, each entry having a corresponding aux key value and a corresponding aux node pointer that points to a corresponding internal node or a leaf node of the B-tree;
• b) an auxiliary index manager comprising computer program instructions for searching the auxiliary index for an entry having a corresponding aux key value matching a search key;
• c) trust determination means for determining whether the entry having the corresponding aux key value is trusted;
• d) means for, if the entry is trusted, retrieving a data record corresponding to the search key;
• e) means for, if the entry is not trusted, retrieving the data record corresponding to the search key;
• and
• f) means for selectively performing searches of the B-tree after modifying the auxiliary index to reduce an amount of cache or an amount of main memory used by the auxiliary index.