Patent US5758356A successfully refreshed from Google Patents.
US5758356A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High concurrency and recoverable B-tree index management method and system
Assignee: Hitachi Software Engineering Co Ltd
•
Filing: 1995-09-12
•
Granted: 1998-05-26
•
Expires: 2015-09-12
Abstract
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.
Inventors
- 👤 Norihiro Hara
- 👤 Nobuo Kawamura
- 👤 Junichiro Soshiki
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 23:38
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; G06F16/2336; G06F16/2343; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/956; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99938; Y10S707/99939; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
106 words
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.
Claim 2
Dependent Claim
106 words
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.
Claim 3
Dependent Claim
40 words
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.
Claim 4
Dependent Claim
209 words
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.
Claim 5
Dependent Claim
209 words
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.
Claim 6
Independent Claim
174 words
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.
Claim 7
Independent Claim
174 words
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.
Claim 8
Dependent Claim
46 words
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.
Claim 9
Dependent Claim
141 words
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.
Claim 10
Dependent Claim
141 words
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.
Claim 11
Dependent Claim
30 words
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.
Claim 12
Dependent Claim
43 words
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.
References Cited (Backward Citations)
US4697266A
Cited
US5265244A
Cited
US5283894A
Cited
US4945474A
Cited
US5123104A
Cited
US5175849A
Cited
US5089952A
Cited
US5265245A
Cited
US5095421A
Cited
US5319774A
Cited
US5319773A
Cited
US5333303A
Cited
US5475837A
Cited
US5204958A
Cited
US5568638A
Cited
US5418947A
Cited
US5465328A
Cited
US5560007A
Cited
US5522068A
Cited
US5596710A
Cited
US5644763A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |