Patent ID: 8176021

Claim:
A method implemented at least in part by a computer, the method comprising: receiving a request to access data in a database, the data associated with a key that identifies the data; obtaining a first index value, the first index value corresponding to the key; computing a second index value based on the first index value and a dispersion factor, the dispersion factor indicative of a maximal potential difference between the first index value and the second index value, the second index value having a same first portion as a first portion of the first index value, and computing the second index value by performing a circular bit shift on a last portion of the first index value, the last portion corresponding to the dispersion factor; and accessing an index associated with the data using the second index value, the index comprising pages that are independently lockable, each page of the index including a corresponding set of index entries, each index entry including a corresponding index value, receiving a query for a first range of index values; determining a lower bound of a transformed range corresponding to the first range; determining an upper bound of the transformed range; retrieving index entries between the lower and upper bounds; and filtering retrieved index entries that do not map to the first range of index values.