Data processing: database and file management or data structures – Database design – Data structure types
Patent
1996-10-08
1998-05-12
Black, Thomas G.
Data processing: database and file management or data structures
Database design
Data structure types
707101, 707200, G06F 1730
Patent
active
057522430
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.
REFERENCES:
patent: 4344134 (1982-08-01), Barnes
patent: 4606002 (1986-08-01), Waisman et al.
patent: 4841435 (1989-06-01), Papenberg
patent: 5408652 (1995-04-01), Hayashi et al.
patent: 5446887 (1995-08-01), Berkowitz
patent: 5546571 (1996-08-01), Shan et al.
patent: 5560007 (1996-09-01), Thai
patent: 5613105 (1997-03-01), Zbikowski et al.
Nakamura et al., "MD-tree: A Balanced Hierarchical Data Structure for Multi-dimensional Data with Highly Efficient Dynamic Characteristics," IEEE 9th International Conference on Pattern Recognition 1(17):375-378, 1988.
Gerard Salton, "Multiway Search Trees," Automatic Text Processing, Chapter 7.6, pp. 183-189, Dec., 1988.
Gerard Salton, "Multidimensional Access Structures," Automatic Text Processing, Chapter 7.10, pp. 216-225, Dec., 1988.
K. Culik et al., "Dense Multiway Trees," ACM Transactions on Database Systems, vol. 6, 1981, pp. 486-512, Sep., 1981.
Douglas Comer, "The Ubiquitous B-Tree," Computing Surveys, vol. 11, Jun. 1979, pp. 121-137
Cormen et al., "B-Trees," Introduction to Algorithms, Chapter 19, pp. 381-399, Jun. 1991.
"How to become a high-performance expert: here's a look at Rdb's high-performance features", DBMS, v4, n4, ps9(6) Apr. 1991.
Data Structure for Multi-Layer N-Dimesional Data Using Hierarchical Structure, Nakamura et al., May 1990, IEEE.
Microsoft Press Computer Dictionary, Second Edition, Jan. 1993, p. 208.
Jose Ian Charles
Reiter Allen
Alam Hosain T.
Black Thomas G.
Microsoft Corporation
LandOfFree
Computer method and storage structure for storing and accessing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer method and storage structure for storing and accessing , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer method and storage structure for storing and accessing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-996552