Indexing deduplicated data

A computer-readable storage device storing a computer program for managing data in a data storage system, the computer program including instructions for causing a computing system to:

• receive identifiers corresponding to different respective entries of a map, with a particular identifier corresponding to a particular entry of the map, the particular entry including a computed value corresponding to a particular portion of data stored in the data storage system and metadata indicating a location where the particular portion of data is stored in the data storage system;
• store at least some of the identifiers in a first portion of an index that contains multiple identifiers corresponding to a first plurality of entries of the map, the identifiers in the first portion of the index having been selected according to a first sampling criterion;
• and
• store at least some of the identifiers in a second portion of the index that contains multiple identifiers corresponding to a second plurality of entries of the map, the identifiers in the second portion of the index having been selected according to a second sampling criterion different from the first sampling criterion;
• at least some of the identifiers selected according to the first sampling criterion having been selected at least in part because they were accessed more recently than the identifiers selected according to the second sampling criterion.

A system for managing data, comprising:

• a data storage system storing the data being managed;
• and
• a computing system comprising one or more processors and at least a memory configured to manage the data based on a map, the managing including:
• receiving identifiers corresponding to different respective entries of the map, with a particular identifier corresponding to a particular entry of the map, the particular entry including a computed value corresponding to a particular portion of data stored in the data storage system and metadata indicating a location where the particular portion of data is stored in the data storage system;
• storing at least some of the identifiers in a first portion of an index that contains multiple identifiers corresponding to a first plurality of entries of the map, the identifiers in the first portion of the index having been selected according to a first sampling criterion;
• and
• storing at least some of the identifiers in a second portion of the index that contains multiple identifiers corresponding to a second plurality of entries of the map, the identifiers in the second portion of the index having been selected according to a second sampling criterion different from the first sampling criterion;
• at least some of the identifiers selected according to the first sampling criterion having been selected at least in part because they were accessed more recently than the identifiers selected according to the second sampling criterion.