System for and method of efficient, expandable storage and retrieval of small datasets
First Claim
1. A data structure storing data in a computer memory, said data structure accessible by an application program being executed on a data processing system, said data structure including:
- a hierarchy of nodes including interior nodes and leaf nodes;
node pointers connecting said nodes from parent ones of said nodes to subsidiary ones of said nodes; and
a root pointer pointing to a top one of said nodes;
each of said nodes characterized as having a minimum size and consistent alignment, a subsidiary node type of each of said subsidiary nodes encoded in a number of bits of respective ones of said node pointers.
3 Assignments
0 Petitions
Accused Products
Abstract
An adaptive digital tree data structure supports scalability by encoding type bits within unused data bits of the root pointer word or, as the population increases to support it, into an additional word. In both instances the type bits included in the word or additional word contain dataset-global data which pertains to the underlying data structure. The information contained within the dataset-global data represents the total population of the tree or the amount of memory required to support the tree which may be used to determine the global memory efficiency of the data structure.
48 Citations
23 Claims
-
1. A data structure storing data in a computer memory, said data structure accessible by an application program being executed on a data processing system, said data structure including:
-
a hierarchy of nodes including interior nodes and leaf nodes;
node pointers connecting said nodes from parent ones of said nodes to subsidiary ones of said nodes; and
a root pointer pointing to a top one of said nodes;
each of said nodes characterized as having a minimum size and consistent alignment, a subsidiary node type of each of said subsidiary nodes encoded in a number of bits of respective ones of said node pointers. - View Dependent Claims (2, 3)
-
-
4. A data structure storing data in a computer memory, the data structure accessible by a computer program being executed on a data processing system including the memory, said data processing system supporting a simple pointer constituting a predetermined number of bits, said data structure comprising:
a root pointer including address information constituting a memory pointer and a data field configured to store information about a subsidiary object in said data structure addressed by said memory pointer;
said data field embedded in said root pointer such that said root pointer constitutes no more than said predetermined number of bits, said memory pointer constituting less than said predetermined number of bits.- View Dependent Claims (5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20)
-
18. A method of storing data in a data structure comprising the steps of:
-
storing a population of indexes directly under a root pointer;
encoding, in unused bits of said root pointer, a code indicating a configuration of said data structure wherein said indexes are stored directly under said root pointer;
converting said configuration of said data structure to include a top-level branch node;
modifying said code to indicate a reconfiguration of said data structure to a hierarchical configuration;
rearranging said population of indexes into said hierarchical configuration.
-
-
21. A method of storing data in a data structure comprising the steps of:
-
storing indexes in a hierarchical first data structure of a first structure type, said first data structure comprising branch nodes and leaf nodes under a first root pointer;
associating a value with each of said indexes;
using said value as a second root pointer to a second data structure subsidiary to said first data structure;
encoding a root pointer type of said second data structure in said second root pointer; and
identifying said root pointer type as corresponding to one of the same as and different from said first structure type. - View Dependent Claims (22, 23)
-
Specification