Data structure and storage and retrieval method supporting ordinality based searching and data retrieval

DETAILED DESCRIPTION The present invention is a data structure and related data storage and retrieval method that rapidly provides a count of elements stored or referenced by a hierarchical structure of ordered elements (e.
g.
, a tree), access to elements based on their ordinal value in the structure, and identification of the ordinality of elements.
In an ordered tree implementation of the invention, a count of elements stored in each subtree is stored, i.
e.
, the cardinality of each subtree is stored either at or associated with a higher level node pointing to that subtree or at or associated with the head node of the subtree.
In addition to data structure specific requirements (e.
g.
, creation of a new node, reassignment of pointers, balancing, etc.
) data insertion and deletion includes steps of updating affected counts.
Elements may be target data itself (e.
g.
, data samples, prime numbers); keys or indices associated with target data (e.
g.
, social security numbers of employees, product numbers and codes, etc.
used to reference associated data records, etc.
); or internal memory pointers to keys and/or data stored outside the data structure.
While the invention is applicable to varied hierarchical storage structures including, for example, binary trees, AVL trees (height-balanced binary trees), b-trees, etc.
(population based structures) and digital trees (i.
e.
, tries--expanse based structures), a preferred embodiment of the invention incorporates a hybrid tree structure as described and set forth in above referenced U.
S.
Patent Application.
According to an aspect of the invention, a computer memory is configured to store data for access by an application program being executed on a data processing system.
Stored in memory is a hierarchical data structure, the data structure storing an ordered set of keys.
The structure includes a root node and a plurality of first level data structures, a subset of the ordered set of keys uniquely associated with respective ones of the first level data structures