SYSTEM AND METHOD OF PROVIDING A CACHE-EFFICIENT, HYBRID, COMPRESSED DIGITAL TREE WITH WIDE DYNAMIC RANGES AND SIMPLE INTERFACE REQUIRING NO CONFIGURATION OR TUNING

An adaptive digital tree data structure incorporates a rich pointer object, the rich pointer including both conventional address redirection information used to traverse the structure and supplementary information used to optimize tree traversal, skip levels, detect errors, and store state information. The structure of the pointer is flexible so that, instead of storing pointer information, data may be stored in the structure of the pointer itself and thereby referenced without requiring further redirection. The digital tree data structure is self-modifying based on a digital tree (or “trie”) data structure which is stored in the memory, can be treated as a dynamic array, and is accessed through a root pointer. For an empty tree, this root pointer is null, otherwise it points to the first of a hierarchy of branch nodes of the digital tree. Low-fanout branches are avoided or replaced with alternative structures that are less wasteful of memory while retaining most or all of the performance advantages of a conventional digital tree structure, including index insertion, search, access and deletion performance. This improvement reduces or eliminates memory otherwise wasted on null pointers prevalent in sparsely populated and/or unbalanced, wide/shallow digital trees. Additional processing time required to effectuate and accommodate the branch modification is minimal, particularly in comparison to processing advantages inherent in reducing the size of the structure so that data fetching from memory is more efficient, capturing more data and fewer null pointers.