Patent
1996-05-20
1997-12-23
Black, Thomas G.
395601, 395612, G06F 1730
Patent
active
057014671
DESCRIPTION:
BRIEF SUMMARY
TECHNICAL FIELD
This invention relates to database structures and in particular to hierarchical index structures for use therein, methods for use in indexing a dataspace and methods of searching database structures. The invention also relates to the electronic storage of an n-dimensional entity in the form of an n-dimensional data space in a one-dimensional memory of a computer, and/or the transfer and/retrieval of said n-dimensional entity to or from the memory of the computer.
BACKGROUND ART
Spatial information can be stored in the memory of a computer. Spatial information consists essentially of points in an n-dimensional data space. For example, the points may be coordinates of the centres of objects on a map, in two dimensions, or the locations of aircraft in three-dimensional air-space. Associated with this positional information may be additional information describing the object at the location--such as the type of a map object, or the call-sign and velocity of an aircraft.
Classically, data structures in database systems have been restricted to fixed-structure records or tuples. The structure of a tuple is a set of fields, or attributes. The types of the attributes have been restricted to a few simple types, such as real, integer, and string.
In order to build an index to a set of records, it is assumed that all the members of the set have the same structure. A key value must be associated with each. This value may or may not be unique to the record. In principle, it may be the direct value of a single attribute, or of several attributes, or it may be generated by some conversion operation on one or more attributes. The unit of memory allocation for the data and the index, in main memory or secondary storage, is a page, and this page is almost invariably of fixed size.
The invention is concerned with a hierarchical index, which takes the form of a tree structure. In general, a tree structure is composed of a root node, branch nodes and leaf nodes. By convention, the tree is represented in inverted form i.e. with the root at the top. A traversal path through the tree is defined by the sequence of nodes encountered along the path. The height of the tree is the length of the longest direct path traversed from root to leaf. The fan-out ratio is the number of branches leading from a node in the direction of the leaves. This ratio usually has a range of allowed values, depending on the details of the design and implementation. The limits of this range are the same for all the index nodes.
The best known and most widely used hierarchical structure for dynamically indexing a set of records in a database is the B-tree. The B-tree takes the value of a single attribute in a record, or the lexical concatenation of several attributes, as the index key. Each index node corresponds to a page of memory, and contains an ordered set of index keys. The index is constructed as a hierarchy of index keys: at any particular level of the tree, each node contains an ordered set of key values and, associated with each key, a pointer to a node at the index level below. Each key represents an upper (or lower) bound to the key values stored in the node to which it points. At the lowest index level, the keys point to data pages containing records within the ranges defined by the lowest level index keys.
When the insertion of an additional record causes a data page to overflow: attribute(s). pointer for the new page, is inserted in the index leaf node which holds for the extreme upper or lower range partition!.
If an insertion in an index node causes it to overflow, then the index node is similarly split about its median key value, a copy of which is posted upwards, together with a pointer to the newly created index page.
In the worst case, a single insertion of a data record can trigger a chain of overflows and insertions up to and including the root of the index tree. When the root splits, a new root is generated and the height of the index tree increases by one. In this way a tree-structured index grows upwards (i.e. an
REFERENCES:
patent: 5119490 (1992-06-01), Kurose
patent: 5247666 (1993-09-01), Buckwold
patent: 5307486 (1994-04-01), Nakamigawa
Black Thomas G.
European Computer-Industry Research Centre GmbH
Min Donald
LandOfFree
Computer data storage management system and methods of indexing 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 data storage management system and methods of indexing , we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer data storage management system and methods of indexing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1808049