US5495609A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for managing concurrent access to data files consisting of data entries referenced by keys comprising sequence of digits
Assignee: International Business Machines Corp
•
Filing: 1995-06-07
•
Granted: 1996-02-27
•
Expires: 2015-06-07
Abstract
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.
Inventors
- 👤 Jonathan A. Scott
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 04:40
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/23; G06F16/2308; G06F16/2315; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/956; Y10S707/99931; Y10S707/99938
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
196 words
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.
Claim 2
Dependent Claim
196 words
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.
Claim 3
Dependent Claim
24 words
A system as claimed in claim 1 wherein the change indication means comprises a single change indicator for the whole of the index tree.
Claim 4
Dependent Claim
61 words
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.
Claim 5
Dependent Claim
19 words
A system as claimed in claim 1 wherein the change indication is only examined on completion of the search.
Claim 6
Dependent Claim
65 words
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.
Claim 7
Dependent Claim
29 words
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.
Claim 8
Dependent Claim
51 words
A system as claimed in claim 1 in which said user-supplied key comprises a sequence of base 2 n digits, said tree comprising a base 2 n digital tree in which each index node contains a leading key value and 2 n pointers to each possible value of an index digit.
Claim 9
Dependent Claim
12 words
A system as claimed in claim 7 in which n is 4.
Claim 10
Dependent Claim
27 words
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.
Claim 11
Dependent Claim
24 words
A system as claimed in claim 1 in which said change indication is provided only if a data entry is deleted from said index.
Claim 12
Independent Claim
170 words
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.
Claim 13
Independent Claim
170 words
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.
Claim 14
Dependent Claim
17 words
A method as claimed in claim 11 in which the change indication is examined after the search.
Claim 15
Dependent Claim
51 words
A method as claimed in claim 11 in which said user-supplied key comprises a sequence of base 2 n digits, said tree comprising a base 2 n digital tree in which each index node contains a leading key value and 2 n pointers to each possible value of an index digit.
Claim 16
Dependent Claim
12 words
A method as claimed in claim 13 in which n is 4.
Claim 17
Dependent Claim
27 words
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.
Claim 18
Dependent Claim
24 words
A system as claimed in claim 11 in which said change indication is provided only if a data entry is deleted from said index.
Claim 19
Dependent Claim
63 words
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.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-02-26 | 1999-08-28 | 2000-02-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-02-26 | 2003-08-28 | 2004-02-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-02-26 | 2007-08-28 | 2008-02-27 | $7700.00 | Window Closed / Lapsed |