Techniques for improving memory access patterns in tree-based data index structures

An apparatus for performing key lookups, the apparatus comprising:

• a cache;
• at least one main memory coupled to the cache and comprising a tree-based data index structure comprising a plurality of interconnected nodes, a given one of the plurality of nodes comprising a header and a plurality of partitions, each partition comprising at least one key, the header of the given node comprising a selected key from each of a selected plurality of the partitions;
• and
• at least one processor coupled to the at least one main memory and to the cache, the at least one processor configured to perform:
• choosing, using a search key, a selected key in the header;
• 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,
• wherein the selected one of the at least one keys can be used to access another of the plurality of nodes.

A program storage device tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform operations for performing key lookups, the operations 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 key, the header of the given node comprising a selected key from each of a selected plurality of the partitions;
• choosing, using a search key, a selected key in the header;
• 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,
• wherein the selected one of the at least one keys can be used to access another of the plurality of nodes.