Index-only tables with nested group keys

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.

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.