Various embodiments for managing data in a data storage having data deduplication. In response to a portion of the data storage determined to be inaccessible, an identifier of a user data segment is queried by examining a corresponding back reference data structure, the back reference data structure implemented as an approximation of a relationship between the user data segment and a particular storage block in the data storage. If the outcome of the query is negative, the user data segment is determined not associated with the particular storage block. If the outcome of the query is positive, the user data segment is warranted be examined further to determine if the user data segment is associated with the particular storage block.