US5283894A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Lockless concurrent B-tree index meta access method for cached nodes
Assignee: Individual
•
Filing: 1991-04-11
•
Granted: 1994-02-01
•
Expires: 2011-04-11
Abstract
Abstract A user interface for a database management system uses an interactive display to display information selected from the database in magnitude ordered rows comprising a set of items. Each row is an assertion consisting of a plurality of components including an entity, an attribute and a value of the attribute. The components are arranged in that fixed order in decreasing significance, respectively. In the database management system, the database is itself also stored in this format. A database engine in the database management system utilizes a B-tree index to the database and a meta accessing method for items from the database in a working cache.
Inventors
- 👤 Roger L. Deran
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:16
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/40; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
283 words
A data storage and retrieval system comprising: first generating means for generating a key sequence for constructing a basic index tree structure; second generating means for generating said basic tree index structure responsive to said key sequence; secondary direct access storage means, coupled to said first and second generating means, for storing a plurality of nodes of said basic tree index structure and corresponding key-indexed data; primary direct-access memory means for storing a selected subset of said plurality of nodes of said basic tree index structure and said corresponding key indexed data; means, coupled between said secondary storage means and said primary memory means, for copying said selected subset from said secondary storage means to said primary memory means; means, coupled to said primary memory means, for modifying said selected subset; first accessing means, coupled to said secondary storage means, responsive to a first external inputted key access sequence for sequential accessing said basic tree index structure and said corresponding key indexed data and to an external inputted key value for randomly accessing said basic tree index structure and corresponding key indexed data; second accessing means, coupled to said primary memory means, responsive to a second external inputted key access sequence for sequentially accessing said selected subset and external inputted key value for randomly accessing said selected subset; third accessing means, coupled to said primary memory means, for accessing said copied or modified selected subset; said third accessing means includes determining means for determining a key value range of one of said plurality of nodes of said selected subset and means responsive to an external inputted key value within said key value range to access said selected subset and corresponding key indexed data.
Claim 2
Dependent Claim
283 words
A data storage and retrieval system comprising: first generating means for generating a key sequence for constructing a basic index tree structure; second generating means for generating said basic tree index structure responsive to said key sequence; secondary direct access storage means, coupled to said first and second generating means, for storing a plurality of nodes of said basic tree index structure and corresponding key-indexed data; primary direct-access memory means for storing a selected subset of said plurality of nodes of said basic tree index structure and said corresponding key indexed data; means, coupled between said secondary storage means and said primary memory means, for copying said selected subset from said secondary storage means to said primary memory means; means, coupled to said primary memory means, for modifying said selected subset; first accessing means, coupled to said secondary storage means, responsive to a first external inputted key access sequence for sequential accessing said basic tree index structure and said corresponding key indexed data and to an external inputted key value for randomly accessing said basic tree index structure and corresponding key indexed data; second accessing means, coupled to said primary memory means, responsive to a second external inputted key access sequence for sequentially accessing said selected subset and external inputted key value for randomly accessing said selected subset; third accessing means, coupled to said primary memory means, for accessing said copied or modified selected subset; said third accessing means includes determining means for determining a key value range of one of said plurality of nodes of said selected subset and means responsive to an external inputted key value within said key value range to access said selected subset and corresponding key indexed data.
Claim 3
Dependent Claim
79 words
The data storage and retrieval of claim 1, wherein the second accessing means and the third accessing means are configured according to a meta access method; said primary direct access memory means configured to store and retrieve data in a fixed length; and, said secondary direct access storage means configured to store said plurality of nodes in said in said fixed length units, wherein branches of said basic tree index structure are the addresses of said fixed length units.
Claim 4
Dependent Claim
18 words
The data storage and retrieval system of claim 2, in which said meta access method is a tree.
Claim 5
Dependent Claim
16 words
The data storage and retrieval system of claim 3, in which said tree is a B-tree.
Claim 6
Dependent Claim
19 words
The data storage and retrieval system of claim 4, in which said basic tree indexed structure is a B-tree.
Claim 7
Dependent Claim
29 words
The data storage and retrieval system of claim 4, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 8
Dependent Claim
39 words
The data storage and retrieval system of claim 4, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
Claim 9
Dependent Claim
29 words
The data storage and retrieval system of claim 5, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 10
Dependent Claim
39 words
The data storage and retrieval system of claim 5, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
Claim 11
Dependent Claim
29 words
The data storage and retrieval system of claim 6, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.
Claim 12
Dependent Claim
29 words
The data storage and retrieval system of claim 8, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.
Claim 13
Dependent Claim
19 words
The data storage and retrieval system of claim 2, in which said basic tree indexed structure is a B-tree.
Claim 14
Dependent Claim
29 words
The data storage and retrieval system of claim 12, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 15
Dependent Claim
39 words
The data storage and retrieval system of claim 12, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
Claim 16
Dependent Claim
28 words
The data storage and retrieval system of claim 13, in which a data format of fixed length units of basic tree indexed structure allows prefix compression of keys.
Claim 17
Dependent Claim
19 words
The data storage and retrieval system of claim 3, in which said basic tree indexed structure is a B-tree.
Claim 18
Dependent Claim
39 words
The data storage and retrieval system of claim 16, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
Claim 19
Dependent Claim
29 words
The data storage and retrieval system of claim 16, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 20
Dependent Claim
29 words
The data storage and retrieval system of claim 18, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.
Claim 21
Dependent Claim
29 words
The data storage and retrieval system of claim 2, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 22
Dependent Claim
29 words
The data storage and retrieval system of claim 20, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.
Claim 23
Dependent Claim
29 words
The data storage and retrieval system of claim 3, further comprising means for scanning said meta access method in key sequence during updating of said basic tree indexed structure.
Claim 24
Dependent Claim
29 words
The data storage and retrieval system of claim 22, in which a data format of fixed length units of said basic tree indexed structure allows prefix compression of keys.
Claim 25
Dependent Claim
39 words
The data storage and retrieval system of claim 2, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
Claim 26
Dependent Claim
39 words
The data storage and retrieval system of claim 3, further comprising means for preventing writing of a fixed length unit on the same fixed length unit of said secondary storage means from which the fixed length unit was read.
References Cited (Backward Citations)
US4606002A
Cited
US4611298A
Cited
US4677550A
Cited
US4719571A
Cited
US4945475A
Cited
US4914569A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-01-31 | 1997-08-02 | 1998-02-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-01-31 | 2001-08-02 | 2002-02-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-01-31 | 2005-08-02 | 2006-02-01 | $7700.00 | Window Closed / Lapsed |