System for and method of efficient, expandable storage and retrieval of small datasets

• US 6,785,687 B2
• Filed: 06/04/2001
• Issued: 08/31/2004
• Est. Priority Date: 06/04/2001
• Status: Expired due to Fees

• Current Assignee: HTC Corporation
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Baskins, Douglas L., Silverstein, Alan
• Primary Examiner(s): Rones, Charles
• Application Number:
  US09/874,654
• Publication Number:
  US 20020194184A1
• Time in Patent Office: 1,184 Days
• Field of Search: 707/1, 707/3, 707/4, 707/5, 707/6, 707/100, 707/101, 707/102, 707/201, 341/50, 341/51, 364/251.6, 364/282.6, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. 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; and

rearranging said population of indexes into said hierarchical configuration.

2. The method of claim 1 further comprising a step of inserting an information node between said root pointer and said top branch.

3. The method of claim 1 further comprising a step of detecting via said code an invalid pointer passed by a calling application.

4. 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.

5. The method according to claim 4 further comprising the steps of:

dividing a variable-size index into a plurality of fixed-size indexes;

inserting a first of said fixed-size indexes into said first data structure; and

inserting a second of said fixed-size indexes into said second data structure.

6. The method according to claim 5 further comprising the steps of:

inserting a last of said plurality of fixed-size indexes into a terminal data structure of a second data structure type; and

setting in said value corresponding with said last fixed-size index said root pointer of said root pointer type corresponding to said second data structure type.

7. 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;

a root pointer pointing to a top one of said nodes; and

wherein each of said nodes characterized as having a minimum size and consistent alignment, and a subsidiary node type of each of said subsidiary nodes encoded in a number of bits of respective ones of said node pointers.

8. The data structure according to claim 7 wherein said subsidiary node type indicates that said subsidiary node contains subtree information describing data stored in ones of said nodes subsidiary to, and forming a subtree of, said subsidiary node.

9. The data structure according to claim 7 wherein said number of bits comprises a number of least significant bits of said node pointers.

10. 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.

11. The data structure according claim 10 further comprising a bitmask configured to convert said memory pointer into said simple pointer.

12. The data structure according to claim 10 wherein said data structure is configured in a first configuration to store a relatively small number of indexes, said data structure in said first configuration comprising a root-level leaf node wherein said root pointer is configured to identify a type of said root-level leaf node.

13. The data structure according to claim 12 wherein said root pointer identifies a number of keys stored in said root-level leaf node.

14. The data structure according to claim 12 wherein said root-level leaf node is directly accessible without calling a subroutine.

15. The data structure according to claim 10 wherein said data structure is arranged in a hierarchy of interior branch nodes and terminal leaf nodes, said root pointer configured to point to an interior information node containing information about and a pointer to a first subsidiary one of said branch and leaf nodes.

16. The data structure according to claim 15 wherein said interior information node is configured to store at least one of an amount of memory used by the data structure, and a total population of the data structure.

17. The data structure according to claim 10 wherein said data field indicates a type of the data structure to which said memory pointer points.

18. The data structure according to claim 17 wherein said type includes an indication that said memory pointer is a null pointer and there is no associated data structure.

19. The data structure according to claim 17 wherein said type includes an indication that said memory pointer points to said data structure containing a sufficiently low population of indexes that said data structure includes less than a predetermined number of levels.

20. The data structure according to claim 19 wherein said data field further includes an indication of a population count of indexes stored in said data structure.

21. The data structure according to claim 17 wherein said type indicates that said memory pointer points to said data structure containing at least a threshold number of indexes such that said data structure is configured to amortize memory needed for global data useful in the management of said data structure, said memory needed amortized over a minimum number of indexes represented by said threshold value.

22. The data structure according to claim 21 wherein said memory pointer points to a first node of a hierarchical data structure wherein said first node contains information about a remainder of said hierarchical data structure.

23. The data structure according to claim 10 wherein said data field resides in the least significant bits of said root pointer, said least significant bits that would otherwise have a fixed value for a consistently aligned object of any minimum size.