A deduplicated storage system is provided according to certain embodiments that uses one or more mechanisms to update the deduplication database and remove records corresponding to data blocks that have been or will be erased from the secondary copies, without using or tracking reference counting values. Some embodiments described herein use a secondary table (for tracking archive file contents) and a bitmap to mark which primary records are present in the secondary table. In another embodiment, once the marking phase is completed, the deduplication system uses the marked-up bitmap to identify the corresponding records from the primary table that can be moved to another table for storing “zero-reference” data blocks. In other embodiments, the system will then traverse the “zero-reference” table and remove those primary data blocks from secondary storage devices.