Concurrency and recovery for index trees with nodal updates using multiple atomic actions by which the trees integrity is preserved during undesired system interruptions

• US 5,276,872 A
• Filed: 06/25/1991
• Issued: 01/04/1994
• Est. Priority Date: 06/25/1991
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Salzberg, Betty J., Lomet, David B.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Harper, Burch
• Application Number:
  US07/720,405
• Time in Patent Office: 924 Days
• Field of Search: 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention includes an approach to index tree structure changes which provides high concurrency while being usable with many recovery schemes and with many varieties of index trees. The present invention permits multiple concurrent structure changes. In addition, all update activity and structure change activity above the data level executes in short independent atomic actions which do not impede normal database activity. Only data node splitting executes in the context of a database transaction. This feature makes the approach usable with diverse recovery mechanisms, while only impacting concurrency in a modest way. Even this impact can be avoided by re-packaging the atomic actions, at the cost of requiring more from the recovery system.

Claims

1. For use in a computer system which allows a plurality of processing elements to access a memory concurrently during a normal operating mode, a method of maintaining a nodal tree arrangement which is a data structure for finding data records based on key values stored with the records, comprising the steps of:

establishing a multitude of data records, each of said data records having an associated node and said nodes being linked in the nodal tree arrangement to other of the nodes by at least one of the following types of linking relationships;

parental, child and sibling;

during the normal operating mode, using a plurality of atomic actions to reconfigure the nodal tree arrangement so as to replace, delete or add a data record;

each atomic action including executing a set of steps having an end marker indicating that the set of steps has been completed, said set of steps executed without apparent interruption, such that before and after executing said set of steps the nodal tree arrangement is configured for finding any data record stored therein;

providing a signal to indicate whether or not each of the atomic actions in the plurality has been performed; and

in response to an undesired and abnormal system interruption during the step of using the plurality of atomic actions to reconfigure the nodal tree network, resuming the normal operating mode and completing the plurality of atomic actions during the normal operating mode so that the nodal tree arrangement reconfiguration permits concurrent access of the memory by the plurality of processing elements.

2. A method of maintaining the nodal tree arrangement, according to claim 1, wherein the step of reconfiguring the nodal tree arrangement using the plurality of atomic actions includes performing each atomic action in a manner that leaves the tree in a connected state.

3. A method of maintaining the nodal tree arrangement, according to claim 1, wherein after completing any of the atomic actions the tree arrangement is retained in an uncompleted reconfiguration state and the nodal tree arrangement is maintained via crash recovery without additional special recovery nodal-tree reformation steps required as a result of the undesired and abnormal system interruption.

4. A method of maintaining the nodal tree arrangement, according to claim 1, wherein after completion of each of the atomic actions the computer system enters an intermediate state from which another atomic action begins.

5. A method of maintaining the nodal tree arrangement, according to claim 1, wherein the step of providing the signal includes the step of indicating that the tree arrangement is being reconfigured.

6. A method of maintaining the nodal tree arrangement, according to claim 5, further comprising a scheduling of a completing atomic action in response to detecting during the normal operating mode that the tree arrangement is in an intermediate state.

7. A method of maintaining the nodal tree arrangement, according to claim 6, further comprising performing the step of completing the scheduled atomic action and, in response thereto, verifying that the tree arrangement is correctly configured.

8. A method of maintaining the nodal tree arrangement, according to claim 1, wherein each node maintains, and has allocated thereto, an entire key space until said node is de-allocated.

9. For use in a computer system which allows a plurality of processing elements to access a memory concurrently during a normal operating mode, a method of maintaining a nodal tree arrangement which is a data structure, comprising the steps of:

establishing a multitude of data records, each of said data records having an associated node and said nodes being linked in the nodal tree arrangement to other of the nodes by a set of predetermined relationships, and wherein each node maintains a key space by performing at least one of the following steps;

containing data records containing index terms for the data records, or delegating responsibility for at least a part of the key space to a sibling node;

during the normal operating mode, using a sequence of atomic actions to reconfigure the nodal tree arrangement so as to replace, delete or add a data record;

each atomic action including executing a set of steps having an end marker indicating that the set of steps has been completed, said set of steps executed without apparent interruption, such that before and after executing said set of steps the nodal tree arrangement is configured for finding any data record stored therein;

providing a signal to indicate whether or not each of the atomic actions in the sequence has been performed; and

in response to an undesired and abnormal system interruption during the step of using the sequence of atomic actions to reconfigure the nodal tree network, resuming the normal operating mode and completing the sequence of atomic actions during the normal operating mode so that the nodal tree arrangement permits concurrent access of the memory by the plurality of processing elements.

10. A method of maintaining the nodal tree arrangement, according to claim 9, wherein at least one of the predetermined relationships includes at least one of a plurality of sibling nodes.

11. A method of maintaining nodal the tree arrangement, according to claim 9, wherein at least one of the predetermined relationships includes a parent node.

12. A method of maintaining the nodal tree arrangement, according to claim 9, wherein at least two of the predetermined relationships together include a parent node, a child node and a sibling node.