摘要 |
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. <IMAGE>
|