High concurrency and recoverable B-tree index management method and system

• US 5,758,356 A
• Filed: 09/12/1995
• Issued: 05/26/1998
• Est. Priority Date: 09/19/1994
• Status: Expired due to Term

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd., Hitachi Software Engineering Co., Ltd. (Hitachi, Ltd.)
• Inventors: Soshiki, Junichiro, Hara, Norihiro, Kawamura, Nobuo
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/527,224
• Time in Patent Office: 987 Days
• Field of Search: 395/603, 395/602, 395/604, 395/608, 395/611, 395/618, 707/202, 707/201, 707/100, 707/10, 707/9, 707/8, 707/2, 707/3
• US Class Current: 707/683
• 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/956 Hierarchical
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A database management system for accessing the same B-tree index by a plurality of transactions. When a transaction is intercepted at the intermediate stage of an index structure modification process executed by an index structure modification execution unit, the logs of the index structure modification operation at rollback is analyzed by an index structure modification operation log analysis unit. Then, an incomplete index structure change process is completed by an uncompleted index structure modification operation completion and control unit, i.e., the roll-forward operation is performed. In this manner, it is possible to provide an efficient access to the B-tree index wherein even if the tree structure modification operation by one transaction is intercepted at its intermediate stage, another transaction is allowed to access the B-tree index thereafter.

Claims

1. A B-tree index management system for a database management system to access the same B-tree index by a plurality of transactions, wherein:

when one of the plurality of transactions executes an index structure modification operation, including the update operations on a plurality of B-tree index nodes, by inserting an index constituent element to the page for data insertion or update,

if said transaction is intercepted before said index structure modification operation is completed, said index structure modification operation still not completed is made complete and rolled back to guarantee the update result by another transaction made to the nodes associated with said index structure modification operation.

2. A B-tree management system according to claim 1, wherein an access restriction, against another process to the page associated with said index structure modification operation, is released as soon as the node is updated by said index structure modification operation.

3. A B-tree index management system for a database management system to access the same B-tree index by a plurality of transactions, wherein:

when one of the plurality of transactions executes an index structure modification operation, including the update operations on a plurality of B-tree index nodes, by inserting an index constituent element to the page for data insertion or update, said B-tree management system comprises;

means for writing a record including information necessary to execute said index structure modification operation, at the start of said index structure modification operation, and writing a record representing the current stage of said index structure modification operation when each process constituting said index structure modification operation is executed;

means for rolling forward said index structure modification operation, said means for rolling forward including analysis means for determining operations necessary to complete said index structure modification operation when said one transaction is intercepted before said index structure modification operation is completed, in accordance with said records corresponding to said each operation associated with said index structure modification operation and said record corresponding to said start of said index structure modification operation; and

means for rolling back a process for an index constituent element inserted or deleted after rolling forward said index structure modification operation.

4. A method for accessing a B-tree index wherein an index structure modification operation updates a plurality of B-tree index nodes by inserting an index constituent element to the page of the data insertion or update said method comprising the steps of:

writing a record including information necessary to execute said index structure modification operation, at the start of said index structure modification operation; and

writing a record representing the current stage of said index structure modification operation when each process constituting said index structure modification operation is executed;

rolling forward said index structure modification operation, including analysis for determining operations necessary to complete said index structure modification operation when said one transaction is intercepted before said index structure modification operation is completed, in accordance with said records corresponding to said each operation or associated with said index structure modification operation and said record corresponding to said start of said index structure modification operation; and

rolling back a process for an index constituent element inserted or deleted after rolling forward said index structure modification operation.

5. A method of accessing a B-tree index according to claim 4, comprising the further step of releasing an access restriction, against another process to the page associated with said index structure modification operation, as soon as the node is updated by said index structure modification operation.

6. A fault recovery B-tree index management method of recovering an access fault which occurs during an index structure modification operation and a database management system to access the same B-tree index by a plurality of transactions, wherein the method comprises the steps of

when one of the plurality of transactions executes an index structure modification operation including the update operations on a plurality of B-tree index nodes, inserting an index constituent element to the page for data insertion or update,

when said transaction is intercepted before a B-tree index structure modification operation is completed, completing the index structure modification operation using roll forward log records taken for the period of the structure index structure modification operation and then rolling back an insertion key to gaurantee the update result by another transaction made to nodes associated with the index structure modification operation.

7. A fault recovery B-tree index management method according to claim 6, wherein said data base management system currently acts as the B-tree index with during the index structure modification operation.

8. A fault recovery B-tree index management method according to claim 6, wherein an access restriction, against another process to the page associated with said index structure modification operation, is released as soon as the note is updated by said index structure modification operation.