Method and apparatus for concurrent modification of an index tree in a transaction processing system utilizing selective indication of structural modification operations

• US 5,123,104 A
• Filed: 04/08/1988
• Issued: 06/16/1992
• Est. Priority Date: 04/08/1988
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Levine, Frank E., Mohan, Chandrasekaran
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Treat, William M.
• Application Number:
  US07/179,190
• Time in Patent Office: 1,530 Days
• Field of Search: 364/200, 364/300, 364/900, 395/800, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A method and apparatus for concurrent modifications of an index tree in a transaction processing system. The index tree includes at least one root node having a key record reference to one or more nodes in a next lower ordered level and at least one bottom node providing access to key records. Transactions including a structure modification operation are performed by traversing the index tree to the selected node and then setting an indication of the pendency of a structure modification operation. Concurrent key record inserts or deletes are permitted throughout the index tree where no indication of a pending structure modification operation is present and are delayed where a pending structure modification operation is indicated. Similarly, transactions which include a key record delete may require a structure modification operation in the event the transaction does not reach new point of consistency and must be undone. Therefore, an indication of each key record delete which has not yet reached a new point of consistency is set and concurrent key record inserts or deletes are also delayed until the possibility of a structure modification operation is completed.

Claims

1. In a data processing system a method executed by a data processor for fetching a selected key record in a group of record keys by utilizing a portion of a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lower ordered level and having bottom nodes that provide access to said key record data in an ordered sequence of key records, said method comprising the steps performed within said data processing system of:

traversing across said nodes within said data processing system from said root node by using key record reference until an appropriate bottom node is reached;

identifying said selected key record in said bottom node;

requesting a conditional access restriction on said selected key record;

fetching said selected key record if said conditional access restriction is granted;

requesting an unconditional access restriction of said selected key record if said conditional access restriction is not granted;

examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or note said appropriate bottom node has been substantially altered;

fetching said selected key record is said appropriate bottom node has not been substantially altered; and

traversing across said nodes from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

2. The method according to claim 1, wherein said step of examining said appropriate bottom node after said unconditional access restriction has been granted to determine whether or not said appropriate bottom node has been substantially altered further includes the step of determining whether or not said selected key record is a first key record in said ordered sequence of key records within said appropriate bottom node.

3. The method of according to claim 1, wherein said step of examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered further includes the step of determining whether or not a next lower key record in said ordered sequence of key records within said appropriate bottom node is lower than said selected key record.

4. The method according to claim 1, wherein said step of examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered further includes the step of determining whether or not a key record exists in said appropriate bottom node which is lower than said selected key record.

5. In a data processing system a method executed by a data processor for inserting a single key record in a group of record keys according to a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lower ordered level and having bottom nodes that provide access to an ordered sequence of key records, said method comprising the steps performed within said data processing system of:

traversing across said nodes within said data processing system from said root node by using said key record reference until an appropriate bottom node is reached;

identifying a next higher key record than the single key record to be inserted;

requesting a conditional access restriction on said next higher key record;

inserting said single key record into said appropriate bottom node if said conditional access restriction is granted;

requesting an unconditional access restriction on said next higher key record if said conditional access restriction is not granted;

examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered;

inserting said single key record into said appropriate bottom node if said appropriate bottom node has not been substantially altered; and

traversing across said node from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

6. The method according to claim 5, wherein said step of examining said appropriate bottom node after said unconditional access restriction is granted further includes the step of determining whether said single key record is bounded on said appropriate bottom node.

7. The method according to claim 5, wherein said step of examining said appropriate bottom node after said unconditional access restriction is granted further includes the step of determining whether said appropriate bottom node is participating in a structure modification operation which is not yet complete.

8. In a data processing system a method executed by a data processor for deleting a single key record in a group of record keys according to a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lower ordered level and having bottom nodes that provide access to an ordered sequence of record keys, said method comprising the steps performed within said data processing system of:

traversing said nodes within said data processing system from said root node by using said key record reference until an appropriate bottom node is reached;

requesting a conditional access restriction on a next higher key record than the single key record to be deleted;

deleting said single key record from said appropriate bottom node if said conditional access restriction is granted;

requesting an unconditional access restriction on said next higher key record if said conditional access restriction is not granted;

examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered;

deleting said single key record from said appropriate bottom node if said appropriate bottom node has not been substantially altered; and

traversing across said nodes from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

9. The method according to claim 8, wherein said step of examining said appropriate bottom node after said unconditional access restriction is granted further includes the step of determining whether said appropriate bottom node is participating in a structure modification operation which is not yet complete.

10. A data processing system for fetching a selected key record in a group of record keys by utilizing a portion of a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lower ordered level and having bottom nodes that provide access to said key record data in an ordered sequence of key records, said data processing system comprising:

means for traversing across said nodes within said data processing system from said root node by using said key record reference until an appropriate bottom node is reached;

means for identifying said selected key record in said bottom node;

means for requesting a conditional access restriction on said selected key record;

means for fetching said selected key record if said conditional access restriction is granted;

means for requesting an unconditional access restriction of said selected key record if said conditional access restriction is not granted;

means for examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered;

means for fetching said selected key record if said appropriate bottom node has not been substantially altered; and

means for traversing across said nodes from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

11. The data processing system according to claim 10, wherein said means for examining said appropriate bottom node after said unconditional access restriction has been granted to determine whether or not said appropriate bottom node has been substantially altered further includes means for determining whether or not said selected key record is a first key record in said ordered sequence of key records within said appropriate bottom node.

12. The data processing system according to claim 10, wherein said means for examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered further includes means for determining whether or not a next lower key record in said ordered sequence of key records within said appropriate bottom node is lower than said selected key record.

13. The data processing system according to claim 10, wherein said means for examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered further includes means for determining whether or not a key record exists in said appropriate bottom node which is lower than said selected key record.

14. A data processing system for inserting a single key record in a group of record keys according to a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lowered ordered level and having bottom nodes that provide access to an ordered sequence of key records, said data processing system comprising:

means for traversing across said nodes within said data processing system from said root node by using said key record reference until an appropriate bottom node is reached;

means for identifying a next higher key record than the single key record to be inserted;

means for requesting a conditional access restriction on said next higher key record;

means for inserting said single key record into said appropriate bottom node if said conditional access restriction is granted;

means for requesting an unconditional access restriction on said next higher key record if said conditional access restriction is not granted;

means for examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered;

means for inserting said single key record into said appropriate bottom node if said appropriate bottom node has not been substantially altered; and

means for traversing across said node from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

15. The data processing system according to claim 14, wherein said means for examining said appropriate bottom node after said unconditional access restriction is granted further includes means for determining whether said single key record is bounded on said appropriate bottom node.

16. The data processing system according to claim 14, wherein said means for examining said appropriate bottom node after said unconditional access restriction is granted further includes means for determining whether said appropriate bottom node is participating in a structure modification operation which is not yet complete.

17. A data processing system for deleting a single key record in a group of record keys according to a key record through an index tree having a modifiable structure during a transaction in said data processing system wherein other transactions may concurrently modify the structure of said index tree, said index tree having at least a root node, each root node having a key record reference to one or more nodes in a next lower ordered level and having bottom nodes that provide access to an ordered sequence of record keys, said data processing system comprising:

means for traversing said nodes within said data processing system from said root node by using said key record reference until an appropriate bottom node is reached;

means for requesting a conditional access restriction on a next higher key record than the single key record to be deleted;

means for deleting said single key record from said appropriate bottom node if said conditional access restriction is granted;

means for requesting an unconditional access restriction on said next higher key record if said conditional access restriction is not granted;

means for examining said appropriate bottom node after said unconditional access restriction is granted to determine whether or not said appropriate bottom node has been substantially altered;

means for deleting said single key record from said appropriate bottom node if said appropriate bottom node has not been substantially altered; and

means for traversing across said nodes from said root node by using said key record reference until a second appropriate bottom node is reached if said appropriate bottom node has been substantially altered.

18. A data processing system according to claim 17, wherein said means for examining said appropriate bottom node after said unconditional access restriction is granted further includes means for determining whether said appropriate bottom node is participating in a structure modification operation which is not yet complete.