1. A computer program product for increasing efficiency of random lookups in an index for a database, the index stored in an original tree structure stored in a first memory, the original tree structure comprising a plurality of levels, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising: calculating an actual expense comprising a first time of traversal by the processor of the original tree structure stored in the first memory; for a n number of top levels of the original tree structure, and assuming a candidate alternate tree structure stored in a second memory comprising the n number of top levels of the original tree structure: calculating an estimated expense comprising a second time of traversal by the processor of the candidate alternate tree structure stored in the second memory and remaining levels of the original tree structure stored in the first memory; calculating a performance improvement comprising a difference between the actual expense and the estimated expense; calculating a memory expense comprising an amount of the second memory used by the candidate alternate tree structure; and calculating a ratio of the performance improvement and the memory expense; repeating the calculating of the estimated expense, the performance improvement, the memory expense, and the ratio for a plurality of n numbers of the top levels of the original tree structure; selecting a given m number of top levels of the original tree structure to be stored in an alternate tree structure based on the ratios of the plurality of n numbers of the top levels of the original tree structure; creating the alternate tree structure comprising the selected given m number of top levels of the original tree structure and storing the alternate tree structure in the second memory; and searching the index by traversing the alternate tree structure stored in the second memory and the remaining levels of the original tree structure stored in the first memory.