Method for concurrent record access, insertion, deletion and alteration using an index tree

• US 4,914,569 A
• Filed: 10/30/1987
• Issued: 04/03/1990
• Est. Priority Date: 10/30/1987
• 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.
• Application Number:
  US07/115,146
• Time in Patent Office: 886 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 364/300
• US Class Current: 1/1
• 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: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method for fetching key record data in a group or record keys according to at least a portion of a key record through an index tree is provided. The index tree provides concurrent accesses of record keys by different transactions. The index tree includes a root node connected to at least one level of nodes, each node having a key record reference to one of more nodes in a next successive level and having bottom nodes that provide access to the key data. The method consists of the steps of (1) traversing across said nodes from said root node by using said key record portion until a bottom node is reached; (2) limiting all but read accesses to the node being traversed and a previously accessed node, to other concurrent transactions; (3) identifying said key record in said bottom node; (4) limiting all but read accesses to said key record; (5) removing all access limitations to traversed nodes; (6) fetching key record data; and (7) removing the access limitation to the key record after the record data has been fetched. Further, methods for inserting and deleting record keys are provided. Additionally, a method for changing the index tree structure while allowing concurrent accesses to take place is provided.

Claims

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

(a) traversing across said nodes in said data processing memory from said root node through said intermediate level of nodes by accessing a node using said key record portion of the root node and traversing to a next node indicated by said key record portion of the accessed node until a bottom node is reached;

(b) limiting all but read accesses to the node being accessed and an immediate previously accessed node in said data processing memory, to other concurrent transactions in said data processing system;

(c) identifying and accessing said key record in said bottom node;

(d) limiting all but read accesses to said key record;

(e) removing all access limitations to the accessed nodes including the bottom node except for the accessed key record;

(f) fetching key record data; and

(g) removing the access limitation to the key record after the record data has been fetched.

2. A method according to claim 1 wherein said step (c) further includes the steps of:

(c1) identifying and accessing said record keys in said node;

(c2) determining from said record keys in the node if another node is to be accessed;

(c3) if another node is to be accessed, returning to step (a); and

(c4) if another node is not to be accessed, identifying the key record data according to the portion of the key record.

3. A method according to claim 2 wherein said step (f) includes the steps of:

(f1) retrieving said key record in said node;

(f2) accessing a record according said key record in said node; and

(f3) returning record data from said record.

4. A method according to claim 3 wherein said step (g) further includes waiting until the transaction requiring the fetch of key record data is completed before the access limitation is removed from the 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 stored in a data processing memory according to a key record through an index tree during a transaction in the data processing system wherein other transactions concurrently access said record keys through said index tree, said index tree having at least a root node, at least one intermediate level of at least one node, each node having a key record reference to one or more nodes n a next successive level of nodes and having bottom nodes that provide access to said record keys, said method comprising the steps of:

(a) limiting all accesses to the key record being inserted;

(b) traversing across said nodes in said data processing memory from said root node through said intermediate level of nodes by accessing a node using said key record of said root node and traversing to a next node indicated by said key record of said accessed node until a bottom node is reached;

(c) limiting all but read accesses to the node being accessed and not more than one immediately previous accessed node, to other concurrent transactions in said data processing system as said nodes are traversed;

(d) identifying a next successively located key record relative to the key record to be inserted in said node and limiting all access to the bottom node;

(e) limiting all accesses to said next successively located key record;

(f) inserting said key record;

thereafter,

(g) removing the access limitation to the next successively located key record and the bottom node; and

thereafter,

(h) removing all remaining access limitations to the accessed nodes.

6. A method according to claim 5 wherein step (f) includes the steps of:

(f1) determining if the key record can be inserted in said node;

(f2) if the key can be inserted into the node, proceeding to step (f6);

(f3) if the key cannot be inserted into the node, providing an indication that the index tree structure is being changed;

(f4) altering the index tree structure to add a node to receive the key record;

(f5) removing the indication of an index tree structure change; and

(f6) inserting aid key record in the node.

7. In a data processing system, a method executed by a data processor for deleting a key record in a group of record keys stored in a data processing memory according to a key record through an index tree during a transaction in the data processing system wherein other transactions concurrently access said record keys through said index tree, said index tree having a root node connected to at least one intermediate level of nodes, each node having a key record reference to one or more nodes in a next successive level and having bottom nodes that provide access to said record keys, said method comprising the steps of:

(a) traversing across said nodes from said root node in said data processing memory through said intermediate level of nodes by accessing a node according to said key record and traversing to a next node indicated by said key record of said accessed node until a bottom node is reached;

(b) limiting all but read accesses to the node being accessed and not more than one immediately previous accessed node, to other concurrent transactions in said data processing system as said nodes are accessed;

(c) identifying a next successively located key record relative to the key record to be deleted in said bottom node and limiting all access to the bottom node;

(d) limiting all accesses to said next successively located key record;

(e) deleting said key record;

thereafter,

(f) removing all remaining access limitations to the accessed nodes; and

thereafter,

(g) removing the access limitation to the next successively located key record.

8. A method according to claim 7 wherein step (e) includes the steps of:

(e1) determining if the key record to be deleted is the only key record in said node;

(e2) if the key to be deleted is not the only key in the node, deleting said key record in the node and then proceeding to step (f);

(e3) if the key to be deleted is the only key in the node, providing an indication that the index tree structure is being changed;

(e4) deleting said key record in the node;

(e5) altering the index tree structure to remove the node; and

(e6) removing the indication of an index tree structure change.

9. A method according to claim 8 wherein said step (g) further includes waiting until the transaction requiring the deletion of the key record is completed before the access limitation is removed from the key record.

10. In a data processing system, a method executed by a data processor for altering an index tree structure that provides access to at least one key record in a group of record keys stored in a data processing memory according to a key record for a transaction in the data processing system wherein other transactions concurrently access said record keys through said index tree, said index tree structure having at least one node, said node having a key record reference to either another node or having a key record reference providing direct access to said key record, said index tree including an indication when said index tree is being changed said method comprising the steps of:

(a) determining that no indication of an index tree change is present in said data processing system;

(b) providing the indication of an index tree change that allows concurrent non-altering access to the index tree to said data processing system;

(c) altering said index tree node in said data processing memory;

(d) allowing concurrent non-altering access to said index tree while said index tree is being altered; and

(e) removing the indication of an index tree change after completion of said altering step.