Patent ID: 8370315

Claim:
A computer system comprising: a server comprising a processor and a memory; an index comprising a plurality of blocks, wherein each block comprises a plurality of entries, each entry including a fingerprint and an identifier which identifies where a corresponding data segment is stored within a data storage subsystem; wherein in response to receiving a storage access request corresponding to a given fingerprint, the server is configured to: access a data structure comprising a plurality of entries, wherein each entry of the plurality of entries identifies a block of the plurality of blocks, and a fingerprint corresponding to a first entry of the block; responsive to said access of the data structure, identify a particular block of the plurality of blocks corresponding to the storage access request; and responsive to identifying the particular block, send a query corresponding to the particular block to the index; wherein in response to the query, the index is configured to convey a response to the server that indicates whether the given fingerprint is included within the particular block; wherein the plurality of blocks of the index are sorted based on a value of an entry in a given block, and wherein responsive to said access of the data structure the particular block identified is one of: a block in the index whose first entry includes a fingerprint value that is a smallest value of all first entry fingerprint values that are greater than the given fingerprint; and a block with a first entry including a fingerprint value that is a largest value of all first entry fingerprint values that are less than the given fingerprint.