Computer method and storage structure for storing and accessing multidimensional data

• US 5,752,243 A
• Filed: 10/08/1996
• Issued: 05/12/1998
• Est. Priority Date: 10/20/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jose, Ian Charles, Reiter, Allen
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/727,131
• Time in Patent Office: 581 Days
• Field of Search: 395/603, 707/3, 707/101, 707/102, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer method and storage structure for storing and accessing multidimensional data is provided. A tree manager provided by the present invention stores data such as pointers, variable length data records, other B-trees, and directories, in a Multidimensional B-tree (MDB-tree). An MDB-tree has an imbedded "parent-child" structure which allows subtrees to be stored within nodes. The subtrees contain subnodes, which, in turn, may contain subtrees. The nodes are indexed by a primary key value while the subnodes in a subtree are indexed by secondary key values. Nodes of a MDB-tree contain a key value table, a subnode table, and a data area. When the tree manager attempts to store a unit of data on a page and the unit of data is too large for the page, the tree manager attempts to split a node currently stored on the page (or the unit of data being inserted) into a subnode and a subtree. The subtree is then stored on a new page. If the unit of data cannot be split into a subnode and a subtree, then one or more of the node currently stored on the page are moved to a new page.

Claims

1. A method in a computer system having hierarchically-related data objects for storing a data object on a storage device, the method comprising the steps of:

providing a first node entry having a first associated node identifier on the storage device as part of a tree data structure that indexes the hierarchically-related data objects, the first node entry comprising a table for storing key values and a table for storage identifying information for subnodes, and a first data area for storing at least one data object;

receiving a request to store the data object on the storage device;

determining whether the data object can be stored in the first data area;

when it is determined that the data object cannot be stored in the first data area,

creating a new node entry on the storage device, the new node entry having a new node identifier and comprising a new key value table, a new subnode table, and a new data area,

storing the data object in the new data area,

creating a pointer node entry on the storage device, the pointer node entry having a pointer node identifier,

storing the new node identifier in the pointer node entry, and

storing the pointer node identifier in the first subnode table; and

when it is determined that the data object can be stored in the first data area, storing the data object in the first data area.

2. A method in a computer system having hierarchically-related data objects for storing a data object having an associated key value and a size on a storage device, the method comprising the steps of:

storing a plurality of node entry groups on the storage device, each node entry group comprising one or more node entries and having an amount of available space, each node entry having a unique node identifier and comprising a key value table, a subnode table, and a data area for storing at least one data object;

based upon the key value of the data object, determining in which of the plurality of node entry groups the data object should be stored;

based upon the size of the data object and the amount of available space in the determined node entry group, determining whether the data object can be stored in the determined node entry group;

when the amount of available space in the determined node entry group is smaller than the size of the data object, creating a new node entry group on the storage device, the new node entry group containing a new node entry having a new node identifier and comprising a new key value table, a new subnode table, and a new data area;

storing the data object in the new data area; and

storing the new node identifier of the new node entry in the subnode table of the determined node entry.

3. The method of claim 2 wherein the step of determining in which one of the node entries the data object should be stored includes the step of comparing the key value of the data object to the key values stored in each node entry.

4. The method of claim 2 wherein the determined node entry is contained within a fixed-size page having an amount of available space, and wherein the step of determining whether the data object can be stored in the determined node entry includes comparing the size of the data object to the amount of available space in the page.

5. A method in a computer system having hierarchically-related data objects for storing a selected data object on a storage device logically divided into a plurality of fixed-size blocks, each block comprising a block header, an array of tags, and a plurality of node entries, each node entry comprising a key value table, a subnode table, and a data table, the method comprising the steps of:

assigning a key value to the selected data object;

based upon the assigned key value, determining in which node entry the selected data object should be stored;

determining whether the selected data object can be stored in the block which contains the determined node entry;

when the selected data object can be stored in the block which contains the determined node entry, determining whether the selected data object can be stored in the determined node entry;

when the selected data object can be stored in the determined node entry, storing the selected data object in the determined node entry;

when the selected data object cannot be stored in the determined node entry but can be stored in the block which contains the determined node entry,

creating a new node entry and storing the selected data object in the new node entry,

storing the node identifier of the new node entry in the subnode table of the determined node entry, and

storing the key value of the selected data object in the key value table of the determined node entry; and

when the selected data object cannot be stored in the determined node entry and cannot be stored in the block which contains the determined node entry,

requesting allocation of a new block,

creating a new node entry and storing the selected data object in the new node entry,

storing a pointer node in the block which contains the determined node entry and storing the node identifier of the new node entry in the pointer node,

storing the node identifier of the pointer node in the subnode table of the determined node entry, and

storing the key value of the selected data object in the key value table of the determined node entry.

6. A computer system having indexed data for storing a selected data object on a storage device, the selected data object having an associated key value and a size, the storage device storing a plurality of node entry groups, each node entry group comprising one or more node entries and having an amount of available space, each node entry having a unique node identifier and comprising a key value table, a subnode table, and a data area for storing at least one data object, comprising:

means for determining in which of the plurality of node entry groups the selected data object should be stored based upon the key value of the selected data object;

means for determining whether the selected data object can be stored in the determined node entry group based upon the size of the data object and the amount of available space in the determined node entry group;

means for creating a new node entry group on the storage device when the amount of available space in the determined node entry group is smaller than the size of the data object, the new node entry group containing a new node entry having a new node identifier and comprising a new key value table, a new subnode table, and a new data area;

means for storing the data object in the new data area; and

means for storing the new node identifier of the new node entry in the subnode table of the determined node entry.

7. The computer system of claim 6 wherein the means for determining in which one of the node entries the selected data object should be stored includes means for comparing the key value of the selected data object to the key values stored in each node entry.

8. The computer system of claim 6 wherein the each determined node entry is contained within a fixed-size page having an amount of available space and wherein the means for determining whether the selected data object can be stored in a determined node entry contained within a particular fixed-size page includes comparing the size of the selected data object to the amount of available space in the particular page.

9. A computer system having hierarchically-related data objects for storing a selected data object on a storage device, the storage device logically divided into a plurality of fixed-size blocks, each block comprising a block header, an array of tags, and a plurality of node entries, each node entry comprising a key value table, a subnode table, and a data table, comprising:

means for assigning a key value to the selected data object;

means for determining in which node entry the selected data object should be stored based upon the assigned key value and designating that node entry as the determined node entry;

means for determining whether the selected data object can be stored in the block which contains the determined node entry;

means for determining whether the selected data object can be stored in the determined node entry when the selected data object can be stored in the block which contains the determined node entry;

means for storing the selected data object in the determined node entry when the selected data object can be stored in the determined node entry;

when the selected data object cannot be stored in the determined node entry but can be stored in the block which contains the determined node entry,

means for creating a new node entry and storing the selected data object in the new node entry,

means for storing the node identifier of the new node entry in the subnode table of the determined node entry, and

means for storing the key value of the selected data object in the key value table of the determined node entry; and

when the selected data object cannot be stored in the determined node entry and cannot be stored in the block which contains the determined node entry,

means for requesting allocation of a new block,

means for creating a new node entry and storing the selected data object in the new node entry,

means for storing a pointer node in the block which contains the determined node entry and storing the node identifier of the new node entry in the pointer node,

means for storing the node identifier of the pointer node in the subnode table of the determined node entry, and

means for storing the key value of the selected data object in the key value table of the determined node entry.

10. A computer-readable storage device containing instructions for controlling a computer system having hierarchically-related data objects to perform a method for storing a data object on a storage device, the method comprising the steps of:

providing a first node entry having a first associated node identifier on the storage device as part of a tree data structure that indexes the hierarchically-related data objects, the first node entry comprising a table for storing key values and a table for storage identifying information for subnodes, and a first data area for storing at least one data object;

receiving a request to store the data object on the storage device;

determining whether the data object can be stored in the first data area;

when it is determined that the data object cannot be stored in the first data area,

creating a new node entry on the storage device, the new node entry having a new node identifier and comprising a new key value table, a new subnode table, and a new data area,

storing the data object in the new data area,

creating a pointer node entry on the storage device, the pointer node entry having a pointer node identifier,

storing the new node identifier in the pointer node entry, and

storing the pointer node identifier in the first subnode table; and

when it is determined that the data object can be stored in the first data area, storing the data object in the first data area.

11. A computer-readable storage device containing instructions for controlling a computer system having hierarchically-related data objects to perform a method for storing a data object having an associated key value and a size on a storage device, the method comprising the steps of:

storing a plurality of node entry groups on the storage device, each node entry group comprising one or more node entries and having an amount of available space, each node entry having a unique node identifier and comprising a key value table, a subnode table, and a data area for storing at least one data object;

based upon the key value of the data object, determining in which of the plurality of node entry groups the data object should be stored;

based upon the size of the data object and the amount of available space in the determined node entry group, determining whether the data object can be stored in the determined node entry group;

when the amount of available space in the determined node entry group is smaller than the size of the data object, creating a new node entry group on the storage device, the new node entry group containing a new node entry having a new node identifier and comprising a new key value table, a new subnode table, and a new data area;

storing the data object in the new data area; and

storing the new node identifier of the new node entry in the subnode table of the determined node entry.

12. A computer-readable storage device containing instructions for controlling a computer system having hierarchically-related data objects to perform a method for storing a selected data object on a storage device logically divided into a plurality of fixed-size blocks, each block comprising a block header, an array of tags, and a plurality of node entries, each node entry comprising a key value table, a subnode table, and a data table, the method comprising the steps of:

assigning a key value to the selected data object;

based upon the assigned key value, determining in which node entry the selected data object should be stored;

determining whether the selected data object can be stored in the block which contains the determined node entry;

when the selected data object can be stored in the block which contains the determined node entry, determining whether the selected data object can be stored in the determined node entry;

when the selected data object can be stored in the determined node entry, storing the selected data object in the determined node entry;

when the selected data object cannot be stored in the determined node entry but can be stored in the block which contains the determined node entry,

creating a new node entry and storing the selected data object in the new node entry,

storing the node identifier of the new node entry in the subnode table of the determined node entry, and

storing the key value of the selected data object in the key value table of the determined node entry; and

when the selected data object cannot be stored in the determined node entry and cannot be stored in the block which contains the determined node entry,

requesting allocation of a new block,

creating a new node entry and storing the selected data object in the new node entry,

storing a pointer node in the block which contains the determined node entry and storing the node identifier of the new node entry in the pointer node,

storing the node identifier of the pointer node in the subnode table of the determined node entry, and

storing the key value of the selected data object in the key value table of the determined node entry.

13. A method for storing data objects that are organized into a multi-level hierarchy of data objects, each data object having a key, each data object associated with data objects at the next lower-level in the hierarchy of data objects, the method comprising:

constructing a highest-level B-tree data structure that indexes the keys for the data objects of the highest level in the hierarchy of data objects, the highest-level B-tree data structure having leaf nodes that correspond to the data objects of the highest level in the hierarchy of data objects; and

for each successive lower level in the hierarchy of data objects,

constructing a lower-level B-tree data structure associated with each data object of the next-higher level in the hierarchy of data objects that indexes the keys for the data objects of the lower level in the hierarchy of data objects, the lower-level B-tree data structure having leaf nodes that correspond to data objects of the lower level

whereby each data object at each level in the hierarchy of data objects has an associated B-tree data structure that indexes the data objects of the next lower level in the hierarchy of data objects.

14. The method of claim 13 wherein the nodes of the B-tree data structures each contain three storage areas, including a storage area for storing pointers to lower-level nodes, a storage area for storing maximum key values corresponding to each lower-level node pointer, and a storage area for a data object.

15. The method of claim 14 wherein a data object is stored in the leaf node of the B-tree that indexes the key for that data object.

16. The method of claim 15 wherein a lower-level B-tree data structure is associated with a data object of the next-higher level in the hierarchy of data objects by a pointer to the lower-level B-tree data structure stored in the pointer storage area of the B-tree node that contains the data object.

17. A method for storing data objects organized into a multi-level hierarchy of data objects into the nodes of a data structure comprising a tree of B*-trees, each data object having a key, each data object associated with data objects at the next lower-level in the hierarchy of data objects, each node of the data structure having storage areas, including a storage area for storing pointers to lower-level nodes, a storage area for storing maximum key values corresponding to each lower-level node pointer, and a storage area for a data object, the method comprising:

constructing a highest-level B*-tree that indexes the keys for the data objects of the highest level in the hierarchy of data objects, the highest-level B*-tree having leaf nodes that contain the data objects of the highest level in the hierarchy of data objects; and

for each successive lower level in the hierarchy of data objects,

constructing a lower-level B*-tree associated with each data object of the next-higher level in the hierarchy of data objects, the lower-level B*-tree indexing the keys of the data objects of the lower level in the hierarchy of data objects, the lower-level B*-tree having leaf nodes that contain the data objects of the lower level in the hierarchy of data objects.

18. The method of claim 17 wherein a lower-level B*-tree is associated with a data object of the next-higher level in the hierarchy of data objects by a pointer to the lower-level B*-tree stored in the pointer storage area of the B*-tree node of that contains the data object.

19. The method of claim 18 wherein the nodes of the data structure are stored in pages of memory that are stored on and retrieved from a disk.

20. The method of claim 19 wherein, when a data object is to be added to a node that would cause that node to expand to a size that cannot be contained within a memory page,

when the data object can be split into sub-objects, the data object is split into sub-objects and stored in a sub-tree referenced by a pointer from the node, and

when the data object cannot be split into sub-objects, the node is split, and the split is propagated up to successively higher-level nodes of B*-tree that contains the node until addition of a pointer to a higher-level node does not cause the higher-level node to expand to a size that cannot be contained within a memory page.

21. A computer-readable storage device containing instructions for controlling a computer system to store data objects that are organized into a multi-level hierarchy of data objects, each data object having a key, each data object associated with data objects at the next lower-level in the hierarchy of data objects;

the method comprising;

constructing a highest-level B-tree data structure that indexes the keys for the data objects of the highest level in the hierarchy of data objects, the highest-level B-tree data structure having leaf nodes that correspond to the data objects of the highest level in the hierarchy of data objects; and

for each successive lower level in the hierarchy of data objects,

constructing a lower-level B-tree data structure associated with each data object of the next-higher level in the hierarchy of data objects that indexes the keys for the data objects of the lower level in the hierarchy of data objects, the lower-level B-tree data structure having leaf nodes that correspond to data objects of the lower level.

22. The computer-readable storage device of claim 21 further containing instructions to specify that the nodes of the B-tree data structures each contain three storage areas, including a storage area for storing pointers to lower-level nodes, a storage area for storing maximum key values corresponding to each lower-level node pointer, and a storage area for a data object.

23. The computer-readable storage device of claim 22 further containing instructions to store each data object in the leaf node of the B-tree that indexes the key for that data object.

24. The computer-readable storage device of claim 23 further containing instructions to associate a lower-level B-tree data structure with a data object of the next-higher level in the hierarchy of data objects by storing a pointer to the lower-level B-tree data structure in the pointer storage area of the B-tree node that contains the data object.