US5123104A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for concurrent modification of an index tree in a transaction processing system utilizing selective indication of structural modification operations
Assignee: International Business Machines Corp
•
Filing: 1988-04-08
•
Granted: 1992-06-16
•
Expires: 2008-04-08
Abstract
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.
Inventors
- 👤 Frank E. Levine
- 👤 Chandrasekaran Mohan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 13:35
CPC Classifications
G; G06; G06F; G06F17/00; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; G06F12/00; G06F16/23; G06F16/2308; G06F16/2336; G06F16/2343; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
265 words
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.
Claim 2
Dependent Claim
265 words
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.
Claim 3
Dependent Claim
66 words
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.
Claim 4
Dependent Claim
69 words
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.
Claim 5
Dependent Claim
61 words
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.
Claim 6
Dependent Claim
275 words
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.
Claim 7
Dependent Claim
275 words
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.
Claim 8
Dependent Claim
40 words
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.
Claim 9
Dependent Claim
45 words
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.
Claim 10
Dependent Claim
268 words
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.
Claim 11
Dependent Claim
268 words
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.
Claim 12
Dependent Claim
45 words
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.
Claim 13
Dependent Claim
267 words
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.
Claim 14
Dependent Claim
267 words
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.
Claim 15
Dependent Claim
67 words
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.
Claim 16
Dependent Claim
69 words
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.
Claim 17
Dependent Claim
62 words
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.
Claim 18
Dependent Claim
276 words
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.
Claim 19
Dependent Claim
276 words
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.
Claim 20
Dependent Claim
41 words
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.
Claim 21
Dependent Claim
46 words
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.
Claim 22
Dependent Claim
267 words
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.
Claim 23
Dependent Claim
267 words
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.
Claim 24
Dependent Claim
46 words
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.
References Cited (Backward Citations)
US4318184A
Cited
US4468728A
Cited
US4507751A
Cited
US4627019A
Cited
US4479196A
Cited
US4698752A
Cited
US4606002A
Cited
US4611298A
Cited
US4704703A
Cited
US4868744A
Cited
JPS62206628A
Cited
US4878167A
Cited
US4823310A
Cited
US4914569A
Cited
US4945474A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-06-16 | 1995-12-16 | 1996-06-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-06-16 | 1999-12-16 | 2000-06-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-06-16 | 2003-12-16 | 2004-06-16 | $7700.00 | Window Closed / Lapsed |