Method and system for facilitating processing of statistical inquires on stored data accessible through a data access structure

Claim 2

A data processing system for maintaining a data access structure which facilitates the processing of statistical queries relating to records stored in the structure, each of the records including a search key and record data, the system comprising: a data storage medium; means for maintaining, in the data storage medium, a plurality of data nodes, each storing a subset of the records, and a plurality of access nodes as a B-tree including a series of successive levels, the levels including a first level including a root access node and a last level including the data nodes, each one of the access nodes being linked to at least one other of the access nodes or to at least one of the data nodes, each of the access nodes which is not linked directly to any of the data nodes being indirectly linked through one or more intermediate ones of the access nodes to at least one of the data nodes; means for maintaining statistical information linked to at least a selected one of the access nodes, the statistical information being related collectively to the record data of the records stored in one or more of those of the data nodes which are linked directly or indirectly to the selected access node; and means, responsive to changes in the records, for updating the statistical information.

Claim 3

The system of claim 1, wherein: the means for maintaining the data nodes and access nodes include means for maintaining the access nodes and data nodes on a plurality of levels i, i going from 0 to n, n being greater than 1, level 0 including the root access node with pointers to nodes in level 1, and access nodes in level i having pointers to those of the access nodes and/or data nodes in level i+1, for i equal to 1 through n-1, and level n including data and the means responsive to changes in the records for updating the statistical information is operable, responsive to a change in a record stored at one of the data nodes linked directly or indirectly to the selected access node on level i that results in a change exceeding a threshold in the statistical information of the selected access node, for recomputing the statistical information of the selected access node.

Claim 4

The system of claim 1, wherein: the means for maintaining the data nodes includes means for maintaining, for each of the data nodes, a storage location for storing the statistical information; and the means for maintaining the access nodes includes means for maintaining a pointer in the selected access node which points to the storage location.

Claim 5

The system of claim 1, further including means for maintaining second statistical information linked to one of the access nodes, which is a child node of the selected access node concerning the records stored in those of the data nodes which are linked directly or indirectly to the child node, said child node being linked directly to the selected access node; and wherein said means for recomputing the statistical information of the selected access node includes: means for promoting the statistical information linked to the child node for combination with the statistical information of the selected access node; means for storing a last promoted version of the statistical information linked to the child node; and means for comparing the last promoted version of the statistical information linked to the child node with a recomputed version of the statistical information linked to the child node to determine whether the threshold is exceeded.

Claim 6

A data processing system for maintaining a data access structure which facilitates the processing of statistical queries relating to records stored in the structure, each of the records including a search key and record data, the system comprising: a data storage medium; means for maintaining, in the data storage medium, a plurality of data nodes, each storing a subset of the records, and a plurality of access nodes as a B-tree including a series of successive levels, the levels including a first level including a root access node and a last level including the data nodes, each one of the access nodes being linked to at least one other of the access nodes or to at least one of the data nodes, each one of the access nodes which is not linked directly to any of the data nodes being indirectly linked through one or more intermediate ones of the access nodes to at least one of the data nodes; means for maintaining statistical information stored in at least a selected one of the access nodes related collectively to the recorded stored in one or more of those of the data nodes which are linked directly or indirectly to the selected access nodes; and means, responsive to changes in the records, for updating the statistical information.

Claim 7

A data processing system for maintaining a data access structure which facilitates the processing of statistical queries relating to records stored in the structure, each of the records including a search key and record data, the system comprising: a data storage medium; means for maintaining, in the data storage medium, a plurality of data nodes, each storing a subset of the records, and a plurality of access nodes as a B-tree including a series of successive levels, the levels including a first level including a root access node and a last level including the data nodes, each one of the access nodes being linked to at least one other of the access nodes or to at least one of the data nodes, each one of the access nodes which is not linked directly to any of the data nodes being indirectly linked through one or more intermediate ones of the access nodes to at least one of the data nodes; means for maintaining statistical information stored in at least a selected one of the access nodes related collectively to the recorded stored in one or more of those of the data nodes which are linked directly or indirectly to the selected access nodes; and means, responsive to changes in the records, for updating the statistical information.

Claim 8

The system of claim 5, further including means for maintaining second statistical information stored in one of the access nodes, which is a child node of the selected access node, concerning the records stored those of the data nodes which are linked directly or indirectly to the child node, said child node being linked directly to the selected access node; and wherein said means for updating the statistical information includes: means for promoting the statistical information stored in the child node for combination with the statistical information of the selected access node; means for storing a last promoted version of the statistical stored in the child node; and means for comparing the last promoted version of the statistical information linked to the child node with a recomputed version of the statistical information stored in the child node to determine whether the threshold is exceeded.

Claim 9

The system of claim 5, wherein: the means for maintaining the data nodes and access nodes include means for maintaining the access node and data nodes on a plurality of levels i, i going from 0 to n, n being greater than 1, level 0 including the root access node with pointers to nodes in level 1, and access nodes in level i having pointers to those of the access nodes and/or data nodes in level i+1, for i equal to 1 through n-1, and level n including data nodes; and the means responsive to changes in the records for updating the statistical information is operable, responsive to a change in a record stored at one of the data nodes linked directly or indirectly to the selected access node no level i that results in a change exceeding a threshold in the statistical information of the selected access node, for recomputing the statistical information of the selected access node.

Claim 10

A computer implemented method, for use with a data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the method comprising the steps of: maintaining, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, updating the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 11

A computer implemented method, for use with a data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the method comprising the steps of: maintaining, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, updating the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 12

A method as recited in claim 8, wherein the step of updating includes: determining whether the change in the data record engenders a change in the statistical information which exceeds a predetermined threshold; and updating the respective pieces of statistical information responsive to a determination, in the step of determining, that the change in the statistical information does exceed the predetermined threshold.

Claim 13

A method as recited in claim 9, wherein the step of updating includes: promoting statistical information of one of the first plurality of access nodes to the corresponding access node of the second plurality for combination with the statistical information of the corresponding access node of the second plurality; storing a last promoted version of the statistical information from the access node of the first plurality; and comparing the last promoted version of the statistical information with a recomputed version of the statistical information to determine whether the threshold is exceeded.

Claim 14

A method as recited in claim 8, wherein the step of maintaining includes maintaining the first and second nodes in the form of a B-tree.

Claim 15

A method as recited in claim 8, wherein the step of maintaining includes: storing each respective piece of statistical information in a predetermined storage location; and maintaining a respective pointer in each respective one of the second nodes which points to the predetermined storage location.

Claim 16

A data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the system comprising: means for maintaining, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, means, operable responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, for updating the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 17

A data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the system comprising: means for maintaining, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, means, operable responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, for updating the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 18

A system as recited in claim 13, wherein the means for updating includes: means for determining whether the change in the data record engenders a change in the statistical information which exceeds a predetermined threshold; and means for updating the respective pieces of statistical information responsive to a determination, by the means for determining, that the change in the statistical information does exceed the predetermined threshold.

Claim 19

A system as recited in claim 14, wherein the means for updating includes: means for promoting statistical information of one of the first plurality of access nodes to the corresponding access node of the second plurality for combination with the statistical information of the corresponding access node of the second plurality; means for storing a last promoted version of the statistical information from the access node of the first plurality; and means for comparing the last promoted version of the statistical information with a recomputed version of the statistical information to determine whether the threshold is exceeded.

Claim 20

A system as recited in claim 13, wherein the means for maintaining includes means for maintaining the first and second nodes in the form of a B-tree.

Claim 21

A system as recited in claim 13, wherein the means for maintaining includes: means for storing each respective piece of statistical information in a predetermined storage location; and means for maintaining a respective pointer in each respective one of the second nodes which points to the predetermined storage location.

Claim 22

A computer program product, for use with a data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the data processing and storage system to maintain, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, means, recorded on the recording medium, for directing the data processing and storage system, responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, to update the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 23

A computer program product, for use with a data processing and storage system, for facilitating inquiries relating to data records stored in nodes of an hierarchical data structure having a plurality of successive layers of nodes, each of the data records including a search key and record data, the nodes including (a) first nodes, each one of the first nodes including linking information for linking to a node in a next previous one of the layers, and (b) second nodes, each one of the second nodes including linking information for linking to at least one of (i) a node in a next previous one of the layers, and (ii) at least one node in a next successive one of the layers, each respective one of the second nodes at a given layer thereby being linked, directly or indirectly, with a respective set of nodes in at least one of the layers successive to the given layer, the data records being stored in various ones of the respective set of nodes, and making up a respective set of data records corresponding with the respective second node, the computer program product comprising: a recording medium; means, recorded on the recording medium, for directing the data processing and storage system to maintain, in respective ones of the second nodes, respective pieces of statistical information related collectively to the record data of the data records making up the respective sets of data records; and, means, recorded on the recording medium, for directing the data processing and storage system, responsive to a change in a given one of the stored data records, the given data record being stored in a given one of the nodes, to update the respective pieces of statistical information maintained in each one of the second nodes for which the given node belongs in the respective set of nodes.

Claim 24

A computer program product as recited in claim 18, wherein the means for directing to update includes: means, recorded on the recording medium, for directing the data processing and storage system to determine whether the change in the data record engenders a change in the statistical information which exceeds a predetermined threshold; and means, recorded on the recording medium, for directing the data processing and storage system to update the respective pieces of statistical information responsive to a determination, by the means for determining, that the change in the statistical information does exceed the predetermined threshold.

Claim 25

A computer program product as recited in claim 19, wherein the means for directing to update includes: means, recorded on the recording medium, for directing the data processing and storage system to promote statistical information of one of the first plurality of access nodes to the corresponding access node of the second plurality for combination with the statistical information of the corresponding access node of the second plurality; means, recorded on the recording medium, for directing the data processing and storage system to store a last promoted version of the statistical information from the access node of the first plurality; and means, recorded on the recording medium, for directing the data processing and storage system to compare the last promoted version of the statistical information with a recomputed version of the statistical information to determine whether the threshold is exceeded.

Claim 26

A computer program product as recited in claim 18, wherein the means for directing to maintain includes means, recorded on the recording medium, for directing the data processing and storage system to maintain the first and second nodes in the form of a B-tree.

Claim 27

A computer program product as recited in claim 18, wherein the means for directing to maintain includes: means, recorded on the recording medium, for directing the data processing and storage system to store each respective piece of statistical information in a predetermined storage location; and means, recorded on the recording medium, for directing the data processing and storage system to maintain a respective pointer in each respective one of the second nodes which points to the predetermined storage location.