System and method for managing concurrent access to data files consisting of data entries referenced by keys comprising sequence of digits

• US 5,495,609 A
• Filed: 06/07/1995
• Issued: 02/27/1996
• Est. Priority Date: 03/02/1992
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Scott, Jonathan A.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): WANG, PETER
• Application Number:
  US08/474,529
• Time in Patent Office: 265 Days
• Field of Search: 395/600, 395/650, 395/700, 395/425
• US Class Current: 707/696
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/2315 Optimistic concurrency control
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A database management system including an index with parallel read access for large amounts of keyed information. The index can be referenced for read-only access by any number of simultaneous processes in parallel with being updated by a single process where the read-only access does not involve any locking or waiting.

Claims

1. A computer data storage management system for managing concurrent access to data files consisting of data entries referenced by keys comprising sequences of digits, the system including:

means for maintaining an index to each data file comprising a digital tree structure of index nodes hierarchically arranged according to the key structure and including at least downward pointers to lower-ranking nodes or to data entries of the data files, said pointers corresponding to possible values of an index digit;

index modifying means for modifying the index tree as necessary to reflect changes in data entries;

change indication means for providing an indication of predetermined types of modifications of the index tree or of a part thereof;

index search means for searching the index for a node containing a pointer to a user-supplied key in order to permit the reading of the data entry to which the user-supplied key refers; and

means for examining said change indication to determine whether said index was modified by a concurrent access to the corresponding data file during the search of said index and for causing the index search means to repeat said search if a change was indicated during said search.

2. A system as claimed in claim 1 wherein the change indication means comprises a single change indicator for the whole of the index tree.

3. A system as claimed in claim 1 wherein the change indicator includes:

a counter, which is incremented in response to each predetermined modification of the index tree;

means for storing the value of the counter before the commencement of the search; and

means for comparing the stored counter value with the current counter value to determine if a change has occurred.

4. A system as claimed in claim 1 wherein the change indication is only examined on completion of the search.

5. A system as claimed in claim 1 in which the change indication means includes a plurality of change indicators associated with different respective parts of the index tree and in which said search is repeated only if a change to one of the different parts of the index tree is indicated and then the search of that part of the index tree only is repeated.

6. A system as claimed in claim 1 wherein the index search means performs only read access to the index without locking of the whole or part of the tree.

7. A system as claimed in claim 1 in which said user-supplied key comprises a sequence of base 2ⁿ digits, said tree comprising a base 2ⁿ digital tree in which each index node contains a leading key value and 2ⁿ pointers to each possible value of an index digit.

8. A system as claimed in claim 7 in which n is 4.

9. A system as claimed in claim 1 in which said change indication is provided only if a data entry is inserted in or deleted from said index.

10. A system as claimed in claim 1 in which said change indication is provided only if a data entry is deleted from said index.

11. A method of managing concurrent access to stored computer data files consisting of data entries referenced by keys comprising sequences of digits, said method comprising the steps of:

maintaining an index to each data file comprising a digital tree structure of index nodes hierarchically arranged according to the key structure and including at least downward pointers to lower-ranking nodes or to data entries of the data file, said pointers corresponding to possible values of an index digit;

modifying the index as necessary to reflect changes in data entries;

providing a change indication indicating the occurrence of predetermined types of modifications of the index tree or of a part thereof;

searching the index for a node containing a pointer to a user-supplied key in order to permit reading of the data entry to which the user-supplied key refers; and

examining said change indication to determine whether said index was modified by a concurrent access to the corresponding data file during the search of said index and, if so, repeating said search.

12. A method as claimed in claim 11 in which the change indication is examined after the search.

13. A method as claimed in claim 11 in which said user-supplied key comprises a sequence of base 2ⁿ digits, said tree comprising a base 2ⁿ digital tree in which each index node contains a leading key value and 2ⁿ pointers to each possible value of an index digit.

14. A method as claimed in claim 13 in which n is 4.

15. A method as claimed in claim 11 in which said change indication is provided only if a data entry is inserted in or deleted from said index.

16. A system as claimed in claim 11 in which said change indication is provided only if a data entry is deleted from said index.

17. A method as claimed in claim 11 wherein the step of providing a change indication comprises the steps of:

incrementing a counter incremented in response to each predetermined modification of the index tree;

storing the value of the counter before the commencement of the search; and

comparing the stored counter value with the current counter value to determine if a change has occurred.