US5089952A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for allowing weak searchers to access pointer-connected data structures without locking
Assignee: International Business Machines Corp
•
Filing: 1988-10-07
•
Granted: 1992-02-18
•
Expires: 2008-10-07
Abstract
Abstract A method for allowing weak-searchers of a B+-tree avoid locks that serialize access to the B+-tree structure. The update technique used to achieve this ensures that the B+-tree is always in a correct state on secondary storage so that repair is not necessary after a system failure. The assumption is made that the readers will complete their reading within a specified period but sometimes will need to be restarted because they have not completed their reading within a predetermined time period.
Inventors
- 👤 Gerald P. Bozman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 12:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; G06F16/13
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
195 words
A computer implemented method for performing an update to a data structure of nodes connected by address pointers while permitting weak searcher processes including processes which seek to read data values with no intent to update them and which can accept data values which were valid at sometime between beginning and end of the search, to read the data structure without locking, comprising, the steps of: if the domain of said update is contained in one node, updating said data structure by updating said one node in place; if the domain of said update exceeds one node, updating said data structure by updating the deepest safe node in said domain in place and shadow-writing updated nodes in said domain other than said deepest safe node; giving weak searcher processes read access to said data structure without placing locks on nodes in said data structure; and providing a procedure for reusing storage occupied by nodes that become disconnected from said data structure as a result of said shadow-writing of updated nodes, said procedure for reusing storage also allowing weak searcher processes that may be searching in said nodes which become disconnected to successfully complete their search.
Claim 2
Dependent Claim
195 words
A computer implemented method for performing an update to a data structure of nodes connected by address pointers while permitting weak searcher processes including processes which seek to read data values with no intent to update them and which can accept data values which were valid at sometime between beginning and end of the search, to read the data structure without locking, comprising, the steps of: if the domain of said update is contained in one node, updating said data structure by updating said one node in place; if the domain of said update exceeds one node, updating said data structure by updating the deepest safe node in said domain in place and shadow-writing updated nodes in said domain other than said deepest safe node; giving weak searcher processes read access to said data structure without placing locks on nodes in said data structure; and providing a procedure for reusing storage occupied by nodes that become disconnected from said data structure as a result of said shadow-writing of updated nodes, said procedure for reusing storage also allowing weak searcher processes that may be searching in said nodes which become disconnected to successfully complete their search.
Claim 3
Dependent Claim
37 words
The method defined in claim 1 and further comprising the step of: before updating any node in the domain of an update, locking the nodes contained in the domain of said update until said update is completed.
Claim 4
Dependent Claim
73 words
The method defined in claim 1 wherein said deepest safe node in the domain of an update that exceeds one node is updated by replacing an address pointer in said deepest safe node so that said replaced address pointer points to one of said shadow-written updated nodes rather than the unupdated version of one of said shadow-written node, thereby disconnecting from said data structure the unupdated version of at least one shadow-written node.
Claim 5
Dependent Claim
45 words
The method defined in claim 1 wherein said procedure for reusing storage comprises the step of: waiting for all weak searcher processes active at the time a node becomes disconnected to complete reading before allowing the storage occupied by said disconnected node to be reused.
Claim 6
Dependent Claim
98 words
The method defined in claim 1 wherein said procedure for reusing storage comprises the steeps of: providing a specified time period for said weak searcher processes to read said data structure; terminating any of said weak searcher processes that have not completed reading of said data structure within said specified time period; restarting said terminated weak searcher processes; and allowing storage occupied by a disconnected node to be reused after a time interval has expired, said time interval starting at the time said disconnected node became disconnected and having a duration no less than said specified time period.
Claim 7
Dependent Claim
73 words
The method defined in claim 1 wherein said procedure for reusing storage comprises the step of: allowing storage occupied by a disconnected node to be reused immediately in said data structure; having each weak searcher process determine whether each node encountered during its weak search is valid, said each weak searcher process restarting its weak search at the beginning of said data structure if an invalid node is encountered during its weak search.
Claim 8
Dependent Claim
109 words
The method defined in claim 6 wherein said step of having each weak searcher process determine whether each encountered node is valid comprises the steps of: providing a a time field in each node of said data structure; recording in said time field the time when said each node was added to said data structure; and having each weak searcher process check said time field in each node encountered during its weak search, any node encountered during its weak search which has a value in said time field that is later than the entry time into said data structure by said encountering weak searcher process being an invalid node.
Claim 9
Dependent Claim
76 words
The method defined in claim 6 wherein said step of having each weak searcher process determine whether each encountered node is valid comprises the steps of: having each weak searcher process check the key range and the level of each node encountered during its weak search, any node encountered during its weak search having a key range or level which does not have a value expected by said encountering weak searcher process being an invalid node.
Claim 10
Dependent Claim
175 words
The method defined in claim 1 wherein said procedure for reusing storage comprises the steps of: allowing storage occupied by a disconnected node to be reused immediately in said data structure; having each weak searcher process determine whether each node encountered during its weak search is valid, said each weak searcher process restarting its weak search at the beginning of said data structure if an invalid node is encountered during its weak search; said step of having each weak searcher process determine whether each node encountered during its weak search is valid comprising: providing an affix field in each node for identifying nodes which are part of said data structure; placing a unique object identifier in said affix field of each node which is part of said data structure; and for each node encountered by a weak searcher process during its weak search, checking said object identifier in said affix field to determine whether said encountered node is part of said data structure, any node not part of said data structure being an invalid node.
Claim 11
Dependent Claim
109 words
The method defined in claim 9 wherein said step of having each weak searcher process determine whether each encountered node is valid comprises the steps of: providing a a time field in each node of said data structure; recording in said time field the time when said each node was added to said data structure; and having each weak searcher process check said time field in each node encountered during its weak search, any node encountered during its weak search which has a value in said time field that is later than the entry time into said data structure by said encountering weak searcher process being an invalid node.
Claim 12
Dependent Claim
70 words
The method defined in claim 9 wherein said step of having each weak searcher process determine each encountered node is valid comprises the steps of: having each weak searcher process check the key range and the level of each node encountered during its weak search, any node having a key range or level which does not have a value expected by said encountering weak searcher process being an invalid node.
References Cited (Backward Citations)
US4054911A
Cited
US4318184A
Cited
US4236227A
Cited
US4479196A
Cited
US4611272A
Cited
US4677550A
Cited
US4561051A
Cited
US4590586A
Cited
US4725870A
Cited
US4823310A
Cited
US4914569A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-02-17 | 1995-08-19 | 1996-02-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-02-17 | 1999-08-19 | 2000-02-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-02-17 | 2003-08-19 | 2004-02-18 | $7700.00 | Window Closed / Lapsed |