A system and method for accelerating searches of B-trees. An auxiliary index that is optimized for use with a cache is used in conjunction with a B-tree. A hash type of auxiliary index maintains pointers to key entries in the B-tree leaf nodes. The hash type of index may be searched, and a resulting pointer is used to locate records of the B-tree, bypassing a search of the B-tree. A top level type of auxiliary index maintains pointers to leaf nodes or internal nodes of the B-tree. A top level index may be searched, and a search of the B-tree is performed beginning with the node found by using the top level index. A monitoring mechanism may automatically start, change, or discard the auxiliary index based on an amount of cache memory, types of searches, or other factors. The auxiliary index may be optimized for high performance in read only searches, while the B-tree provides transaction durability.