A computer-implemented method is provided for performing key lookups. The method comprises accessing a header of a given one of a plurality of nodes in a tree-based data index structure. The given node comprises the header and a plurality of partitions. Each partition comprises at least one key. The header of the given node comprises a selected key from each of a selected plurality of the partitions. The method also comprises choosing, using a search key, a selected key in the header. The method further comprises accessing a partition corresponding to the chosen selected key and selecting, using the search key, one of the at least one keys in the accessed partition. The selected one of the at least one keys can be used to access another of the plurality of nodes. Yet additional methods, apparatus, and program products are disclosed.
