Scalable retrieval of data entries using an array index or a secondary key

Abstract

Example embodiments improve the lookup times and modification costs of indexing on a dynamically sorted list by using a combination of data structures to determine index values for secondary keys and vice versa. More specifically, exemplary embodiments provide a combination of a binary tree (e.g., a balanced binary tree) with a lookup table (e.g., linear dynamic hash table) to provide scalable retrieval of entries by either an array index or a secondary key. For example, given a key, a hash thereof returns a node placement within a balanced binary tree. This positioning can then be used at runtime to determine an index value for a data record, resulting in a near real-time lookup cost. Also note that modifications, such as reordering, insertions, and deletions, become a function of the nodes depth in the binary tree, rather than a linear function of number of records within the data array.