Patent ID: 8386494
Filing Date: 2013-02-26
Classification: G06F

Abstract:
1. A method comprising: associating keys of an index with corresponding data chunks in a storage system; in response to a request for a particular key, accessing, by a system having a processor, a particular location in a first data structure maintained in a first storage using a first portion of the particular key; in response to the particular location containing a first value, indicating, by the system, that the particular key is not present in the index; and in response to the particular location containing a second value, accessing, by the system, a map using a second portion of the particular key to retrieve an entry in a second data structure maintained in a second storage, wherein the second data structure provides a collision chain to link entries of the second data structure that share a common value of the second portion of the particular key, wherein the first data structure, map, and second data structure are part of the index.