Computer data storage management system and methods of indexing a dataspace and searching a computer memory

• US 5,701,467 A
• Filed: 05/20/1996
• Issued: 12/23/1997
• Est. Priority Date: 07/07/1993
• Status: Expired due to Fees

• Current Assignee: International Computers Limited (Fujitsu Limited)
• Original Assignee: European Computer-Industry Research Centre GmbH
• Inventors: Freeston, Michael William
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Min, Donald
• Application Number:
  US08/583,072
• Time in Patent Office: 582 Days
• Field of Search: 395/611, 395/612, 395/601
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A computer data storage management system includes a memory employing a hierarchical data structure comprising a plurality of nodes (root, branch and leaf), in particular a multi-dimensional information database. The branch nodes are index nodes and the leaf nodes are data nodes. The index nodes are arranged in an index tree structure. When extra information inserted into the memory results in index node overflow, the index node is split and, in certain specified circumstances, an index entry will become disposed at an index tree level higher than the hierarchical level to which it corresponds, i.e. is promoted. Whilst this makes the index tree unbalanced, it facilitates the addition of information to and the searching of such a database.

Claims

1. A computer-implemented computer data storage management system including a memory employing a hierarchical data structure representing the recursive partitioning of a data space into contiguous or disjoint subspaces, and such that the external boundary of any subspace does not intersect the external or internal boundary of any other subspace at the same or any other level of recursive partitioning but may enclose, or partially coincide with, the external boundary of said other subspace;

the data structure hierarchy comprising a plurality of nodes including a root node, a plurality of branch nodes and a plurality of leaf nodes;

each node in the data structure hierarchy representing a subspace at respective or lower level in the corresponding recursive partition hierarchy;

the root node representing the entire data space;

each lower level node representing a subspace of the space represented by a respective parent node, or a subspace of the space represented by a descendant of the respective parent node, each lower level node comprising a child node;

the branch nodes in the hierarchical data structure being index nodes and the leaf nodes being data nodes;

each data node containing either a set of data entries or a set of pointers which reference data entries stored elsewhere;

each data entry containing a value or set of values which directly or indirectly specify the coordinates of a point representing that data entry in the data space;

each index node containing a set of index entries;

each index entry corresponding uniquely to one of the children of the index node which contains the index entry, each index entry being associated with;

(i) a respective pointer which refers to the logical address of the child node corresponding to the index entry, and

(ii) a value or set of values which directly or indirectly defines the external boundary of the subspace represented by the index entry;

characterised in that;

node promotion can occur as a result of node overflows due to the introduction of extra information into the memory;

an unpromoted node being a node which is at the same level in the data structure hierarchy as the level of the subspace which it represents in the corresponding recursive partition hierarchy, and a promoted node being a node which is at a higher level in the data structure hierarchy than the level of the subspace which it represents in the corresponding recursive partition hierarchy;

the subspace represented by any child node promoted to a respective node being a subspace of the union of all the subspaces represented by unpromoted children of the respective node;

in that the system includes first means which, upon the introduction of said extra information into the memory and resultant overflow of an index node, split the said index node into two resulting index nodes by partitioning the space which the said index node represents into two subspaces, said partitioning either being such that the number of index entries in the two resulting index nodes is as near equal as possible, or being in accordance with a predetermined criterion of balance in the distribution of the index entries between the two resulting index nodes;

the first means serving also to dispose the two resulting index nodes at the same level of the data structure hierarchy as the index node from which they were created, with each resulting index node having as parent the parent of the index node from which it was created,

in that the system includes second means which, if the external boundary of one of the two subspaces represented by the resulting index nodes is enclosed by the external boundary of the other of the two subspaces, and if no index entry in the said index node represents a subspace whose external boundary coincides with the said enclosed external boundary but there exists in the said index node an unpromoted or promoted index entry which represents a subspace whose external boundary directly encloses the said enclosed external boundary, promote said unpromoted or promoted index entry to the parent of the said index node;

the external boundary of a first subspace directly enclosing the external boundary of a second subspace if, at the same recursive partition level, there exists no third subspace whose external boundary is enclosed by the external boundary of the said first subspace and whose external boundary encloses the external boundary of the said second subspace;

in that the system includes third means which for each index node entry associate an indication of the level, in the hierarchy of recursive partitions of the dataspace, of the subspace represented by the entry;

and characterised in that the internal boundary of the subspace represented by an index entry is defined implicitly by the presence in the index of one or more other index entries which belong to the same or higher recursive partitioning level and each of which represents a subspace which the external boundary of the subspace represented by the said index entry directly encloses.

2. A computer implemented method for use in indexing a data space, the data space comprising a database for multi-dimensional information, the indexing having a hierarchical structure and the dataspace being recursively partitioned into subspaces with the corresponding index entry nodes arranged in an index tree, characterised in that the method comprises a plurality of steps including,

upon the introduction of extra information causing an index entry node to overflow, the step of splitting the said index entry node into two resulting index nodes by partitioning the space which the said index node represents into two subspaces, said partitioning either being such that the number of index entries in the two resulting index nodes is as near equal as possible, or being in accordance with a predetermined criterion of balance in the distribution of the index entries between the two resulting index nodes;

the step of disposing the two resulting index nodes at the same level of the index tree as the index node from which they were created, with each resulting index node having as parent the parent of the said index node from which it was created;

if the external boundary of one of the two subspaces represented by the resulting index nodes is enclosed by the external boundary of the other of the two subspaces, and if no index entry in the said index node represents a subspace whose external boundary coincides with the said enclosed external boundary but there exists in the said index node an unpromoted or promoted index entry which represents a subspace whose external boundary directly encloses the said enclosed external boundary, the step of promoting said unpromoted or promoted index entry to the parent of the said index node;

an unpromoted index entry being an index entry which is at the same level in the data structure hierarchy as the level of the subspace which it represents in the corresponding recursive partition hierarchy, and a promoted index entry being an index entry which is at a higher level in the data structure hierarchy than the level of the subspace which it represents in the corresponding recursive partition hierarchy, and the external boundary of a first subspace directly enclosing the external boundary of a second subspace if, at the same recursive partition level, there exists no third subspace whose external boundary is enclosed by the external boundary of said first subspace and whose external boundary encloses the external boundary of the second subspace, and

including the step of labelling each newly created index entry with the level of the subspace which it represents in the recursive partition hierarchy, whereby to facilitate the detection of index entries disposed at higher levels in the index tree than the level in the recursive partition hierarchy to which they correspond.

3. A computer-implemented method of searching a computer memory having a hierarchical data structure which represents the recursive partitioning of a data space of a plurality of dimensions into contiguous or disjoint subspaces, and which is such that the external boundary of any subspace does not intersect the external or internal boundary of any other subspace at the same or any other level of recursive partitioning but may enclose, or partially coincide with, the external boundary of such other subspace, the data structure hierarchy comprising a plurality of nodes including a root node, a plurality of branch nodes and a plurality of leaf nodes in a tree structure;

each node in the data structure hierarchy representing a subspace at a respective or lower level in the corresponding recursive partition hierarchy;

the root node representing the entire data space;

each lower level node representing a subspace of the space represented by a respective parent node, or a subspace of the space represented by a descendant of the respective parent node, each lower level node comprising a child node;

an unpromoted node being a node which is at the same level in the data structure hierarchy as the level of the subspace which it represents in the corresponding recursive partition hierarchy, and a promoted node being a node which is at a higher level in the data structure hierarchy than the level of the subspace which it represents in the recursive partition hierarchy, promotion occurring as a result of node overflows due to the introduction of extra information into the memory;

the subspace represented by any child node promoted to a respective node being a subspace of the union of all of the subspaces represented by unpromoted children of the respective node;

the branch nodes in the hierarchical data structure being index nodes and the leaf nodes being data nodes;

each data node containing either a set of data entries or a set of pointers which reference data entries stored elsewhere;

each data entry containing a value or set of values which directly or indirectly specify the coordinates of a point representing that data entry in the data space;

each index node containing a set of index entries;

wherein

(i) upon the introduction of said extra information into the memory and resultant overflow of an index entry node, the said index entry node is split into two resulting index nodes by partitioning the space which the said index node represents into two subspaces, said partitioning either being such that the number of index entries in the two resulting index nodes is as near equal as possible, or being in accordance with a predetermined criterion of balance in the distribution of the index entries between the two resulting index nodes;

the two resulting index nodes being disposed at the same level of the data structure hierarchy as the index node from which they were created, and each resulting index node having as parent the parent of the index node from which it was created, and

(ii) if the external boundary of one of the two subspaces represented by the resulting index nodes is enclosed by the external boundary of the other of the two subspaces, and if no index entry in the said index node represents a subspace whose external boundary coincides with the said enclosed external boundary but there exists in the said index node an unpromoted or promoted index entry which represents a subspace whose external boundary directly encloses the said enclosed external boundary,

then said unpromoted or promoted index entry is promoted to the parent of the said index node;

each index entry corresponding uniquely to one of the children of the index node which contains the index entry, each index entry being associated with;

(i) a respective pointer which refers to the logical address of the child node corresponding to the index entry;

(ii) an indication of the level, in the hierarchy of recursive partitions of the data space, of the subspace represented by the entry, and

(iii) a value or a set of values which directly or indirectly defines the external boundary of the subspace represented by the index entry;

and the internal boundary of the subspace represented by an index entry being defined implicitly by the presence in the index of one or more other index entries which belong to the same or higher recursive partitioning levels and each of which represents a subspace which the external boundary of the subspace represented by the said index entry directly encloses;

the external boundary of a first subspace directly enclosing the external boundary of a second subspace if, at the same recursive partition level, there exists no third subspace whose external boundary is enclosed by the external boundary of the said first subspace and whose external boundary encloses the external boundary of the said second subspace;

and the method comprising a plurality of steps for searching iteratively the recursive partition hierarchy for the smallest subspace which encloses a point in the data space, such point representing the sought item of information;

said search comprising the step of iteratively reconstituting the relevant nodes in the recursive partition hierarchy from the corresponding index hierarchy during the search;

starting at the root node of the index tree, the step of searching the unpromoted index entries in the index node for an unpromoted index entry which represents a subspace which directly encloses the point representing the sought item of information;

in the case of no such unpromoted index entry being found in the index node the search failing and terminating;

in the case of such an unpromoted index entry being found, the step of searching promoted index entries in the index node for those promoted index entries which respectively represent a subspace which directly encloses the point representing the sought item of information;

and the steps of copying each such promoted index entry directly enclosing the point representing the sought item of information, carrying it forward, demoting it by one level and including it for the purpose of the search only with the set of index entries in the next indexed node to be searched;

the next index node to be searched being that index node referenced by the pointer associated with the unpromoted index entry which represents a subspace which directly encloses the point representing the sought item of information;

the number of different index nodes visited along the search path for the item of information being sought being constant for a constant total number of items of information contained in the data space.