A computer-implemented method for removing unreferenced data segments from deduplicated data systems, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising: identifying a deduplicated data system that reduces redundant data by only storing single instances of data segments, the deduplicated data system comprising: a plurality of data segments (224, 422-458); a plurality of data objects (222, 402-412) that reference at least a portion of the data segments; a plurality of containers (226, 460, 470, 620 to 628) that contain the data segments referenced by the data objects; dividing the data objects within the deduplicated data system into a plurality of data object groups; monitoring the data object groups to identify at least one data object group that has changed subsequent to a prior mark-and-sweep cycle that removed data segments that were not referenced by data objects within the deduplicated data system, wherein monitoring the data object groups comprises identifying a data object group with at least one of: an added data object; a removed data object; a changed data object; identifying each container (226, 460, 470, 620 to 628) within the deduplicated data system that contains data segments referenced by data objects within the changed data object group; characterized in that the method further comprises: performing a mark-and-sweep cycle that comprises a mark operation and a sweep operation, wherein: the mark operation comprises: marking each referenced data segment in the identified container(s) (226, 460, 470, 620 to 628) that contains data segments (224, 422-458) referenced by data objects within the changed data object group, the sweep operation comprises: sweeping only each identified container; removing, while sweeping only each identified container, unmarked data segments from the identified subset of containers. identifying a deduplicated data system that reduces redundant data by only storing single instances of data segments, the deduplicated data system comprising: a plurality of data segments (224, 422-458); a plurality of data objects (222, 402-412) that reference at least a portion of the data segments; a plurality of containers (226, 460, 470, 620 to 628) that contain the data segments referenced by the data objects; a plurality of data segments (224, 422-458); a plurality of data objects (222, 402-412) that reference at least a portion of the data segments; a plurality of containers (226, 460, 470, 620 to 628) that contain the data segments referenced by the data objects; dividing the data objects within the deduplicated data system into a plurality of data object groups; monitoring the data object groups to identify at least one data object group that has changed subsequent to a prior mark-and-sweep cycle that removed data segments that were not referenced by data objects within the deduplicated data system, wherein monitoring the data object groups comprises identifying a data object group with at least one of: an added data object; a removed data object; a changed data object; an added data object; a removed data object; a changed data object; identifying each container (226, 460, 470, 620 to 628) within the deduplicated data system that contains data segments referenced by data objects within the changed data object group; performing a mark-and-sweep cycle that comprises a mark operation and a sweep operation, wherein: the mark operation comprises: the mark operation comprises: marking each referenced data segment in the identified container(s) (226, 460, 470, 620 to 628) that contains data segments (224, 422-458) referenced by data objects within the changed data object group, the sweep operation comprises: sweeping only each identified container; removing, while sweeping only each identified container, unmarked data segments from the identified subset of containers. sweeping only each identified container; removing, while sweeping only each identified container, unmarked data segments from the identified subset of containers.