A method and system for improving performance with single-instance-storage volumes by leveraging data locality is provided. A client provides a set of fingerprints generated from data segments to be saved to a single-instance storage volume and receives the information on whether a data segment exists on the single-instance storage volume and where it is stored if a data segment exists. Based on its received information, the client determines if a number of non-sequential accesses of a computer-readable medium for the set of segments from the single-instance-storage volume exceeds a predetermined threshold. If so, the client provides the whole set of data segments for storage within the single-instance storage volume regardless of whether or not the data segments are duplicate data segments. These sent data segments will be stored contiguously within the single-instance storage volume while the duplicates will be removed from their previous stored locations.