Index-only tables with nested group keys
First Claim
1. 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.
2 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. 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. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14)
-
-
15. 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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification