Patent ID: 7499927

Claim:
A computer-implemented method for performing key lookups, comprising: accessing a header of a given one of a plurality of nodes in a tree-based data index structure, the given node comprising the header and a plurality of partitions, each partition comprising at least one partition key, and the header of the given node comprising a plurality of header keys comprising at least one partition key from each of all but one partition of the plurality of partitions; choosing, using a search key, a chosen header key in the header; accessing a partition corresponding to the chosen header key; and selecting, using the search key, one of the at least one partition keys in the accessed partition, wherein the selected one of the at least one partition keys is used to access another of the plurality of nodes, wherein a partition key comprises information corresponding to a record; wherein the plurality of partitions comprises a predetermined number of positions, and the header further comprises a counter indicating how many of the predetermined number of positions are filled.