EP0650131A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Computer method and storage structure for storing and accessing multidimensional data
Assignee: Microsoft Corp
•
Filing: 1994-10-19
•
Granted: —
•
Expires: 2014-10-19
Abstract
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.
Inventors
- 👤 Allen Reiter
- 👤 Ian Charles Jose
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-30 10:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
90 words
A method in a computer system for storing a unit of data on a storage device, the method comprising the steps of: storing a first node entry having a first associated node identifier on the storage device as part of a tree data structure that indexes a group of data, the first node entry comprising a field for storing key values, a field for storing identifying information for subnodes, and a first data area for storing units of data; and storing the unit of data in the first data area.
Claim 2
Dependent Claim
50 words
The method recited in claim 1, further comprising the steps of: storing a second node entry on the storage device as part of the tree data structure; and storing identifying information for the second node entry in the field for storing identifying information for subnodes in the first node entry.
Claim 3
Dependent Claim
60 words
The method recited in claim 2 wherein the step of storing the second node entry on the storage device as part of the tree data structure further comprises the step of storing the second node entry, comprising only data and having no key values and no identifying information for subnodes, on the storage device as part of the tree structure.
Claim 4
Dependent Claim
68 words
The method recited in claim 2 wherein the step of storing the second node entry on the storage device as part of the tree data structure further comprises the step of storing the second node entry, comprising a field storing key values, a field storing identifying information for subnodes and a data area for storing units of data, on the storage device as part of the tree structure.
Claim 5
Dependent Claim
68 words
The method recited in claim 2, further comprising the step of storing a subtree of data in the tree structure on the storage device and said step of storing the second node entry further comprising the step of storing a pointer node as the second node entry in the storage device as part of the tree structure, said pointer node holding a pointer to the subtree of data.
Claim 6
Dependent Claim
111 words
The method of claim 1, further comprising the steps of: storing a parent node entry for the first node entry in the tree data structure, the parent node entry having a second node identifier associated with it and comprising a field for storing key values, a field for storing identifying information for subnodes, and a data area for storing units of data, the unit of data having a key value; storing the key value of the unit of data in the field for storing key values in the parent node entry; and storing the first node identifier in the field for storing identifying information for subnodes in the parent node entry.
Claim 7
Independent Claim
235 words
A method in a computer system for storing a unit of data 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 a group of data, the first node entry comprising a field for storing key values and a field for storage identifying information for subnodes, and a first data area for storing units of data; receiving a request to store the unit of data on the storage device; determining whether the unit of data can be stored in the first data area; when it is determined that the unit of data 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 unit of data 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 unit of data can be stored in the first data area, storing the unit of data in the first data area.
Claim 8
Independent Claim
243 words
A method in a computer system for storing a selected unit of data 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 units of data; based upon the key value of the unit of data, determining in which of the plurality of node entry groups the selected unit of data should be stored; based upon the size of the unit of data and the amount of available space in the determined node entry group, determining whether the selected unit of data 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 unit of data, 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 unit of data 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.
Claim 9
Dependent Claim
48 words
The method of claim 8 wherein the step of determining in which one of the node entries the selected unit of data should be stored includes the step of comparing the key value of the selected unit of data to the key values stored in each node entry.
Claim 10
Dependent Claim
70 words
The method of claim 8 wherein the determined node entry is contained within a fixed-size page having an amount of available space, wherein the selected unit of data has a size, and wherein the step of determining whether the selected unit of data can be stored in the determined node entry includes comparing the size of the selected unit of data to the amount of available space in the page.
Claim 11
Independent Claim
356 words
A method in a computer system for storing a selected data unit 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, the method comprising the steps of: assigning a key value to the selected data unit; based upon the assigned key value, determining in which node entry the selected data unit should be stored; determining whether the selected data unit can be stored in the block which contains the determined node entry; when the selected data unit can be stored in the block which contains the determined node entry, determining whether the selected data unit can be stored in the determined node entry; when the selected data unit can be stored in the determined node entry, storing the selected data unit in the determined node entry; when the selected data unit 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 unit 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 unit in the key value table of the determined node entry; and when the selected data unit 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 unit 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 unit in the key value table of the determined node entry.
Claim 12
Dependent Claim
101 words
A computer system for storing a unit of data on a storage device, the computer system comprising: a node storage mechanism for storing a node entry on the storage device as part of a tree data structure that indexes a group of data, the node entry having a first node identifier associated with it and comprising a first key value table for storing key values, a first subnode table for storing node identifiers of subnodes, and a first data area for storing units of data; and a data storage mechanism for storing the unit of data in the first data area.
Claim 13
Dependent Claim
108 words
The computer system of claim 12, the node entry having a parent node entry in the tree data structure, the parent node entry having a second node identifier associated with it and comprising a second key value table for storing key values, a second subnode table for storing node identifiers of subnodes, and a second data area for storing units of data, the unit of data having a key value, additionally comprising: a key storage mechanism for storing the key value of the unit of data in the second key value table; and a subnode storage mechanism for storing the first node identifier in the second subnode table.
Claim 14
Dependent Claim
188 words
The computer system of claim 13 additionally comprising: a mechanism for determining whether the unit of data can be stored in the first data area; when it is determined that the unit of data cannot be stored in the first data area, a node creator mechanism for 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, a second data storage mechanism for storing the unit of data in the new data area, a pointer node creator mechanism for creating a pointer node entry on the storage device, the pointer node entry having a pointer node identifier, a second node storage mechanism for storing the new node identifier in the pointer node entry, and a pointer node storage mechanism for storing the pointer node identifier in the first subnode table; and when it is determined that the unit of data can be stored in the first data area, a third data storage mechanism for storing the unit of data in the first data area.
Claim 15
Dependent Claim
256 words
A computer system for storing a selected unit of data on a storage device, the selected unit of data having an associated key value and a size, the storage device storing a plurality of node entry groups (pages), each node entry group (page) 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 units of data, comprising: means for determining in which of the plurality of node entry groups (pages) the selected unit of data should be stored based upon the key value of the unit of data; means for determining whether the selected unit of data can be stored in the determined node entry group (page) based upon the size of the unit of data and the amount of available space in the determined node entry group (page); means for creating a new node entry group (page) on the storage device when the amount of available space in the determined node entry group is smaller than the size of the unit of data, the new node entry group (page) 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 unit of data 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.
Claim 16
Dependent Claim
48 words
The computer system of claim 15 wherein the means for determining in which one of the node entries the selected unit of data should be stored includes means for comparing the key value of the selected unit of data to the key values stored in each node entry.
Claim 17
Dependent Claim
71 words
The computer system of claim 15 wherein the determined node entry is contained within a fixed-size page having an amount of available space, wherein the selected unit of data has a size, and wherein the means for determining whether the selected unit of data can be stored in the determined node entry includes comparing the size of the selected unit of data to the amount of available space in the page.
Claim 18
Dependent Claim
374 words
A computer system for storing a selected data unit 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 unit; means for determining in which node entry the selected data unit should be stored based upon the assigned key value; means for determining whether the selected data unit can be stored in the block which contains the determined node entry; means for determining whether the selected data unit can be stored in the determined node entry when the selected data unit can be stored in the block which contains the determined node entry; means for storing the selected data unit in the determined node entry when the selected data unit can be stored in the determined node entry,; when the selected data unit 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 unit 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 unit in the key value table of the determined node entry; and when the selected data unit 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 unit 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 unit in the key value table of the determined node entry.
References Cited (Backward Citations)
GB2196764A
Cited
EP0375307A2
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.