US 8,429,133 B2 · Partial key indexes

Abstract

A partial reverse key index is described, which allows distributed contention as resources vie to insert data into an index as well as allows range scans to be performed on the index. To do so, before an index entry for a key value is inserted into an index, the key value is transformed using a transformation operation that affects a subset of the order of the key value. The index entry is then inserted based on the transformed key value. Because the transformation operation affects the order of the key value, the transformed values associated with two consecutive key values will not necessarily be consecutive. Therefore, the index entries associated with the consecutive key values may be inserted into unrelated portions of the index.

Claims18

Dependent claims

A method for inserting entries into a hierarchical tree-structured index, the method comprising the steps of:

receiving an entry to be inserted into the hierarchical tree-structured index;
identifying a key value in said entry, wherein said key value includes at least a first subset of data and a second subset of data;
generating a transformed key value by performing an operation on the first subset of data from said key value, without performing said operation on said second subset of data from said key value;
generating a transformed entry that includes said transformed key value;
storing said transformed entry in a location within said hierarchical tree-structured index that is based upon said transformed key value;
wherein said transformed key value causes said transformed entry to be stored in a location within said hierarchical tree-structured index that maintains said entry in at least a partial ordering.

3 more elements

Dependencies are inferred from the claim text.

Partial key indexes

Life of this patent

Partial key indexes

Life of this patent

Abstract

Claims18