 |
|
|
|
|
|
 Title: |
US4914569:
Method for concurrent record access, insertion, deletion and alteration using an index tree
[ Derwent Title ]
|
| Country: |
US United States of America
|
| |
| Inventor: |
Levine, Frank E.; Austin, TX
Mohan, Chandrasekaran; San Jose, CA
|
| Assignee: |
International Business Machines Corporation, Armonk, NY
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company
|
| Published / Filed: |
1990-04-03
/ 1987-10-30
|
| Application Number: |
US1987000115146
|
| IPC Code: |
Advanced:
G06F 12/00;
G06F 17/30;
Core:
more...
IPC-7:
G06F 15/40;
|
| U.S. Class: |
Current:
707/008;
707/E17.007;
707/E17.012;
Original:
364/200;
364/282.1;
364/282.2;
364/246.6;
364/246.8;
364/300;
|
| Field of Search: |
364/200 MS File,900 MS File,300
|
| Priority Number: |
| 1987-10-30 |
US1987000115146 |
|
| 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.
|
| Attorney, Agent or Firm: |
Tyson, Thomas E. ;
|
| Primary / Asst. Examiners: |
Lee, Thomas C.;
|
| Maintenance Status: |
CC Certificate of Correction issued
|
| INPADOC Legal Status: |
Show legal status actions
Family Legal Status Report
|
| Designated Country: |
DE FR GB IT
|
| Family: |
Show 18 known family members
|
First Claim:
Show all 10 claims |
What is claimed is:
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.
|
| Background / Summary: |
Show background / summary
|
| Drawing Descriptions: |
Show drawing descriptions
|
| Description: |
Show description
|
| Forward References: |
Show 56 U.S. patent(s) that reference this one
|
|
|
|
|
|
|
| Foreign References: |
None
|
| Other Abstract Info: |
DERABS G89-131834
|
| Other References: |
"Efficient Locking for Concurrent Operations on B-Trees", ACM Transactions on Database Systems, vol. 6, No. 4, Dec., 1981, pp. 650-670.
(21 pages)
Cited by 14 patents
"Ubiquitous B-Tree", Computer Surveys, vol. 11, No. 2, Jun., 1979, pp. 121-137.
(17 pages)
Cited by 49 patents
"Concurrent Operations on B-Trees with Overtaking", by Sagiv ACM Sigact-Sigmond Symposium on Principles of Database System, Mar., 1985, pp. 28-37.
"Index Locking and Splitting", IBM Technical Disclosure Bulletin, vol. 25, No. 7B, Dec., 1985, pp. 3725-3927.
"Locking Protocol for Concurrent Operations on B-Trees", IBM Technical Disclosure Bulletin, vol. 19, No. 10, Mar., 1977, pp. 3887-3889.
Data Structure and Algorithms, by Aho, Hopcroft and Ullman, Addison-Wesley Publishing Company, 1983, pp. 170-179.
"Multilevel Locking with Deadlock Avoidance", IBM Technical Disclosure Bulletin, vol. 21, No. 4, Sep., 1987, pp. 1723-1728.
"Locking Technique in a Relational Data Base: Locking on Intents", , IBM Technical Disclosure Bulletin, vol. 18, No. 7, Dec., 1975, pp. 2324-2326.
"Index Mini-Pages", IBM Technical Disclosure Bulletin, vol. 25, No. 11A, Apr., 1983, pp. 5460-5463.
"Locking Mechanism for Controlling Access to Data Base Resources", IBM Technical Disclosure Bulletin, vol. 29, No. 3, Aug., 1986, pp. 1193-1195.
"Multi-Access Data Sharing Facility Utilizing Magnetic Bubble Storage", IBM Technical Disclosure Bulletin, vol. 23, No. 8, Jan., 1981, pp. 3882-3885.
"Integrated Concurrency and Shared Buffer Coherency Control for Multi-Systems", IBM Technical Disclosure Bulletin, vol. 28, No. 10, Mar., 1986, pp. 4642-4650.
"Copy Currency Control in Distributed Data Networks", IBM Technical Disclosure Bulletin, vol. 24, No. 5, Oct., 1981, pp. 2348-2351.
"Performance Without Deadlock Algorithm", IBM Technical Disclosure Bulletin, vol. 22, No. 10, Mar., 1980, p. 6759.
"Sharing of Disk Files Without Locking", IBM Technical Disclosure Bulletin, vol. 22, No. 7, Dec., 1979, pp. 2887-2889.
"Hardware-Supported Critical Sections to Minimize Process Waiting/Dispatching", IBM Technical Disclosure Bulletin, vol. 22, No. 3, Aug., 1979, pp. 1290-1293.
"Spin Queues", IBM Technical Disclosure Bulletin, vol. 18, No. 6, Nov., 1975, pp. 1953-1954.
"Locking Architecture in a Multiple Virtual Memory Multi-Processing System", IBM Technical Disclosure Bulletin, vol. 16, No. 7, Dec. 1973.
"Transaction Monitoring in Encompass (TM): Reliable Distributed Transaction Processing", by Borr, Procedures International Conference on Very Large Data Bases, Sep., 1981, pp. 244-254.
"Robustness to Crash in a Distributed Database: A Non Shared-Memory Multi-Processor Approach", by Borr, Proceedings 10th International Conference on Very Large Databases, Singapore, Aug., 1984.
"The Recovery Manager of the System R Database Manager", ACM Computing Surveys, vol. 13, No. 2, Jun., 1981, pp. 223-242.
(20 pages)
Cited by 18 patents
|
|
 Nominate this for the Gallery...
|
|
