US5852822A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Index-only tables with nested group keys
Assignee: Oracle International Corp
•
Filing: 1996-12-09
•
Granted: 1998-12-22
•
Expires: 2016-12-09
Abstract
Abstract A method and apparatus for building, maintaining, and using a multi-level index is provided. The multi-level index is accessed using a key. The key is divided into multiple portions referred to as sub-keys. The first level of the multi-level index is built on a first-level sub-key. Each index entry at the first-level is for a particular first-level sub-key value, and either includes sub-entries associated with second-level sub-key values or a reference to a second-level data retrieval structure. All second-level data retrieval structures are built on the portion of the key that has been designated as the second-level sub-key. As the vocabulary of the first-level sub-key becomes exhausted, fewer maintenance operations will have to be performed to maintain the first-level data retrieval structure. This decreases the overhead and increases the concurrency in a database system that uses the multiple-level index. The multi-level index structure is especially suited for queries that retrieve all values for a given first-level sub-key. The structure also has reduced storage costs compared to a single-level index structure, since first-level sub-key values are stored only once for each nested group.
Inventors
- 👤 Jagannathan Srinivasan
- 👤 Samuel DeFazio
- 👤 Jayanta Banerjee
- 👤 Chuck Freiwald
- 👤 Souripriya Das
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:35
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934; Y10S707/99936; Y10S707/99951; Y10S707/99952
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
106 words
A method for building a multiple-level index on a key, the method comprising the steps of: dividing said key into a plurality of sub-keys; building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.
Claim 2
Independent Claim
106 words
A method for building a multiple-level index on a key, the method comprising the steps of: dividing said key into a plurality of sub-keys; building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.
Claim 3
Dependent Claim
90 words
The method of claim 1 wherein: if the size of a group of second-level sub-key values associated with a first-level sub-key value is less than a predetermined threshold, then storing in said first-level data retrieval structure sub-entries that identify said second-level sub-key values that are associated with said first-level sub-key value; and if the size of the group of second-level sub-key values associated with said first-level sub-key value exceeds said predetermined threshold, then creating a second-level data retrieval structure for said first-level sub-key value based on said second-level sub-key values.
Claim 4
Dependent Claim
53 words
The method of claim 1 wherein: the step of building a first-level data retrieval structure includes building one of a B-tree or hash table based on said first-level sub-key; and the step of building a second-level data retrieval structure includes building one of a B-tree or hash table based on said second-level sub-key.
Claim 5
Dependent Claim
78 words
The method of claim 3 wherein: the step of building a second-level data retrieval structure includes building a second-level B-tree based on said second-level sub-key, said second-level B-tree having a plurality of leaf nodes; the method further comprises the steps of: linking said plurality of leaf nodes to form a leaf node chain; and establishing a link between said index entry associated with said particular first-level sub-key value and a first leaf node in said leaf node chain.
Claim 6
Dependent Claim
75 words
The method of claim 4 further comprising the steps of: receiving a query that requests information from all index entries associated with said particular first-level sub-key value; traversing said first-level B-tree to locate said index entry associated with said particular first-level sub-key value; following said link from said index entry to said first leaf node in said leaf node chain; and following said leaf node chain to retrieve information from said plurality of leaf nodes.
Claim 7
Dependent Claim
100 words
The method of claim 1 wherein: the key is a combination of a word value and a document identifier; and the step of dividing the key into a plurality of sub-keys includes establishing the word value as the first-level sub-key and the document identifier as the second level sub-key; the step of building a first-level data retrieval structure includes building a first-level data retrieval structure based on word values contained in said key; and the step of building a second-level data retrieval structure includes building a second-level data retrieval structure based on document identifiers associated with a particular word value.
Claim 8
Independent Claim
187 words
A method for indexing data based on a key, the method comprising the steps of: dividing said key into a plurality of sub-keys; building a B-tree based on a first-level sub-key of said plurality of sub-keys; inserting an index entry into said B-tree by performing the steps of receiving a request to insert a row of data; reading a key value from said row of data; dividing said key value into a plurality of sub-key values, said plurality of sub-key values including a first-level sub-key value; traversing said B-tree to locate a leaf node of said B-tree that is associated with a range that includes said first-level sub-key value; determining whether said leaf node already contains an entry for said first-level sub-key value; if said leaf node does not already contain an entry for said first-level sub-key value, then inserting an entry for said first-level sub-key value into said leaf node; creating a sub-entry that contains all sub-key values other than said first-level sub-key value and all non-key column values of said row of data; and storing said sub-entry in said entry for said first-level sub-key value.
Claim 9
Independent Claim
187 words
A method for indexing data based on a key, the method comprising the steps of: dividing said key into a plurality of sub-keys; building a B-tree based on a first-level sub-key of said plurality of sub-keys; inserting an index entry into said B-tree by performing the steps of receiving a request to insert a row of data; reading a key value from said row of data; dividing said key value into a plurality of sub-key values, said plurality of sub-key values including a first-level sub-key value; traversing said B-tree to locate a leaf node of said B-tree that is associated with a range that includes said first-level sub-key value; determining whether said leaf node already contains an entry for said first-level sub-key value; if said leaf node does not already contain an entry for said first-level sub-key value, then inserting an entry for said first-level sub-key value into said leaf node; creating a sub-entry that contains all sub-key values other than said first-level sub-key value and all non-key column values of said row of data; and storing said sub-entry in said entry for said first-level sub-key value.
Claim 10
Dependent Claim
113 words
The method of claim 7 further comprising the steps of: determining whether the size of sub-entries associated with said entry for said first-level sub-key value exceeds a predetermined threshold; and if the size of sub-entries associated with said entry for said first-level sub-key value exceeds a predetermined threshold, then building a second-level data retrieval structure based on a second-level sub-key of said plurality of sub-keys; storing said sub-entries that reside in said entry for said first-level sub-key value in said second-level data retrieval structure; removing said sub-entries from said entry for said first-level sub-key value; and storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure.
Claim 11
Dependent Claim
67 words
The method of claim 8 wherein: the step of building a second-level data retrieval structure includes the step of building a second-level B-tree; and the step of storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure includes the step of storing in said entry for said first-level sub-key value a pointer to a root node of said second-level B-tree.
Claim 12
Dependent Claim
73 words
The method of claim 9 wherein: the method further includes the step of linking leaf nodes of said second-level B-tree to form a leaf node chain; and the step of storing in said entry for said first-level sub-key value a reference to said second-level data retrieval structure further includes the step of storing in said entry for said first-level sub-key value a pointer to a first leaf node in said leaf node chain.
Claim 13
Dependent Claim
24 words
The method of claim 8 wherein the step of building a second-level data retrieval structure includes the step of building a second-level hash table.
Claim 14
Dependent Claim
120 words
The method of claim 8 further comprising the steps of: receiving a query that specifies said key value; reading said first-level sub-key value from said key value contained in said query; traversing said B-tree based on said first-level sub-key value to locate said leaf node associated with said range that includes said first-level sub-key value; locating said entry for said first-level sub-key value within said leaf node; using said reference to said second-level data retrieval structure to locate said second-level data retrieval structure; reading a second-level sub-key value from said key value contained in said query; using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure; and reading said non-key column values from said sub-entry.
Claim 15
Dependent Claim
45 words
The method of claim 12 wherein: said second-level data retrieval structure is a second-level B-tree; and the step of using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure includes traversing said second-level B-tree based on said second-level sub-key value.
Claim 16
Dependent Claim
44 words
The method of claim 12 wherein: said second-level data retrieval structure is a hash table; and the step of using said second-level sub-key value to locate said sub-entry within said second-level data retrieval structure includes performing a hash function on said second-level sub-key value.
Claim 17
Dependent Claim
127 words
A computer-readable medium having stored thereon sequences of instructions for building a multiple-level index on a key, the sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of: dividing said key into a plurality of sub-keys; building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.
Claim 18
Dependent Claim
127 words
A computer-readable medium having stored thereon sequences of instructions for building a multiple-level index on a key, the sequences of instructions including instructions which, when executed by a processor, cause said processor to perform the steps of: dividing said key into a plurality of sub-keys; building a first-level data retrieval structure based on a first-level sub-key of said plurality of sub-keys, said first-level data retrieval structure including an index entry associated with a particular first-level sub-key value; and building a second-level data retrieval structure for said particular first-level sub-key value, said second-level data retrieval structure being built on a second-level sub-key of said plurality of sub-keys; and establishing a link between said index entry associated with said particular first-level sub-key value and said second-level data retrieval structure.
Claim 19
Dependent Claim
96 words
The computer-readable medium of claim 15 further including instructions for: if a first-level sub-key value is associated with a group of second-level sub-key values whose total size is less than a predetermined threshold, then storing in said first-level data retrieval structure sub-entries that identify said second-level sub-key values that are associated with said first-level sub-key value; and if said first-level sub-key value is associated with a group of second-level sub-key values whose total size exceeds said predetermined threshold, then creating a second-level data retrieval structure for said first-level sub-key value based on said second-level sub-key values.
Claim 20
Dependent Claim
51 words
The computer-readable medium of claim 15 wherein: the step of building a first-level data retrieval structure includes building a first-level B-tree based on said first-level sub-key; and the step of building a second-level data retrieval structure includes building one of a B-tree or a hash table based on said second-level sub-key.
Claim 21
Dependent Claim
83 words
The computer-readable medium of claim 17 wherein: the step of building a second-level data retrieval structure includes building a second-level B-tree based on said second-level sub-key, said second-level B-tree having a plurality of leaf nodes; the computer-readable medium further comprises instructions for performing the steps of: linking said plurality of leaf nodes to form a leaf node chain; and establishing a link between said index entry associated with said particular first-level sub-key value and a first leaf node in said leaf node chain.
Claim 22
Dependent Claim
78 words
The computer-readable of claim 18 further comprising instructions for performing the steps of: receiving a query that requests information from all index entries associated with said particular first-level sub-key value; traversing said first-level B-tree to locate said index entry associated with said particular first-level sub-key value; following said link from said index entry to said first leaf node in said leaf node chain; and following said leaf node chain to retrieve information from said plurality of leaf nodes.
Claim 23
Dependent Claim
101 words
The computer-readable medium of claim 15 wherein: the key is a combination of a word value and a document identifier; and the step of dividing the key into a plurality of sub-keys includes establishing the word value as the first-level sub-key and the document identifier as the second level sub-key; the step of building a first-level data retrieval structure includes building a first-level data retrieval structure based on word values contained in said key; and the step of building a second-level data retrieval structure includes building a second-level data retrieval structure based on document identifiers associated with a particular word value.
References Cited (Backward Citations)
US5404514A
Cited
US5551027A
Cited
US5619709A
Cited
US5623679A
Cited
US5623681A
Cited
US5706365A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-21 | 2002-06-22 | 2002-12-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-21 | 2006-06-22 | 2006-12-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-21 | 2010-06-22 | 2010-12-22 | $7700.00 | Window Closed / Lapsed |